Coverage Report

Created: 2022-05-17 06:19

/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
46.1k
    IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {}
47
  };
48
49
  IdDeclInfoPool *CurPool = nullptr;
50
  unsigned int CurIndex = POOL_SIZE;
51
52
public:
53
100k
  IdDeclInfoMap() = default;
54
55
95.0k
  ~IdDeclInfoMap() {
56
95.0k
    IdDeclInfoPool *Cur = CurPool;
57
137k
    while (IdDeclInfoPool *P = Cur) {
58
42.8k
      Cur = Cur->Next;
59
42.8k
      delete P;
60
42.8k
    }
61
95.0k
  }
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
2.76M
void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) {
75
5.06M
  for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); 
--I2.29M
) {
76
5.06M
    if (D == *(I-1)) {
77
2.76M
      Decls.erase(I-1);
78
2.76M
      return;
79
2.76M
    }
80
5.06M
  }
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
100k
    : LangOpt(PP.getLangOpts()), PP(PP), IdDeclInfos(new IdDeclInfoMap) {}
91
92
95.0k
IdentifierResolver::~IdentifierResolver() {
93
95.0k
  delete IdDeclInfos;
94
95.0k
}
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
56.9M
                                       bool AllowInlineNamespace) const {
101
56.9M
  Ctx = Ctx->getRedeclContext();
102
103
56.9M
  if (Ctx->isFunctionOrMethod() || 
(56.8M
S56.8M
&&
S->isFunctionPrototypeScope()56.6M
)) {
104
    // Ignore the scopes associated within transparent declaration contexts.
105
50.9k
    while (S->getEntity() && 
S->getEntity()->isTransparentContext()20.1k
)
106
0
      S = S->getParent();
107
108
50.9k
    if (S->isDeclScope(D))
109
1.65k
      return true;
110
49.3k
    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
48.2k
      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
48.2k
      if (S->getParent()->isControlScope() && 
!S->isFunctionScope()301
) {
127
295
        S = S->getParent();
128
295
        if (S->isDeclScope(D))
129
55
          return true;
130
295
      }
131
48.2k
      if (S->isFnTryCatchScope())
132
6
        return S->getParent()->isDeclScope(D);
133
48.2k
    }
134
49.2k
    return false;
135
49.3k
  }
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
56.8M
  DeclContext *DCtx = D->getDeclContext()->getRedeclContext();
141
56.8M
  return AllowInlineNamespace ? 
Ctx->InEnclosingNamespaceSetOf(DCtx)778k
142
56.8M
                              : 
Ctx->Equals(DCtx)56.0M
;
143
56.9M
}
144
145
/// AddDecl - Link the decl to its shadowed decl chain.
146
59.2M
void IdentifierResolver::AddDecl(NamedDecl *D) {
147
59.2M
  DeclarationName Name = D->getDeclName();
148
59.2M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
149
58.6M
    updatingIdentifier(*II);
150
151
59.2M
  void *Ptr = Name.getFETokenInfo();
152
153
59.2M
  if (!Ptr) {
154
48.7M
    Name.setFETokenInfo(D);
155
48.7M
    return;
156
48.7M
  }
157
158
10.4M
  IdDeclInfo *IDI;
159
160
10.4M
  if (isDeclPtr(Ptr)) {
161
2.20M
    Name.setFETokenInfo(nullptr);
162
2.20M
    IDI = &(*IdDeclInfos)[Name];
163
2.20M
    NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
164
2.20M
    IDI->AddDecl(PrevD);
165
2.20M
  } else
166
8.27M
    IDI = toIdDeclInfo(Ptr);
167
168
10.4M
  IDI->AddDecl(D);
169
10.4M
}
170
171
2.00k
void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) {
172
2.00k
  DeclarationName Name = D->getDeclName();
173
2.00k
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
174
2.00k
    updatingIdentifier(*II);
175
176
2.00k
  void *Ptr = Name.getFETokenInfo();
177
178
2.00k
  if (!Ptr) {
179
1.66k
    AddDecl(D);
180
1.66k
    return;
181
1.66k
  }
182
183
338
  if (isDeclPtr(Ptr)) {
184
    // We only have a single declaration: insert before or after it,
185
    // as appropriate.
186
250
    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
242
    } else {
193
      // Add new declaration after the existing declaration.
194
242
      AddDecl(D);
195
242
    }
196
197
250
    return;
198
250
  }
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
28.0M
void IdentifierResolver::RemoveDecl(NamedDecl *D) {
212
28.0M
  assert(D && "null param passed");
213
0
  DeclarationName Name = D->getDeclName();
214
28.0M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
215
27.4M
    updatingIdentifier(*II);
216
217
28.0M
  void *Ptr = Name.getFETokenInfo();
218
219
28.0M
  assert(Ptr && "Didn't find this decl on its identifier's chain!");
220
221
28.0M
  if (isDeclPtr(Ptr)) {
222
25.2M
    assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
223
0
    Name.setFETokenInfo(nullptr);
224
25.2M
    return;
225
25.2M
  }
226
227
2.76M
  return toIdDeclInfo(Ptr)->RemoveDecl(D);
228
28.0M
}
229
230
/// begin - Returns an iterator for decls with name 'Name'.
231
IdentifierResolver::iterator
232
253M
IdentifierResolver::begin(DeclarationName Name) {
233
253M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
234
250M
    readingIdentifier(*II);
235
236
253M
  void *Ptr = Name.getFETokenInfo();
237
253M
  if (!Ptr) 
return end()115M
;
238
239
137M
  if (isDeclPtr(Ptr))
240
115M
    return iterator(static_cast<NamedDecl*>(Ptr));
241
242
22.4M
  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
243
244
22.4M
  IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
245
22.4M
  if (I != IDI->decls_begin())
246
19.7M
    return iterator(I-1);
247
  // No decls found.
248
2.65M
  return end();
249
22.4M
}
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
39.7k
static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
265
  // If the declarations are identical, ignore the new one.
