Coverage Report

Created: 2022-07-16 07:03

/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
}