Coverage Report

Created: 2020-09-22 08:39

/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
39.4k
    IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {}
47
  };
48
49
  IdDeclInfoPool *CurPool = nullptr;
50
  unsigned int CurIndex = POOL_SIZE;
51
52
public:
53
88.8k
  IdDeclInfoMap() = default;
54
55
83.0k
  ~IdDeclInfoMap() {
56
83.0k
    IdDeclInfoPool *Cur = CurPool;
57
119k
    while (IdDeclInfoPool *P = Cur) {
58
36.3k
      Cur = Cur->Next;
59
36.3k
      delete P;
60
36.3k
    }
61
83.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.46M
void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) {
75
4.50M
  for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); 
--I2.04M
) {
76
4.50M
    if (D == *(I-1)) {
77
2.46M
      Decls.erase(I-1);
78
2.46M
      return;
79
2.46M
    }
80
4.50M
  }
81
82
2.46M
  
llvm_unreachable0
("Didn't find this decl on its identifier's chain!");
83
2.46M
}
84
85
//===----------------------------------------------------------------------===//
86
// IdentifierResolver Implementation
87
//===----------------------------------------------------------------------===//
88
89
IdentifierResolver::IdentifierResolver(Preprocessor &PP)
90
88.8k
    : LangOpt(PP.getLangOpts()), PP(PP), IdDeclInfos(new IdDeclInfoMap) {}
91
92
83.0k
IdentifierResolver::~IdentifierResolver() {
93
83.0k
  delete IdDeclInfos;
94
83.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
48.0M
                                       bool AllowInlineNamespace) const {
101
48.0M
  Ctx = Ctx->getRedeclContext();
102
103
48.0M
  if (Ctx->isFunctionOrMethod() || 
(48.0M
S48.0M
&&
S->isFunctionPrototypeScope()47.7M
)) {
104
    // Ignore the scopes associated within transparent declaration contexts.
105
47.9k
    while (S->getEntity() && 
S->getEntity()->isTransparentContext()17.1k
)
106
0
      S = S->getParent();
107
108
47.9k
    if (S->isDeclScope(D))
109
1.40k
      return true;
110
46.5k
    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
45.6k
      assert(S->getParent() && "No TUScope?");
124
45.6k
      if (S->getParent()->getFlags() & Scope::ControlScope) {
125
626
        S = S->getParent();
126
626
        if (S->isDeclScope(D))
127
55
          return true;
128
45.5k
      }
129
45.5k
      if (S->getFlags() & Scope::FnTryCatchScope)
130
6
        return S->getParent()->isDeclScope(D);
131
46.4k
    }
132
46.4k
    return false;
133
46.4k
  }
134
135
  // FIXME: If D is a local extern declaration, this check doesn't make sense;
136
  // we should be checking its lexical context instead in that case, because
137
  // that is its scope.
138
48.0M
  DeclContext *DCtx = D->getDeclContext()->getRedeclContext();
139
878k
  return AllowInlineNamespace ? Ctx->InEnclosingNamespaceSetOf(DCtx)
140
47.1M
                              : Ctx->Equals(DCtx);
