Coverage Report

Created: 2019-07-24 05:18

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