Coverage Report

Created: 2020-02-18 08:44

/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
29.3k
    IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {}
47
  };
48
49
  IdDeclInfoPool *CurPool = nullptr;
50
  unsigned int CurIndex = POOL_SIZE;
51
52
public:
53
63.7k
  IdDeclInfoMap() = default;
54
55
58.3k
  ~IdDeclInfoMap() {
56
58.3k
    IdDeclInfoPool *Cur = CurPool;
57
84.7k
    while (IdDeclInfoPool *P = Cur) {
58
26.4k
      Cur = Cur->Next;
59
26.4k
      delete P;
60
26.4k
    }
61
58.3k
  }
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.44M
void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) {
75
4.51M
  for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); 
--I2.07M
) {
76
4.51M
    if (D == *(I-1)) {
77
2.44M
      Decls.erase(I-1);
78
2.44M
      return;
79
2.44M
    }
80
4.51M
  }
81
2.44M
82
2.44M
  
llvm_unreachable0
("Didn't find this decl on its identifier's chain!");
83
2.44M
}
84
85
//===----------------------------------------------------------------------===//
86
// IdentifierResolver Implementation
87
//===----------------------------------------------------------------------===//
88
89
IdentifierResolver::IdentifierResolver(Preprocessor &PP)
90
63.7k
    : LangOpt(PP.getLangOpts()), PP(PP), IdDeclInfos(new IdDeclInfoMap) {}
91
92
58.3k
IdentifierResolver::~IdentifierResolver() {
93
58.3k
  delete IdDeclInfos;
94
58.3k
}
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
12.3M
                                       bool AllowInlineNamespace) const {
101
12.3M
  Ctx = Ctx->getRedeclContext();
102
12.3M
103
12.3M
  if (Ctx->isFunctionOrMethod() || 
(12.2M
S12.2M
&&
S->isFunctionPrototypeScope()12.2M
)) {
104
36.7k
    // Ignore the scopes associated within transparent declaration contexts.
105
36.7k
    while (S->getEntity() && 
S->getEntity()->isTransparentContext()16.4k
)
106
0
      S = S->getParent();
107
36.7k
108
36.7k
    if (S->isDeclScope(D))
109
1.37k
      return true;
110
35.3k
    if (LangOpt.CPlusPlus) {
111
34.5k
      // C++ 3.3.2p3:
112
34.5k
      // The name declared in a catch exception-declaration is local to the
113
34.5k
      // handler and shall not be redeclared in the outermost block of the
114
34.5k
      // handler.
115
34.5k
      // C++ 3.3.2p4:
116
34.5k
      // Names declared in the for-init-statement, and in the condition of if,
117
34.5k
      // while, for, and switch statements are local to the if, while, for, or
118
34.5k
      // switch statement (including the controlled statement), and shall not be
119
34.5k
      // redeclared in a subsequent condition of that statement nor in the
120
34.5k
      // outermost block (or, for the if statement, any of the outermost blocks)
121
34.5k
      // of the controlled statement.
122
34.5k
      //
123
34.5k
      assert(S->getParent() && "No TUScope?");
124
34.5k
      if (S->getParent()->getFlags() & Scope::ControlScope) {
125
366
        S = S->getParent();
126
366
        if (S->isDeclScope(D))
127
55
          return true;
128
34.4k
      }
129
34.4k
      if (S->getFlags() & Scope::FnTryCatchScope)
130
6
        return S->getParent()->isDeclScope(D);
131
35.2k
    }
132
35.2k
    return false;
133
35.2k
  }
134
12.2M
135
12.2M
  // FIXME: If D is a local extern declaration, this check doesn't make sense;
136
12.2M
  // we should be checking its lexical context instead in that case, because
137
12.2M
  // that is its scope.
138
12.2M
  DeclContext *DCtx = D->getDeclContext()->getRedeclContext();
139
12.2M
  return AllowInlineNamespace ? 
Ctx->InEnclosingNamespaceSetOf(DCtx)889k
140
12.2M
                              : 
Ctx->Equals(DCtx)11.4M
;
141
12.2M
}
142
143
/// AddDecl - Link the decl to its shadowed decl chain.
144
40.1M
void IdentifierResolver::AddDecl(NamedDecl *D) {
145
40.1M
  DeclarationName Name = D->getDeclName();
146
40.1M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
147
39.6M
    updatingIdentifier(*II);
148
40.1M
149
40.1M
  void *Ptr = Name.getFETokenInfo();
150
40.1M
151
40.1M
  if (!Ptr) {
152
37.0M
    Name.setFETokenInfo(D);
153
37.0M
    return;
154
37.0M
  }
155
3.13M
156
3.13M
  IdDeclInfo *IDI;
157
3.13M
158
3.13M
  if (isDeclPtr(Ptr)) {
159
1.11M
    Name.setFETokenInfo(nullptr);
160
1.11M
    IDI = &(*IdDeclInfos)[Name];
161
1.11M
    NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
162
1.11M
    IDI->AddDecl(PrevD);
163
1.11M
  } else
164
2.02M
    IDI = toIdDeclInfo(Ptr);
165
3.13M
166
3.13M
  IDI->AddDecl(D);
167
3.13M
}
168
169
4.01k
void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) {
170
4.01k
  DeclarationName Name = D->getDeclName();
171
4.01k
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
172
4.01k
    updatingIdentifier(*II);
173
4.01k
174
4.01k
  void *Ptr = Name.getFETokenInfo();
175
4.01k
176
4.01k
  if (!Ptr) {
177
3.69k
    AddDecl(D);
178
3.69k
    return;
179
3.69k
  }
180
317
181
317
  if (isDeclPtr(Ptr)) {
182
251
    // We only have a single declaration: insert before or after it,
183
251
    // as appropriate.
184
251
    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
245
    } else {
191
245
      // Add new declaration after the existing declaration.
192
245
      AddDecl(D);
193
245
    }
194
251
195
251
    return;
196
251
  }