141
48.0M
}
142
143
/// AddDecl - Link the decl to its shadowed decl chain.
144
50.9M
void IdentifierResolver::AddDecl(NamedDecl *D) {
145
50.9M
  DeclarationName Name = D->getDeclName();
146
50.9M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
147
50.3M
    updatingIdentifier(*II);
148
149
50.9M
  void *Ptr = Name.getFETokenInfo();
150
151
50.9M
  if (!Ptr) {
152
42.2M
    Name.setFETokenInfo(D);
153
42.2M
    return;
154
42.2M
  }
155
156
8.69M
  IdDeclInfo *IDI;
157
158
8.69M
  if (isDeclPtr(Ptr)) {
159
1.92M
    Name.setFETokenInfo(nullptr);
160
1.92M
    IDI = &(*IdDeclInfos)[Name];
161
1.92M
    NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
162
1.92M
    IDI->AddDecl(PrevD);
163
1.92M
  } else
164
6.76M
    IDI = toIdDeclInfo(Ptr);
165
166
8.69M
  IDI->AddDecl(D);
167
8.69M
}
168
169
4.26k
void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) {
170
4.26k
  DeclarationName Name = D->getDeclName();
171
4.26k
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
172
4.26k
    updatingIdentifier(*II);
173
174
4.26k
  void *Ptr = Name.getFETokenInfo();
175
176
4.26k
  if (!Ptr) {
177
3.92k
    AddDecl(D);
178
3.92k
    return;
179
3.92k
  }
180
181
339
  if (isDeclPtr(Ptr)) {
182
    // We only have a single declaration: insert before or after it,
183
    // as appropriate.
184
251
    if (Pos == iterator()) {
185
      // Add the new declaration before the existing declaration.
186
8
      NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
187
8
      RemoveDecl(PrevD);
188
8
      AddDecl(D);
189
8
      AddDecl(PrevD);
190
243
    } else {
191
      // Add new declaration after the existing declaration.
192
243
      AddDecl(D);
193
243
    }
194
195
251
    return;
196
251
  }
197
198
  // General case: insert the declaration at the appropriate point in the
199
  // list, which already has at least two elements.
200
88
  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
201
88
  if (Pos.isIterator()) {
202
52
    IDI->InsertDecl(Pos.getIterator() + 1, D);
203
52
  } else
204
36
    IDI->InsertDecl(IDI->decls_begin(), D);
205
88
}
206
207
/// RemoveDecl - Unlink the decl from its shadowed decl chain.
208
/// The decl must already be part of the decl chain.
209
28.7M
void IdentifierResolver::RemoveDecl(NamedDecl *D) {
210
28.7M
  assert(D && "null param passed");
211
28.7M
  DeclarationName Name = D->getDeclName();
212
28.7M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
213
28.2M
    updatingIdentifier(*II);
214
215
28.7M
  void *Ptr = Name.getFETokenInfo();
216
217
28.7M
  assert(Ptr && "Didn't find this decl on its identifier's chain!");
218
219
28.7M
  if (isDeclPtr(Ptr)) {
220
26.3M
    assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
221
26.3M
    Name.setFETokenInfo(nullptr);
222
26.3M
    return;
223
26.3M
  }
224
225
2.46M
  return toIdDeclInfo(Ptr)->RemoveDecl(D);
226
2.46M
}
227
228
/// begin - Returns an iterator for decls with name 'Name'.
229
IdentifierResolver::iterator
230
192M
IdentifierResolver::begin(DeclarationName Name) {
231
192M
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
232
188M
    readingIdentifier(*II);
233
234
192M
  void *Ptr = Name.getFETokenInfo();
235
192M
  if (!Ptr) 
return end()95.6M
;
236
237
96.3M
  if (isDeclPtr(Ptr))
238
76.1M
    return iterator(static_cast<NamedDecl*>(Ptr));
239
240
20.1M
  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
241
242
20.1M
  IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
243
20.1M
  if (I != IDI->decls_begin())
244
17.2M
    return iterator(I-1);
245
  // No decls found.
246
2.93M
  return end();
247
2.93M
}
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
41.2k
static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
263
  // If the declarations are identical, ignore the new one.
264
41.2k
  if (Existing == New)
265
13.4k
    return DMK_Ignore;
266
267
  // If the declarations have different kinds, they're obviously different.
268
27.7k
  if (Existing->getKind() != New->getKind())
269
2.37k
    return DMK_Different;
270
271
  // If the declarations are redeclarations of each other, keep the newest one.
272
25.4k
  if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
273
    // If we're adding an imported declaration, don't replace another imported
274
    // declaration.
275
850
    if (Existing->isFromASTFile() && 
New->isFromASTFile()587
)
276
587
      return DMK_Different;
277
278
    // If either of these is the most recent declaration, use it.
279
263
    Decl *MostRecent = Existing->getMostRecentDecl();
280
263
    if (Existing == MostRecent)
281
175
      return DMK_Ignore;
282
283
88
    if (New == MostRecent)
284
76
      return DMK_Replace;
285
286
    // If the existing declaration is somewhere in the previous declaration
287
    // chain of the new declaration, then prefer the new declaration.
288
358
    
for (auto RD : New->redecls())12
{
289
358
      if (RD == Existing)
290
5
        return DMK_Replace;
291
292
353
      if (RD->isCanonicalDecl())
293
7
        break;
294
353
    }
295
296
7
    return DMK_Ignore;
297
24.5k
  }
298
299
24.5k
  return DMK_Different;
