/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/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 | 20.3k | IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {} |
47 | | }; |
48 | | |
49 | | IdDeclInfoPool *CurPool = nullptr; |
50 | | unsigned int CurIndex = POOL_SIZE; |
51 | | |
52 | | public: |
53 | 46.9k | IdDeclInfoMap() = default; |
54 | | |
55 | 38.2k | ~IdDeclInfoMap() { |
56 | 38.2k | IdDeclInfoPool *Cur = CurPool; |
57 | 53.7k | while (IdDeclInfoPool *P = Cur) { |
58 | 15.4k | Cur = Cur->Next; |
59 | 15.4k | delete P; |
60 | 15.4k | } |
61 | 38.2k | } |
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.07M | void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) { |
75 | 5.25M | for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I2.17M ) { |
76 | 5.25M | if (D == *(I-1)) { |
77 | 3.07M | Decls.erase(I-1); |
78 | 3.07M | return; |
79 | 3.07M | } |
80 | 5.25M | } |
81 | 3.07M | |
82 | 3.07M | llvm_unreachable0 ("Didn't find this decl on its identifier's chain!"); |
83 | 3.07M | } |
84 | | |
85 | | //===----------------------------------------------------------------------===// |
86 | | // IdentifierResolver Implementation |
87 | | //===----------------------------------------------------------------------===// |
88 | | |
89 | | IdentifierResolver::IdentifierResolver(Preprocessor &PP) |
90 | 46.9k | : LangOpt(PP.getLangOpts()), PP(PP), IdDeclInfos(new IdDeclInfoMap) {} |
91 | | |
92 | 38.2k | IdentifierResolver::~IdentifierResolver() { |
93 | 38.2k | delete IdDeclInfos; |
94 | 38.2k | } |
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 | 11.4M | bool AllowInlineNamespace) const { |
101 | 11.4M | Ctx = Ctx->getRedeclContext(); |
102 | 11.4M | |
103 | 11.4M | if (Ctx->isFunctionOrMethod() || (11.4M S11.4M && S->isFunctionPrototypeScope()11.4M )) { |
104 | 31.4k | // Ignore the scopes associated within transparent declaration contexts. |
105 | 31.4k | while (S->getEntity() && S->getEntity()->isTransparentContext()11.0k ) |
106 | 0 | S = S->getParent(); |
107 | 31.4k | |
108 | 31.4k | if (S->isDeclScope(D)) |
109 | 1.24k | return true; |
110 | 30.1k | if (LangOpt.CPlusPlus) { |
111 | 28.7k | // C++ 3.3.2p3: |
112 | 28.7k | // The name declared in a catch exception-declaration is local to the |
113 | 28.7k | // handler and shall not be redeclared in the outermost block of the |
114 | 28.7k | // handler. |
115 | 28.7k | // C++ 3.3.2p4: |
116 | 28.7k | // Names declared in the for-init-statement, and in the condition of if, |
117 | 28.7k | // while, for, and switch statements are local to the if, while, for, or |
118 | 28.7k | // switch statement (including the controlled statement), and shall not be |
119 | 28.7k | // redeclared in a subsequent condition of that statement nor in the |
120 | 28.7k | // outermost block (or, for the if statement, any of the outermost blocks) |
121 | 28.7k | // of the controlled statement. |
122 | 28.7k | // |
123 | 28.7k | assert(S->getParent() && "No TUScope?"); |
124 | 28.7k | if (S->getParent()->getFlags() & Scope::ControlScope) { |
125 | 5.71k | S = S->getParent(); |
126 | 5.71k | if (S->isDeclScope(D)) |
127 | 55 | return true; |
128 | 28.7k | } |
129 | 28.7k | if (S->getFlags() & Scope::FnTryCatchScope) |
130 | 7 | return S->getParent()->isDeclScope(D); |
131 | 30.1k | } |
132 | 30.1k | return false; |
133 | 30.1k | } |
134 | 11.4M | |
135 | 11.4M | // FIXME: If D is a local extern declaration, this check doesn't make sense; |
136 | 11.4M | // we should be checking its lexical context instead in that case, because |
137 | 11.4M | // that is its scope. |
138 | 11.4M | DeclContext *DCtx = D->getDeclContext()->getRedeclContext(); |
139 | 11.4M | return AllowInlineNamespace ? Ctx->InEnclosingNamespaceSetOf(DCtx)1.07M |
140 | 11.4M | : Ctx->Equals(DCtx)10.3M ; |
141 | 11.4M | } |
142 | | |
143 | | /// AddDecl - Link the decl to its shadowed decl chain. |
144 | 30.9M | void IdentifierResolver::AddDecl(NamedDecl *D) { |
145 | 30.9M | DeclarationName Name = D->getDeclName(); |
146 | 30.9M | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
147 | 30.1M | updatingIdentifier(*II); |
148 | 30.9M | |
149 | 30.9M | void *Ptr = Name.getFETokenInfo(); |
150 | 30.9M | |
151 | 30.9M | if (!Ptr) { |
152 | 27.9M | Name.setFETokenInfo(D); |
153 | 27.9M | return; |
154 | 27.9M | } |
155 | 2.96M | |
156 | 2.96M | IdDeclInfo *IDI; |
157 | 2.96M | |
158 | 2.96M | if (isDeclPtr(Ptr)) { |
159 | 983k | Name.setFETokenInfo(nullptr); |
160 | 983k | IDI = &(*IdDeclInfos)[Name]; |
161 | 983k | NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); |
162 | 983k | IDI->AddDecl(PrevD); |
163 | 983k | } else |
164 | 1.98M | IDI = toIdDeclInfo(Ptr); |
165 | 2.96M | |
166 | 2.96M | IDI->AddDecl(D); |
167 | 2.96M | } |
168 | | |
169 | 4.06k | void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) { |
170 | 4.06k | DeclarationName Name = D->getDeclName(); |
171 | 4.06k | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
172 | 4.06k | updatingIdentifier(*II); |
173 | 4.06k | |
174 | 4.06k | void *Ptr = Name.getFETokenInfo(); |
175 | 4.06k | |
176 | 4.06k | if (!Ptr) { |
177 | 3.80k | AddDecl(D); |
178 | 3.80k | return; |
179 | 3.80k | } |
180 | 252 | |
181 | 252 | if (isDeclPtr(Ptr)) { |
182 | 180 | // We only have a single declaration: insert before or after it, |
183 | 180 | // as appropriate. |
184 | 180 | if (Pos == iterator()) { |
185 | 6 | // Add the new declaration before the existing declaration. |
186 | 6 | NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); |
187 | 6 | RemoveDecl(PrevD); |
188 | 6 | AddDecl(D); |
189 | 6 | AddDecl(PrevD); |
190 | 174 | } else { |
191 | 174 | // Add new declaration after the existing declaration. |
192 | 174 | AddDecl(D); |
193 | 174 | } |
194 | 180 | |
195 | 180 | return; |
196 | 180 | } |
197 | 72 | |
198 | 72 | // General case: insert the declaration at the appropriate point in the |
199 | 72 | // list, which already has at least two elements. |
200 | 72 | IdDeclInfo *IDI = toIdDeclInfo(Ptr); |
201 | 72 | if (Pos.isIterator()) { |
202 | 40 | IDI->InsertDecl(Pos.getIterator() + 1, D); |
203 | 40 | } else |
204 | 32 | IDI->InsertDecl(IDI->decls_begin(), D); |
205 | 72 | } |
206 | | |
207 | | /// RemoveDecl - Unlink the decl from its shadowed decl chain. |
208 | | /// The decl must already be part of the decl chain. |
209 | 25.6M | void IdentifierResolver::RemoveDecl(NamedDecl *D) { |
210 | 25.6M | assert(D && "null param passed"); |
211 | 25.6M | DeclarationName Name = D->getDeclName(); |
212 | 25.6M | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
213 | 24.8M | updatingIdentifier(*II); |
214 | 25.6M | |
215 | 25.6M | void *Ptr = Name.getFETokenInfo(); |
216 | 25.6M | |
217 | 25.6M | assert(Ptr && "Didn't find this decl on its identifier's chain!"); |
218 | 25.6M | |
219 | 25.6M | if (isDeclPtr(Ptr)) { |
220 | 22.5M | assert(D == Ptr && "Didn't find this decl on its identifier's chain!"); |
221 | 22.5M | Name.setFETokenInfo(nullptr); |
222 | 22.5M | return; |
223 | 22.5M | } |
224 | 3.07M | |
225 | 3.07M | return toIdDeclInfo(Ptr)->RemoveDecl(D); |
226 | 3.07M | } |
227 | | |
228 | | /// begin - Returns an iterator for decls with name 'Name'. |
229 | | IdentifierResolver::iterator |
230 | 111M | IdentifierResolver::begin(DeclarationName Name) { |
231 | 111M | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
232 | 107M | readingIdentifier(*II); |
233 | 111M | |
234 | 111M | void *Ptr = Name.getFETokenInfo(); |
235 | 111M | if (!Ptr) return end()63.1M ; |
236 | 48.4M | |
237 | 48.4M | if (isDeclPtr(Ptr)) |
238 | 37.9M | return iterator(static_cast<NamedDecl*>(Ptr)); |
239 | 10.5M | |
240 | 10.5M | IdDeclInfo *IDI = toIdDeclInfo(Ptr); |
241 | 10.5M | |
242 | 10.5M | IdDeclInfo::DeclsTy::iterator I = IDI->decls_end(); |
243 | 10.5M | if (I != IDI->decls_begin()) |
244 | 7.14M | return iterator(I-1); |
245 | 3.35M | // No decls found. |
246 | 3.35M | return end(); |
247 | 3.35M | } |
248 | | |
249 | | namespace { |
250 | | |
251 | | enum DeclMatchKind { |
252 | | DMK_Different, |
253 | | DMK_Replace, |
254 | | DMK_Ignore |
255 | | }; |
256 | | |
257 | | } // namespace |
258 | | |
259 | | /// Compare two declarations to see whether they are different or, |
260 | | /// if they are the same, whether the new declaration should replace the |
261 | | /// existing declaration. |
262 | 16.7k | static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) { |
263 | 16.7k | // If the declarations are identical, ignore the new one. |
264 | 16.7k | if (Existing == New) |
265 | 2.06k | return DMK_Ignore; |
266 | 14.7k | |
267 | 14.7k | // If the declarations have different kinds, they're obviously different. |
268 | 14.7k | if (Existing->getKind() != New->getKind()) |
269 | 89 | return DMK_Different; |
270 | 14.6k | |
271 | 14.6k | // If the declarations are redeclarations of each other, keep the newest one. |
272 | 14.6k | if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) { |
273 | 81 | // If we're adding an imported declaration, don't replace another imported |
274 | 81 | // declaration. |
275 | 81 | if (Existing->isFromASTFile() && New->isFromASTFile()43 ) |
276 | 43 | return DMK_Different; |
277 | 38 | |
278 | 38 | // If either of these is the most recent declaration, use it. |
279 | 38 | Decl *MostRecent = Existing->getMostRecentDecl(); |
280 | 38 | if (Existing == MostRecent) |
281 | 1 | return DMK_Ignore; |
282 | 37 | |
283 | 37 | if (New == MostRecent) |
284 | 36 | return DMK_Replace; |
285 | 1 | |
286 | 1 | // If the existing declaration is somewhere in the previous declaration |
287 | 1 | // chain of the new declaration, then prefer the new declaration. |
288 | 2 | for (auto RD : New->redecls())1 { |
289 | 2 | if (RD == Existing) |
290 | 1 | return DMK_Replace; |
291 | 1 | |
292 | 1 | if (RD->isCanonicalDecl()) |
293 | 0 | break; |
294 | 1 | } |
295 | 1 | |
296 | 1 | return DMK_Ignore0 ; |
297 | 14.5k | } |
298 | 14.5k | |
299 | 14.5k | return DMK_Different; |
300 | 14.5k | } |
301 | | |
302 | 50.5k | bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){ |
303 | 50.5k | if (IdentifierInfo *II = Name.getAsIdentifierInfo()) |
304 | 36.9k | readingIdentifier(*II); |
305 | 50.5k | |
306 | 50.5k | void *Ptr = Name.getFETokenInfo(); |
307 | 50.5k | |
308 | 50.5k | if (!Ptr) { |
309 | 46.4k | Name.setFETokenInfo(D); |
310 | 46.4k | return true; |
311 | 46.4k | } |
312 | 4.06k | |
313 | 4.06k | IdDeclInfo *IDI; |
314 | 4.06k | |
315 | 4.06k | if (isDeclPtr(Ptr)) { |
316 | 3.06k | NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); |
317 | 3.06k | |
318 | 3.06k | switch (compareDeclarations(PrevD, D)) { |
319 | 3.06k | case DMK_Different: |
320 | 967 | break; |
321 | 3.06k | |
322 | 3.06k | case DMK_Ignore: |
323 | 2.05k | return false; |
324 | 3.06k | |
325 | 3.06k | case DMK_Replace: |
326 | 35 | Name.setFETokenInfo(D); |
327 | 35 | return true; |
328 | 967 | } |
329 | 967 | |
330 | 967 | Name.setFETokenInfo(nullptr); |
331 | 967 | IDI = &(*IdDeclInfos)[Name]; |
332 | 967 | |
333 | 967 | // If the existing declaration is not visible in translation unit scope, |
334 | 967 | // then add the new top-level declaration first. |
335 | 967 | if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) { |
336 | 0 | IDI->AddDecl(D); |
337 | 0 | IDI->AddDecl(PrevD); |
338 | 967 | } else { |
339 | 967 | IDI->AddDecl(PrevD); |
340 | 967 | IDI->AddDecl(D); |
341 | 967 | } |
342 | 967 | return true; |
343 | 967 | } |
344 | 1.00k | |
345 | 1.00k | IDI = toIdDeclInfo(Ptr); |
346 | 1.00k | |
347 | 1.00k | // See whether this declaration is identical to any existing declarations. |
348 | 1.00k | // If not, find the right place to insert it. |
349 | 1.00k | for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(), |
350 | 1.00k | IEnd = IDI->decls_end(); |
351 | 14.7k | I != IEnd; ++I13.7k ) { |
352 | 13.7k | |
353 | 13.7k | switch (compareDeclarations(*I, D)) { |
354 | 13.7k | case DMK_Different: |
355 | 13.7k | break; |
356 | 13.7k | |
357 | 13.7k | case DMK_Ignore: |
358 | 8 | return false; |
359 | 13.7k | |
360 | 13.7k | case DMK_Replace: |
361 | 2 | *I = D; |
362 | 2 | return true; |
363 | 13.7k | } |
364 | 13.7k | |
365 | 13.7k | if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) { |
366 | 0 | // We've found a declaration that is not visible from the translation |
367 | 0 | // unit (it's in an inner scope). Insert our declaration here. |
368 | 0 | IDI->InsertDecl(I, D); |
369 | 0 | return true; |
370 | 0 | } |
371 | 13.7k | } |
372 | 1.00k | |
373 | 1.00k | // Add the declaration to the end. |
374 | 1.00k | IDI->AddDecl(D); |
375 | 999 | return true; |
376 | 1.00k | } |
377 | | |
378 | 107M | void IdentifierResolver::readingIdentifier(IdentifierInfo &II) { |
379 | 107M | if (II.isOutOfDate()) |
380 | 740k | PP.getExternalSource()->updateOutOfDateIdentifier(II); |
381 | 107M | } |
382 | | |
383 | 54.9M | void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) { |
384 | 54.9M | if (II.isOutOfDate()) |
385 | 619 | PP.getExternalSource()->updateOutOfDateIdentifier(II); |
386 | 54.9M | |
387 | 54.9M | if (II.isFromAST()) |
388 | 11.9k | II.setFETokenInfoChangedSinceDeserialization(); |
389 | 54.9M | } |
390 | | |
391 | | //===----------------------------------------------------------------------===// |
392 | | // IdDeclInfoMap Implementation |
393 | | //===----------------------------------------------------------------------===// |
394 | | |
395 | | /// Returns the IdDeclInfo associated to the DeclarationName. |
396 | | /// It creates a new IdDeclInfo if one was not created before for this id. |
397 | | IdentifierResolver::IdDeclInfo & |
398 | 984k | IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) { |
399 | 984k | void *Ptr = Name.getFETokenInfo(); |
400 | 984k | |
401 | 984k | if (Ptr) return *toIdDeclInfo(Ptr)0 ; |
402 | 984k | |
403 | 984k | if (CurIndex == POOL_SIZE) { |
404 | 20.3k | CurPool = new IdDeclInfoPool(CurPool); |
405 | 20.3k | CurIndex = 0; |
406 | 20.3k | } |
407 | 984k | IdDeclInfo *IDI = &CurPool->Pool[CurIndex]; |
408 | 984k | Name.setFETokenInfo(reinterpret_cast<void*>( |
409 | 984k | reinterpret_cast<uintptr_t>(IDI) | 0x1) |
410 | 984k | ); |
411 | 984k | ++CurIndex; |
412 | 984k | return *IDI; |
413 | 984k | } |
414 | | |
415 | 23.9M | void IdentifierResolver::iterator::incrementSlowCase() { |
416 | 23.9M | NamedDecl *D = **this; |
417 | 23.9M | void *InfoPtr = D->getDeclName().getFETokenInfo(); |
418 | 23.9M | assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?"); |
419 | 23.9M | IdDeclInfo *Info = toIdDeclInfo(InfoPtr); |
420 | 23.9M | |
421 | 23.9M | BaseIter I = getIterator(); |
422 | 23.9M | if (I != Info->decls_begin()) |
423 | 18.1M | *this = iterator(I-1); |
424 | 5.80M | else // No more decls. |
425 | 5.80M | *this = iterator(); |
426 | 23.9M | } |