197
66
198
66
  // General case: insert the declaration at the appropriate point in the
199
66
  // list, which already has at least two elements.
200
66
  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
201
66
  if (Pos.isIterator()) {
202
34
    IDI->InsertDecl(Pos.getIterator() + 1, D);
203
34
  } else
204
32
    IDI->InsertDecl(IDI->decls_begin(), D);
205
66
}
206
207
/// RemoveDecl - Unlink the decl from its shadowed decl chain.
208
/// The decl must already be part of the decl chain.
209
26.2M
void IdentifierResolver::RemoveDecl(NamedDecl *D) {
210
26.2M
  assert(D && "null param passed");
211
26.2M
  DeclarationName Name = D->getDeclName();
212
26.2M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
213
25.6M
    updatingIdentifier(*II);
214
26.2M
215
26.2M
  void *Ptr = Name.getFETokenInfo();
216
26.2M
217
26.2M
  assert(Ptr && "Didn't find this decl on its identifier's chain!");
218
26.2M
219
26.2M
  if (isDeclPtr(Ptr)) {
220
23.7M
    assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
221
23.7M
    Name.setFETokenInfo(nullptr);
222
23.7M
    return;
223
23.7M
  }
224
2.44M
225
2.44M
  return toIdDeclInfo(Ptr)->RemoveDecl(D);
226
2.44M
}
227
228
/// begin - Returns an iterator for decls with name 'Name'.
229
IdentifierResolver::iterator
230
135M
IdentifierResolver::begin(DeclarationName Name) {
231
135M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
232
132M
    readingIdentifier(*II);
233
135M
234
135M
  void *Ptr = Name.getFETokenInfo();
235
135M
  if (!Ptr) 
return end()80.8M
;
236
55.0M
237
55.0M
  if (isDeclPtr(Ptr))
238
44.8M
    return iterator(static_cast<NamedDecl*>(Ptr));
239
10.2M
240
10.2M
  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
241
10.2M
242
10.2M
  IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
243
10.2M
  if (I != IDI->decls_begin())
244
7.55M
    return iterator(I-1);
245
2.70M
  // No decls found.
246
2.70M
  return end();
247
2.70M
}
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
39.5k
static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
263
39.5k
  // If the declarations are identical, ignore the new one.
264
39.5k
  if (Existing == New)
265
15.0k
    return DMK_Ignore;
266
24.4k
267
24.4k
  // If the declarations have different kinds, they're obviously different.
268
24.4k
  if (Existing->getKind() != New->getKind())
269
2.30k
    return DMK_Different;
270
22.1k
271
22.1k
  // If the declarations are redeclarations of each other, keep the newest one.
272
22.1k
  if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
273
846
    // If we're adding an imported declaration, don't replace another imported
274
846
    // declaration.
275
846
    if (Existing->isFromASTFile() && 
New->isFromASTFile()582
)
276
582
      return DMK_Different;
277
264
278
264
    // If either of these is the most recent declaration, use it.
279
264
    Decl *MostRecent = Existing->getMostRecentDecl();
280
264
    if (Existing == MostRecent)
281
174
      return DMK_Ignore;
282
90
283
90
    if (New == MostRecent)
284
84
      return DMK_Replace;
285
6
286
6
    // If the existing declaration is somewhere in the previous declaration
287
6
    // chain of the new declaration, then prefer the new declaration.
288
337
    