300
24.5k
}
301
302
210k
bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){
303
210k
  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
304
201k
    readingIdentifier(*II);
305
306
210k
  void *Ptr = Name.getFETokenInfo();
307
308
210k
  if (!Ptr) {
309
188k
    Name.setFETokenInfo(D);
310
188k
    return true;
311
188k
  }
312
313
22.9k
  IdDeclInfo *IDI;
314
315
22.9k
  if (isDeclPtr(Ptr)) {
316
15.7k
    NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
317
318
15.7k
    switch (compareDeclarations(PrevD, D)) {
319
3.55k
    case DMK_Different:
320
3.55k
      break;
321
322
12.1k
    case DMK_Ignore:
323
12.1k
      return false;
324
325
78
    case DMK_Replace:
326
78
      Name.setFETokenInfo(D);
327
78
      return true;
328
3.55k
    }
329
330
3.55k
    Name.setFETokenInfo(nullptr);
331
3.55k
    IDI = &(*IdDeclInfos)[Name];
332
333
    // If the existing declaration is not visible in translation unit scope,
334
    // then add the new top-level declaration first.
335
3.55k
    if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
336
0
      IDI->AddDecl(D);
337
0
      IDI->AddDecl(PrevD);
338
3.55k
    } else {
339
3.55k
      IDI->AddDecl(PrevD);
340
3.55k
      IDI->AddDecl(D);
341
3.55k
    }
342
3.55k
    return true;
343
3.55k
  }
344
345
7.15k
  IDI = toIdDeclInfo(Ptr);
346
347
  // See whether this declaration is identical to any existing declarations.
348
  // If not, find the right place to insert it.
349
7.15k
  for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
350
7.15k
                                  IEnd = IDI->decls_end();
351
31.1k
       I != IEnd; 
++I23.9k
) {
352
353
25.4k
    switch (compareDeclarations(*I, D)) {
354
23.9k
    case DMK_Different:
355
23.9k
      break;
356
357
1.48k
    case DMK_Ignore:
358
1.48k
      return false;
359
360
3
    case DMK_Replace:
361
3
      *I = D;
362
3
      return true;
363
23.9k
    }
364
365
23.9k
    if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
366
      // We've found a declaration that is not visible from the translation
367
      // unit (it's in an inner scope). Insert our declaration here.
368
0
      IDI->InsertDecl(I, D);
369
0
      return true;
370
0
    }
371
23.9k
  }
372
373
  // Add the declaration to the end.
374
5.66k
  IDI->AddDecl(D);
375
5.66k
  return true;
376
7.15k
}
377
378
188M
void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
379
188M
  if (II.isOutOfDate())
380
1.31M
    PP.getExternalSource()->updateOutOfDateIdentifier(II);
381
188M
}
382
383
78.5M
void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
384
78.5M
  if (II.isOutOfDate())
385
619
    PP.getExternalSource()->updateOutOfDateIdentifier(II);
386
387
78.5M
  if (II.isFromAST())
388
477k
    II.setFETokenInfoChangedSinceDeserialization();
389
78.5M
}
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.93M
IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) {
399
1.93M
  void *Ptr = Name.getFETokenInfo();
400
401
1.93M
  if (Ptr) 
return *toIdDeclInfo(Ptr)0
;
402
403
1.93M
  if (CurIndex == POOL_SIZE) {
404
39.4k
    CurPool = new IdDeclInfoPool(CurPool);
405
39.4k
    CurIndex = 0;
406
39.4k
  }
407
1.93M
  IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
408
1.93M
  Name.setFETokenInfo(reinterpret_cast<void*>(
409
1.93M
                              reinterpret_cast<uintptr_t>(IDI) | 0x1)
410
1.93M
                                                                     );
411
1.93M
  ++CurIndex;
412
1.93M
  return *IDI;
413
1.93M
}
414
415
97.5M
void IdentifierResolver::iterator::incrementSlowCase() {
416
97.5M
  NamedDecl *D = **this;
417
97.5M
  void *InfoPtr = D->getDeclName().getFETokenInfo();
418
97.5M
  assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
419
97.5M
  IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
420
421
97.5M
  BaseIter I = getIterator();
422
97.5M
  if (I != Info->decls_begin())
423
81.4M
    *this = iterator(I-1);
424
16.0M
  else // No more decls.
425
16.0M
    *this = iterator();
426
97.5M
}