266
39.7k
  if (Existing == New)
267
12.8k
    return DMK_Ignore;
268
269
  // If the declarations have different kinds, they're obviously different.
270
26.8k
  if (Existing->getKind() != New->getKind())
271
2.01k
    return DMK_Different;
272
273
  // If the declarations are redeclarations of each other, keep the newest one.
274
24.8k
  if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
275
    // If we're adding an imported declaration, don't replace another imported
276
    // declaration.
277
739
    if (Existing->isFromASTFile() && 
New->isFromASTFile()501
)
278
501
      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
24.1k
  return DMK_Different;
302
24.8k
}
303
304
186k
bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){
305
186k
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
306
175k
    readingIdentifier(*II);
307
308
186k
  void *Ptr = Name.getFETokenInfo();
309
310
186k
  if (!Ptr) {
311
164k
    Name.setFETokenInfo(D);
312
164k
    return true;
313
164k
  }
314
315
21.8k
  IdDeclInfo *IDI;
316
317
21.8k
  if (isDeclPtr(Ptr)) {
318
15.5k
    NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
319
320
15.5k
    switch (compareDeclarations(PrevD, D)) {
321
3.65k
    case DMK_Different:
322
3.65k
      break;
323
324
11.7k
    case DMK_Ignore:
325
11.7k
      return false;
326
327
84
    case DMK_Replace:
328
84
      Name.setFETokenInfo(D);
329
84
      return true;
330
15.5k
    }
331
332
3.65k
    Name.setFETokenInfo(nullptr);
333
3.65k
    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
3.65k
    if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
338
0
      IDI->AddDecl(D);
339
0
      IDI->AddDecl(PrevD);
340
3.65k
    } else {
341
3.65k
      IDI->AddDecl(PrevD);
342
3.65k
      IDI->AddDecl(D);
343
3.65k
    }
344
3.65k
    return true;
345
15.5k
  }
346
347
6.32k
  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
6.32k
  for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
352
6.32k
                                  IEnd = IDI->decls_end();
353
29.3k
       I != IEnd; 
++I22.9k
) {
354
355
24.2k
    switch (compareDeclarations(*I, D)) {
356
22.9k
    case DMK_Different:
357
22.9k
      break;
358
359
1.20k
    case DMK_Ignore:
360
1.20k
      return false;
361
362
4
    case DMK_Replace:
363
4
      *I = D;
364
4
      return true;
365
24.2k
    }
366
367
22.9k
    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
22.9k
  }
374
375
  // Add the declaration to the end.
376
5.11k
  IDI->AddDecl(D);
377
5.11k
  return true;
378
6.32k
}
379
380
250M
void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
381
250M
  if (II.isOutOfDate())
382
1.50M
    PP.getExternalSource()->updateOutOfDateIdentifier(II);
383
250M
}
384
385
86.0M
void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
386
86.0M
  if (II.isOutOfDate())
387
10
    PP.getExternalSource()->updateOutOfDateIdentifier(II);
388
389
86.0M
  if (II.isFromAST())
390
467k
    II.setFETokenInfoChangedSinceDeserialization();
391
86.0M
}
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.20M
IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) {
401
2.20M
  void *Ptr = Name.getFETokenInfo();
402
403
2.20M
  if (Ptr) 
return *toIdDeclInfo(Ptr)0
;
404
405
2.20M
  if (CurIndex == POOL_SIZE) {
406
46.1k
    CurPool = new IdDeclInfoPool(CurPool);
407
46.1k
    CurIndex = 0;
408
46.1k
  }
409
2.20M
  IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
410
2.20M
  Name.setFETokenInfo(reinterpret_cast<void*>(
411
2.20M
                              reinterpret_cast<uintptr_t>(IDI) | 0x1)
412
2.20M
                                                                     );
413
2.20M
  ++CurIndex;
414
2.20M
  return *IDI;
415
2.20M
}
416
417
114M
void IdentifierResolver::iterator::incrementSlowCase() {
418
114M
  NamedDecl *D = **this;
419
114M
  void *InfoPtr = D->getDeclName().getFETokenInfo();
420
114M
  assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
421
0
  IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
422
423
114M
  BaseIter I = getIterator();
424
114M
  if (I != Info->decls_begin())
425
96.2M
    *this = iterator(I-1);
426
18.5M
  else // No more decls.
427
18.5M
    *this = iterator();
428
114M
}