for (auto RD : New->redecls())6
{
289
337
      if (RD == Existing)
290
1
        return DMK_Replace;
291
336
292
336
      if (RD->isCanonicalDecl())
293
5
        break;
294
336
    }
295
6
296
6
    
return DMK_Ignore5
;
297
21.3k
  }
298
21.3k
299
21.3k
  return DMK_Different;
300
21.3k
}
301
302
208k
bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){
303
208k
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
304
200k
    readingIdentifier(*II);
305
208k
306
208k
  void *Ptr = Name.getFETokenInfo();
307
208k
308
208k
  if (!Ptr) {
309
185k
    Name.setFETokenInfo(D);
310
185k
    return true;
311
185k
  }
312
23.4k
313
23.4k
  IdDeclInfo *IDI;
314
23.4k
315
23.4k
  if (isDeclPtr(Ptr)) {
316
16.9k
    NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
317
16.9k
318
16.9k
    switch (compareDeclarations(PrevD, D)) {
319
3.08k
    case DMK_Different:
320
3.08k
      break;
321
0
322
13.8k
    case DMK_Ignore:
323
13.8k
      return false;
324
0
325
81
    case DMK_Replace:
326
81
      Name.setFETokenInfo(D);
327
81
      return true;
328
3.08k
    }
329
3.08k
330
3.08k
    Name.setFETokenInfo(nullptr);
331
3.08k
    IDI = &(*IdDeclInfos)[Name];
332
3.08k
333
3.08k
    // If the existing declaration is not visible in translation unit scope,
334
3.08k
    // then add the new top-level declaration first.
335
3.08k
    if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
336
0
      IDI->AddDecl(D);
337
0
      IDI->AddDecl(PrevD);
338
3.08k
    } else {
339
3.08k
      IDI->AddDecl(PrevD);
340
3.08k
      IDI->AddDecl(D);
341
3.08k
    }
342
3.08k
    return true;
343
3.08k
  }
344
6.49k
345
6.49k
  IDI = toIdDeclInfo(Ptr);
346
6.49k
347
6.49k
  // See whether this declaration is identical to any existing declarations.
348
6.49k
  // If not, find the right place to insert it.
349
6.49k
  for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
350
6.49k
                                  IEnd = IDI->decls_end();
351
27.6k
       I != IEnd; 
++I21.1k
) {
352
22.5k
353
22.5k
    switch (compareDeclarations(*I, D)) {
354
21.1k
    case DMK_Different:
355
21.1k
      break;
356
0
357
1.44k
    case DMK_Ignore:
358
1.44k
      return false;
359
0
360
4
    case DMK_Replace:
361
4
      *I = D;
362
4
      return true;
363
21.1k
    }
364
21.1k
365
21.1k
    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
21.1k
  }
372
6.49k
373
6.49k
  // Add the declaration to the end.
374
6.49k
  IDI->AddDecl(D);
375
5.05k
  return true;
376
6.49k
}
377
378
133M
void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
379
133M
  if (II.isOutOfDate())
380
1.25M
    PP.getExternalSource()->updateOutOfDateIdentifier(II);
381
133M
}
382
383
65.2M
void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
384
65.2M
  if (II.isOutOfDate())
385
619
    PP.getExternalSource()->updateOutOfDateIdentifier(II);
386
65.2M
387
65.2M
  if (II.isFromAST())
388
621k
    II.setFETokenInfoChangedSinceDeserialization();
389
65.2M
}
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
1.11M
IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) {
399
1.11M
  void *Ptr = Name.getFETokenInfo();
400
1.11M
401
1.11M
  if (Ptr) 
return *toIdDeclInfo(Ptr)0
;
402
1.11M
403
1.11M
  if (CurIndex == POOL_SIZE) {
404
29.3k
    CurPool = new IdDeclInfoPool(CurPool);
405
29.3k
    CurIndex = 0;
406
29.3k
  }
407
1.11M
  IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
408
1.11M
  Name.setFETokenInfo(reinterpret_cast<void*>(
409
1.11M
                              reinterpret_cast<uintptr_t>(IDI) | 0x1)
410
1.11M
                                                                     );
411
1.11M
  ++CurIndex;
412
1.11M
  return *IDI;
413
1.11M
}
414
415
27.5M
void IdentifierResolver::iterator::incrementSlowCase() {
416
27.5M
  NamedDecl *D = **this;
417
27.5M
  void *InfoPtr = D->getDeclName().getFETokenInfo();
418
27.5M
  assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
419
27.5M
  IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
420
27.5M
421
27.5M
  BaseIter I = getIterator();
422
27.5M
  if (I != Info->decls_begin())
423
20.9M
    *this = iterator(I-1);
424
6.50M
  else // No more decls.
425
6.50M
    *this = iterator();
426
27.5M
}