/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Sema/IdentifierResolver.cpp
Line | Count | Source (jump to first uncovered line) |
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 | 47.1k | IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {} |
47 | | }; |
48 | | |
49 | | IdDeclInfoPool *CurPool = nullptr; |
50 | | unsigned int CurIndex = POOL_SIZE; |
51 | | |
52 | | public: |
53 | 102k | IdDeclInfoMap() = default; |
54 | | |
55 | 96.6k | ~IdDeclInfoMap() { |
56 | 96.6k | IdDeclInfoPool *Cur = CurPool; |
57 | 140k | while (IdDeclInfoPool *P = Cur) { |
58 | 43.5k | Cur = Cur->Next; |
59 | 43.5k | delete P; |
60 | 43.5k | } |
61 | 96.6k | } |
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 | 3.34M | void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) { |
75 | 6.00M | for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I2.66M ) { |
76 | 6.00M | if (D == *(I-1)) { |
77 | 3.34M | Decls.erase(I-1); |
78 | 3.34M | return; |
79 | 3.34M | } |
80 | 6.00M | } |
81 | | |
82 | 0 | llvm_unreachable("Didn't find this decl on its identifier's chain!"); |
83 | 0 | } |
84 | | |
85 | | //===----------------------------------------------------------------------===// |
86 | | // IdentifierResolver Implementation |
87 | | //===----------------------------------------------------------------------===// |
88 | | |
89 | | IdentifierResolver::IdentifierResolver(Preprocessor &PP) |
90 | 102k | : LangOpt(PP.getLangOpts()), PP(PP), IdDeclInfos(new IdDeclInfoMap) {} |
91 | | |
92 | 96.6k | IdentifierResolver::~IdentifierResolver() { |
93 | 96.6k | delete IdDeclInfos; |
94 | 96.6k | } |
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 | 58.7M | bool AllowInlineNamespace) const { |
101 | 58.7M | Ctx = Ctx->getRedeclContext(); |
102 | | |
103 | 58.7M | if (Ctx->isFunctionOrMethod() || (58.6M S58.6M && S->isFunctionPrototypeScope()58.4M )) { |
104 | | // Ignore the scopes associated within transparent declaration contexts. |
105 | 58.7k | while (S->getEntity() && S->getEntity()->isTransparentContext()23.3k ) |
106 | 0 | S = S->getParent(); |
107 | | |
108 | 58.7k | if (S->isDeclScope(D)) |
109 | 1.72k | return true; |
110 | 56.9k | 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 | 55.8k | assert(S->getParent() && "No TUScope?"); |
124 | | // If the current decl is in a lambda, we shouldn't consider this is a |
125 | | // redefinition as lambda has its own scope. |
126 | 55.8k | if (S->getParent()->isControlScope() && !S->isFunctionScope()727 ) { |
127 | 721 | S = S->getParent(); |
128 | 721 | if (S->isDeclScope(D)) |
129 | 55 | return true; |
130 | 721 | } |
131 | 55.8k | if (S->isFnTryCatchScope()) |
132 | 6 | return S->getParent()->isDeclScope(D); |
133 | 55.8k | } |
134 | 56.9k | return false; |
135 | 56.9k | } |
136 | | |
137 | | // FIXME: If D is a local extern declaration, this check doesn't make sense; |
138 | | // we should be checking its lexical context instead in that case, because |
139 | | // that is its scope. |
140 | 58.6M | DeclContext *DCtx = D->getDeclContext()->getRedeclContext(); |
141 | 58.6M | return AllowInlineNamespace ? Ctx->InEnclosingNamespaceSetOf(DCtx)1.17M |
142 | 58.6M | : Ctx->Equals(DCtx)57.4M ; |
143 | 58.7M | } |
144 | | |
145 | | /// AddDecl - Link the decl to its shadowed decl chain. |
146 | 63.1M | void IdentifierResolver::AddDecl(NamedDecl *D) { |
147 | 63.1M | DeclarationName Name = D->getDeclName(); |
148 | 63.1M | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
149 | 62.3M | updatingIdentifier(*II); |
150 | | |
151 | 63.1M | void *Ptr = Name.getFETokenInfo(); |
152 | | |
153 | 63.1M | if (!Ptr) { |
154 | 52.1M | Name.setFETokenInfo(D); |
155 | 52.1M | return; |
156 | 52.1M | } |
157 | | |
158 | 10.9M | IdDeclInfo *IDI; |
159 | | |
160 | 10.9M | if (isDeclPtr(Ptr)) { |
161 | 2.32M | Name.setFETokenInfo(nullptr); |
162 | 2.32M | IDI = &(*IdDeclInfos)[Name]; |
163 | 2.32M | NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); |
164 | 2.32M | IDI->AddDecl(PrevD); |
165 | 2.32M | } else |
166 | 8.63M | IDI = toIdDeclInfo(Ptr); |
167 | | |
168 | 10.9M | IDI->AddDecl(D); |
169 | 10.9M | } |
170 | | |
171 | 3.96k | void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) { |
172 | 3.96k | DeclarationName Name = D->getDeclName(); |
173 | 3.96k | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
174 | 3.96k | updatingIdentifier(*II); |
175 | | |
176 | 3.96k | void *Ptr = Name.getFETokenInfo(); |
177 | | |
178 | 3.96k | if (!Ptr) { |
179 | 3.62k | AddDecl(D); |
180 | 3.62k | return; |
181 | 3.62k | } |
182 | | |
183 | 342 | if (isDeclPtr(Ptr)) { |
184 | | // We only have a single declaration: insert before or after it, |
185 | | // as appropriate. |
186 | 254 | if (Pos == iterator()) { |
187 | | // Add the new declaration before the existing declaration. |
188 | 8 | NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); |
189 | 8 | RemoveDecl(PrevD); |
190 | 8 | AddDecl(D); |
191 | 8 | AddDecl(PrevD); |
192 | 246 | } else { |
193 | | // Add new declaration after the existing declaration. |
194 | 246 | AddDecl(D); |
195 | 246 | } |
196 | | |
197 | 254 | return; |
198 | 254 | } |
199 | | |
200 | | // General case: insert the declaration at the appropriate point in the |
201 | | // list, which already has at least two elements. |
202 | 88 | IdDeclInfo *IDI = toIdDeclInfo(Ptr); |
203 | 88 | if (Pos.isIterator()) { |
204 | 52 | IDI->InsertDecl(Pos.getIterator() + 1, D); |
205 | 52 | } else |
206 | 36 | IDI->InsertDecl(IDI->decls_begin(), D); |
207 | 88 | } |
208 | | |
209 | | /// RemoveDecl - Unlink the decl from its shadowed decl chain. |
210 | | /// The decl must already be part of the decl chain. |
211 | 31.8M | void IdentifierResolver::RemoveDecl(NamedDecl *D) { |
212 | 31.8M | assert(D && "null param passed"); |
213 | 0 | DeclarationName Name = D->getDeclName(); |
214 | 31.8M | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
215 | 31.1M | updatingIdentifier(*II); |
216 | | |
217 | 31.8M | void *Ptr = Name.getFETokenInfo(); |
218 | | |
219 | 31.8M | assert(Ptr && "Didn't find this decl on its identifier's chain!"); |
220 | | |
221 | 31.8M | if (isDeclPtr(Ptr)) { |
222 | 28.5M | assert(D == Ptr && "Didn't find this decl on its identifier's chain!"); |
223 | 0 | Name.setFETokenInfo(nullptr); |
224 | 28.5M | return; |
225 | 28.5M | } |
226 | | |
227 | 3.34M | return toIdDeclInfo(Ptr)->RemoveDecl(D); |
228 | 31.8M | } |
229 | | |
230 | | /// begin - Returns an iterator for decls with name 'Name'. |
231 | | IdentifierResolver::iterator |
232 | 267M | IdentifierResolver::begin(DeclarationName Name) { |
233 | 267M | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
234 | 263M | readingIdentifier(*II); |
235 | | |
236 | 267M | void *Ptr = Name.getFETokenInfo(); |
237 | 267M | if (!Ptr) return end()120M ; |
238 | | |
239 | 146M | if (isDeclPtr(Ptr)) |
240 | 121M | return iterator(static_cast<NamedDecl*>(Ptr)); |
241 | | |
242 | 25.5M | IdDeclInfo *IDI = toIdDeclInfo(Ptr); |
243 | | |
244 | 25.5M | IdDeclInfo::DeclsTy::iterator I = IDI->decls_end(); |
245 | 25.5M | if (I != IDI->decls_begin()) |
246 | 21.0M | return iterator(I-1); |
247 | | // No decls found. |
248 | 4.50M | return end(); |
249 | 25.5M | } |
250 | | |
251 | | namespace { |
252 | | |
253 | | enum DeclMatchKind { |
254 | | DMK_Different, |
255 | | DMK_Replace, |
256 | | DMK_Ignore |
257 | | }; |
258 | | |
259 | | } // namespace |
260 | | |
261 | | /// Compare two declarations to see whether they are different or, |
262 | | /// if they are the same, whether the new declaration should replace the |
263 | | /// existing declaration. |
264 | 55.9k | static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) { |
265 | | // If the declarations are identical, ignore the new one. |
266 | 55.9k | if (Existing == New) |
267 | 20.8k | return DMK_Ignore; |
268 | | |
269 | | // If the declarations have different kinds, they're obviously different. |
270 | 35.0k | if (Existing->getKind() != New->getKind()) |
271 | 2.00k | return DMK_Different; |
272 | | |
273 | | // If the declarations are redeclarations of each other, keep the newest one. |
274 | 33.0k | if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) { |
275 | | // If we're adding an imported declaration, don't replace another imported |
276 | | // declaration. |
277 | 740 | if (Existing->isFromASTFile() && New->isFromASTFile()502 ) |
278 | 502 | return DMK_Different; |
279 | | |
280 | | // If either of these is the most recent declaration, use it. |
281 | 238 | Decl *MostRecent = Existing->getMostRecentDecl(); |
282 | 238 | if (Existing == MostRecent) |
283 | 143 | return DMK_Ignore; |
284 | | |
285 | 95 | if (New == MostRecent) |
286 | 83 | return DMK_Replace; |
287 | | |
288 | | // If the existing declaration is somewhere in the previous declaration |
289 | | // chain of the new declaration, then prefer the new declaration. |
290 | 358 | for (auto RD : New->redecls())12 { |
291 | 358 | if (RD == Existing) |
292 | 5 | return DMK_Replace; |
293 | | |
294 | 353 | if (RD->isCanonicalDecl()) |
295 | 7 | break; |
296 | 353 | } |
297 | | |
298 | 7 | return DMK_Ignore; |
299 | 12 | } |
300 | | |
301 | 32.3k | return DMK_Different; |
302 | 33.0k | } |
303 | | |
304 | 246k | bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){ |
305 | 246k | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
306 | 235k | readingIdentifier(*II); |
307 | | |
308 | 246k | void *Ptr = Name.getFETokenInfo(); |
309 | | |
310 | 246k | if (!Ptr) { |
311 | 212k | Name.setFETokenInfo(D); |
312 | 212k | return true; |
313 | 212k | } |
314 | | |
315 | 34.4k | IdDeclInfo *IDI; |
316 | | |
317 | 34.4k | if (isDeclPtr(Ptr)) { |
318 | 24.3k | NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); |
319 | | |
320 | 24.3k | switch (compareDeclarations(PrevD, D)) { |
321 | 4.35k | case DMK_Different: |
322 | 4.35k | break; |
323 | | |
324 | 19.8k | case DMK_Ignore: |
325 | 19.8k | return false; |
326 | | |
327 | 84 | case DMK_Replace: |
328 | 84 | Name.setFETokenInfo(D); |
329 | 84 | return true; |
330 | 24.3k | } |
331 | | |
332 | 4.35k | Name.setFETokenInfo(nullptr); |
333 | 4.35k | IDI = &(*IdDeclInfos)[Name]; |
334 | | |
335 | | // If the existing declaration is not visible in translation unit scope, |
336 | | // then add the new top-level declaration first. |
337 | 4.35k | if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) { |
338 | 0 | IDI->AddDecl(D); |
339 | 0 | IDI->AddDecl(PrevD); |
340 | 4.35k | } else { |
341 | 4.35k | IDI->AddDecl(PrevD); |
342 | 4.35k | IDI->AddDecl(D); |
343 | 4.35k | } |
344 | 4.35k | return true; |
345 | 24.3k | } |
346 | | |
347 | 10.1k | IDI = toIdDeclInfo(Ptr); |
348 | | |
349 | | // See whether this declaration is identical to any existing declarations. |
350 | | // If not, find the right place to insert it. |
351 | 10.1k | for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(), |
352 | 10.1k | IEnd = IDI->decls_end(); |
353 | 40.5k | I != IEnd; ++I30.4k ) { |
354 | | |
355 | 31.5k | switch (compareDeclarations(*I, D)) { |
356 | 30.4k | case DMK_Different: |
357 | 30.4k | break; |
358 | | |
359 | 1.09k | case DMK_Ignore: |
360 | 1.09k | return false; |
361 | | |
362 | 4 | case DMK_Replace: |
363 | 4 | *I = D; |
364 | 4 | return true; |
365 | 31.5k | } |
366 | | |
367 | 30.4k | if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) { |
368 | | // We've found a declaration that is not visible from the translation |
369 | | // unit (it's in an inner scope). Insert our declaration here. |
370 | 0 | IDI->InsertDecl(I, D); |
371 | 0 | return true; |
372 | 0 | } |
373 | 30.4k | } |
374 | | |
375 | | // Add the declaration to the end. |
376 | 9.02k | IDI->AddDecl(D); |
377 | 9.02k | return true; |
378 | 10.1k | } |
379 | | |
380 | 263M | void IdentifierResolver::readingIdentifier(IdentifierInfo &II) { |
381 | 263M | if (II.isOutOfDate()) |
382 | 1.54M | PP.getExternalSource()->updateOutOfDateIdentifier(II); |
383 | 263M | } |
384 | | |
385 | 93.4M | void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) { |
386 | 93.4M | if (II.isOutOfDate()) |
387 | 10 | PP.getExternalSource()->updateOutOfDateIdentifier(II); |
388 | | |
389 | 93.4M | if (II.isFromAST()) |
390 | 478k | II.setFETokenInfoChangedSinceDeserialization(); |
391 | 93.4M | } |
392 | | |
393 | | //===----------------------------------------------------------------------===// |
394 | | // IdDeclInfoMap Implementation |
395 | | //===----------------------------------------------------------------------===// |
396 | | |
397 | | /// Returns the IdDeclInfo associated to the DeclarationName. |
398 | | /// It creates a new IdDeclInfo if one was not created before for this id. |
399 | | IdentifierResolver::IdDeclInfo & |
400 | 2.33M | IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) { |
401 | 2.33M | void *Ptr = Name.getFETokenInfo(); |
402 | | |
403 | 2.33M | if (Ptr) return *toIdDeclInfo(Ptr)0 ; |
404 | | |
405 | 2.33M | if (CurIndex == POOL_SIZE) { |
406 | 47.1k | CurPool = new IdDeclInfoPool(CurPool); |
407 | 47.1k | CurIndex = 0; |
408 | 47.1k | } |
409 | 2.33M | IdDeclInfo *IDI = &CurPool->Pool[CurIndex]; |
410 | 2.33M | Name.setFETokenInfo(reinterpret_cast<void*>( |
411 | 2.33M | reinterpret_cast<uintptr_t>(IDI) | 0x1) |
412 | 2.33M | ); |
413 | 2.33M | ++CurIndex; |
414 | 2.33M | return *IDI; |
415 | 2.33M | } |
416 | | |
417 | 116M | void IdentifierResolver::iterator::incrementSlowCase() { |
418 | 116M | NamedDecl *D = **this; |
419 | 116M | void *InfoPtr = D->getDeclName().getFETokenInfo(); |
420 | 116M | assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?"); |
421 | 0 | IdDeclInfo *Info = toIdDeclInfo(InfoPtr); |
422 | | |
423 | 116M | BaseIter I = getIterator(); |
424 | 116M | if (I != Info->decls_begin()) |
425 | 97.5M | *this = iterator(I-1); |
426 | 19.4M | else // No more decls. |
427 | 19.4M | *this = iterator(); |
428 | 116M | } |