Coverage Report

Created: 2021-08-24 07:12

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/AST/DeclContextInternals.h
Line
Count
Source (jump to first uncovered line)
1
//===- DeclContextInternals.h - DeclContext Representation ------*- C++ -*-===//
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 defines the data structures used in the implementation
10
//  of DeclContext.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H
15
#define LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H
16
17
#include "clang/AST/ASTContext.h"
18
#include "clang/AST/Decl.h"
19
#include "clang/AST/DeclBase.h"
20
#include "clang/AST/DeclCXX.h"
21
#include "clang/AST/DeclarationName.h"
22
#include "llvm/ADT/DenseMap.h"
23
#include "llvm/ADT/PointerIntPair.h"
24
#include "llvm/ADT/PointerUnion.h"
25
#include <cassert>
26
27
namespace clang {
28
29
class DependentDiagnostic;
30
31
/// An array of decls optimized for the common case of only containing
32
/// one entry.
33
class StoredDeclsList {
34
  using Decls = DeclListNode::Decls;
35
36
  /// A collection of declarations, with a flag to indicate if we have
37
  /// further external declarations.
38
  using DeclsAndHasExternalTy = llvm::PointerIntPair<Decls, 1, bool>;
39
40
  /// The stored data, which will be either a pointer to a NamedDecl,
41
  /// or a pointer to a list with a flag to indicate if there are further
42
  /// external declarations.
43
  DeclsAndHasExternalTy Data;
44
45
  template<typename Fn>
46
2.05M
  void erase_if(Fn ShouldErase) {
47
2.05M
    Decls List = Data.getPointer();
48
2.05M
    if (!List)
49
1.49M
      return;
50
553k
    ASTContext &C = getASTContext();
51
553k
    DeclListNode::Decls NewHead = nullptr;
52
553k
    DeclListNode::Decls *NewLast = nullptr;
53
553k
    DeclListNode::Decls *NewTail = &NewHead;
54
844k
    while (true) {
55
844k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
102k
        NewLast = NewTail;
57
102k
        *NewTail = List;
58
102k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
7.94k
          NewTail = &Node->Rest;
60
7.94k
          List = Node->Rest;
61
94.4k
        } else {
62
94.4k
          break;
63
94.4k
        }
64
741k
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
282k
        List = N->Rest;
66
282k
        C.DeallocateDeclListNode(N);
67
459k
      } else {
68
        // We're discarding the last declaration in the list. The last node we
69
        // want to keep (if any) will be of the form DeclListNode(D, <rest>);
70
        // replace it with just D.
71
459k
        if (NewLast) {
72
259
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
259
          *NewLast = Node->D;
74
259
          C.DeallocateDeclListNode(Node);
75
259
        }
76
459k
        break;
77
459k
      }
78
844k
    }
79
553k
    Data.setPointer(NewHead);
80
81
553k
    assert(llvm::find_if(getLookupResult(), ShouldErase) ==
82
553k
           getLookupResult().end() && "Still exists!");
83
553k
  }
void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::erase(clang::NamedDecl*)::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::erase(clang::NamedDecl*)::'lambda'(clang::NamedDecl*))
Line
Count
Source
46
46.5k
  void erase_if(Fn ShouldErase) {
47
46.5k
    Decls List = Data.getPointer();
48
46.5k
    if (!List)
49
0
      return;
50
46.5k
    ASTContext &C = getASTContext();
51
46.5k
    DeclListNode::Decls NewHead = nullptr;
52
46.5k
    DeclListNode::Decls *NewLast = nullptr;
53
46.5k
    DeclListNode::Decls *NewTail = &NewHead;
54
48.4k
    while (true) {
55
48.4k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
1.88k
        NewLast = NewTail;
57
1.88k
        *NewTail = List;
58
1.88k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
1.64k
          NewTail = &Node->Rest;
60
1.64k
          List = Node->Rest;
61
1.64k
        } else {
62
245
          break;
63
245
        }
64
46.5k
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
244
        List = N->Rest;
66
244
        C.DeallocateDeclListNode(N);
67
46.2k
      } else {
68
        // We're discarding the last declaration in the list. The last node we
69
        // want to keep (if any) will be of the form DeclListNode(D, <rest>);
70
        // replace it with just D.
71
46.2k
        if (NewLast) {
72
54
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
54
          *NewLast = Node->D;
74
54
          C.DeallocateDeclListNode(Node);
75
54
        }
76
46.2k
        break;
77
46.2k
      }
78
48.4k
    }
79
46.5k
    Data.setPointer(NewHead);
80
81
46.5k
    assert(llvm::find_if(getLookupResult(), ShouldErase) ==
82
46.5k
           getLookupResult().end() && "Still exists!");
83
46.5k
  }
void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*))
Line
Count
Source
46
649k
  void erase_if(Fn ShouldErase) {
47
649k
    Decls List = Data.getPointer();
48
649k
    if (!List)
49
647k
      return;
50
1.25k
    ASTContext &C = getASTContext();
51
1.25k
    DeclListNode::Decls NewHead = nullptr;
52
1.25k
    DeclListNode::Decls *NewLast = nullptr;
53
1.25k
    DeclListNode::Decls *NewTail = &NewHead;
54
5.20k
    while (true) {
55
5.20k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
5.20k
        NewLast = NewTail;
57
5.20k
        *NewTail = List;
58
5.20k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
3.95k
          NewTail = &Node->Rest;
60
3.95k
          List = Node->Rest;
61
3.95k
        } else {
62
1.25k
          break;
63
1.25k
        }
64
5.20k
      } else 
if (DeclListNode *0
N0
= List.dyn_cast<DeclListNode*>()) {
65
0
        List = N->Rest;
66
0
        C.DeallocateDeclListNode(N);
67
0
      } else {
68
        // We're discarding the last declaration in the list. The last node we
69
        // want to keep (if any) will be of the form DeclListNode(D, <rest>);
70
        // replace it with just D.
71
0
        if (NewLast) {
72
0
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
0
          *NewLast = Node->D;
74
0
          C.DeallocateDeclListNode(Node);
75
0
        }
76
0
        break;
77
0
      }
78
5.20k
    }
79
1.25k
    Data.setPointer(NewHead);
80
81
1.25k
    assert(llvm::find_if(getLookupResult(), ShouldErase) ==
82
1.25k
           getLookupResult().end() && "Still exists!");
83
1.25k
  }
void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::replaceExternalDecls(llvm::ArrayRef<clang::NamedDecl*>)::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::replaceExternalDecls(llvm::ArrayRef<clang::NamedDecl*>)::'lambda'(clang::NamedDecl*))
Line
Count
Source
46
1.35M
  void erase_if(Fn ShouldErase) {
47
1.35M
    Decls List = Data.getPointer();
48
1.35M
    if (!List)
49
849k
      return;
50
505k
    ASTContext &C = getASTContext();
51
505k
    DeclListNode::Decls NewHead = nullptr;
52
505k
    DeclListNode::Decls *NewLast = nullptr;
53
505k
    DeclListNode::Decls *NewTail = &NewHead;
54
790k
    while (true) {
55
790k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
95.3k
        NewLast = NewTail;
57
95.3k
        *NewTail = List;
58
95.3k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
2.35k
          NewTail = &Node->Rest;
60
2.35k
          List = Node->Rest;
61
92.9k
        } else {
62
92.9k
          break;
63
92.9k
        }
64
695k
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
282k
        List = N->Rest;
66
282k
        C.DeallocateDeclListNode(N);
67
412k
      } else {
68
        // We're discarding the last declaration in the list. The last node we
69
        // want to keep (if any) will be of the form DeclListNode(D, <rest>);
70
        // replace it with just D.
71
412k
        if (NewLast) {
72
205
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
205
          *NewLast = Node->D;
74
205
          C.DeallocateDeclListNode(Node);
75
205
        }
76
412k
        break;
77
412k
      }
78
790k
    }
79
505k
    Data.setPointer(NewHead);
80
81
505k
    assert(llvm::find_if(getLookupResult(), ShouldErase) ==
82
505k
           getLookupResult().end() && "Still exists!");
83
505k
  }
84
85
46.5k
  void erase(NamedDecl *ND) {
86
50.3k
    erase_if([ND](NamedDecl *D) { return D == ND; });
87
46.5k
  }
88
89
public:
90
25.6M
  StoredDeclsList() = default;
91
92
26.7M
  StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
93
26.7M
    RHS.Data.setPointer(nullptr);
94
26.7M
    RHS.Data.setInt(0);
95
26.7M
  }
96
97
43.3M
  void MaybeDeallocList() {
98
43.3M
    if (isNull())
99
34.0M
      return;
100
    // If this is a list-form, free the list.
101
9.26M
    ASTContext &C = getASTContext();
102
9.26M
    Decls List = Data.getPointer();
103
13.3M
    while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) {
104
4.06M
      List = ToDealloc->Rest;
105
4.06M
      C.DeallocateDeclListNode(ToDealloc);
106
4.06M
    }
107
9.26M
  }
108
109
43.3M
  ~StoredDeclsList() {
110
43.3M
    MaybeDeallocList();
111
43.3M
  }
112
113
0
  StoredDeclsList &operator=(StoredDeclsList &&RHS) {
114
0
    MaybeDeallocList();
115
0
116
0
    Data = RHS.Data;
117
0
    RHS.Data.setPointer(nullptr);
118
0
    RHS.Data.setInt(0);
119
0
    return *this;
120
0
  }
121
122
77.5M
  bool isNull() const { return Data.getPointer().isNull(); }
123
124
9.81M
  ASTContext &getASTContext() {
125
9.81M
    assert(!isNull() && "No ASTContext.");
126
9.81M
    if (NamedDecl *ND = getAsDecl())
127
8.92M
      return ND->getASTContext();
128
889k
    return getAsList()->D->getASTContext();
129
9.81M
  }
130
131
27.7M
  DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; }
132
133
15.2M
  NamedDecl *getAsDecl() const {
134
15.2M
    return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>();
135
15.2M
  }
136
137
4.55M
  DeclListNode *getAsList() const {
138
4.55M
    return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>();
139
4.55M
  }
140
141
7.87M
  bool hasExternalDecls() const {
142
7.87M
    return getAsListAndHasExternal().getInt();
143
7.87M
  }
144
145
2.78M
  void setHasExternalDecls() {
146
2.78M
    Data.setInt(1);
147
2.78M
  }
148
149
46.5k
  void remove(NamedDecl *D) {
150
46.5k
    assert(!isNull() && "removing from empty list");
151
0
    erase(D);
152
46.5k
  }
153
154
  /// Remove any declarations which were imported from an external AST source.
155
649k
  void removeExternalDecls() {
156
649k
    erase_if([](NamedDecl *ND) 
{ return ND->isFromASTFile(); }10.4k
);
157
158
    // Don't have any pending external decls any more.
159
649k
    Data.setInt(0);
160
649k
  }
161
162
1.35M
  void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) {
163
    // Remove all declarations that are either external or are replaced with
164
    // external declarations.
165
1.35M
    erase_if([Decls](NamedDecl *ND) {
166
885k
      if (ND->isFromASTFile())
167
682k
        return true;
168
203k
      for (NamedDecl *D : Decls)
169
22.0k
        if (D->declarationReplaces(ND, /*IsKnownNewer=*/false))
170
13.0k
          return true;
171
190k
      return false;
172
203k
    });
173
174
    // Don't have any pending external decls any more.
175
1.35M
    Data.setInt(0);
176
177
1.35M
    if (Decls.empty())
178
868k
      return;
179
180
    // Convert Decls into a list, in order.
181
486k
    ASTContext &C = Decls.front()->getASTContext();
182
486k
    DeclListNode::Decls DeclsAsList = Decls.back();
183
820k
    for (size_t I = Decls.size() - 1; I != 0; 
--I334k
) {
184
334k
      DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]);
185
334k
      Node->Rest = DeclsAsList;
186
334k
      DeclsAsList = Node;
187
334k
    }
188
189
486k
    DeclListNode::Decls Head = Data.getPointer();
190
486k
    if (Head.isNull()) {
191
485k
      Data.setPointer(DeclsAsList);
192
485k
      return;
193
485k
    }
194
195
    // Find the end of the existing list.
196
    // FIXME: It would be possible to preserve information from erase_if to
197
    // avoid this rescan looking for the end of the list.
198
1.07k
    DeclListNode::Decls *Tail = &Head;
199
1.15k
    while (DeclListNode *Node = Tail->dyn_cast<DeclListNode *>())
200
83
      Tail = &Node->Rest;
201
202
    // Append the Decls.
203
1.07k
    DeclListNode *Node = C.AllocateDeclListNode(Tail->get<NamedDecl *>());
204
1.07k
    Node->Rest = DeclsAsList;
205
1.07k
    *Tail = Node;
206
1.07k
    Data.setPointer(Head);
207
1.07k
  }
208
209
  /// Return an array of all the decls that this list represents.
210
88.0M
  DeclContext::lookup_result getLookupResult() const {
211
88.0M
    return DeclContext::lookup_result(Data.getPointer());
212
88.0M
  }
213
214
  /// If this is a redeclaration of an existing decl, replace the old one with
215
  /// D. Otherwise, append D.
216
22.5M
  void addOrReplaceDecl(NamedDecl *D) {
217
22.5M
    const bool IsKnownNewer = true;
218
219
22.5M
    if (isNull()) {
220
17.0M
      Data.setPointer(D);
221
17.0M
      return;
222
17.0M
    }
223
224
    // Most decls only have one entry in their list, special case it.
225
5.47M
    if (NamedDecl *OldD = getAsDecl()) {
226
1.80M
      if (D->declarationReplaces(OldD, IsKnownNewer)) {
227
454k
        Data.setPointer(D);
228
454k
        return;
229
454k
      }
230
231
      // Add D after OldD.
232
1.35M
      ASTContext &C = D->getASTContext();
233
1.35M
      DeclListNode *Node = C.AllocateDeclListNode(OldD);
234
1.35M
      Node->Rest = D;
235
1.35M
      Data.setPointer(Node);
236
1.35M
      return;
237
1.80M
    }
238
239
    // FIXME: Move the assert before the single decl case when we fix the
240
    // duplication coming from the ASTReader reading builtin types.
241
3.66M
    assert(!llvm::is_contained(getLookupResult(), D) && "Already exists!");
242
    // Determine if this declaration is actually a redeclaration.
243
0
    for (DeclListNode *N = getAsList(); /*return in loop*/;
244
24.3M
         
N = N->Rest.dyn_cast<DeclListNode *>()20.6M
) {
245
24.3M
      if (D->declarationReplaces(N->D, IsKnownNewer)) {
246
109k
        N->D = D;
247
109k
        return;
248
109k
      }
249
24.1M
      if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) {
250
3.55M
        if (D->declarationReplaces(ND, IsKnownNewer)) {
251
33.8k
          N->Rest = D;
252
33.8k
          return;
253
33.8k
        }
254
255
        // Add D after ND.
256
3.52M
        ASTContext &C = D->getASTContext();
257
3.52M
        DeclListNode *Node = C.AllocateDeclListNode(ND);
258
3.52M
        N->Rest = Node;
259
3.52M
        Node->Rest = D;
260
3.52M
        return;
261
3.55M
      }
262
24.1M
    }
263
3.66M
  }
264
265
  /// Add a declaration to the list without checking if it replaces anything.
266
1.76M
  void prependDeclNoReplace(NamedDecl *D) {
267
1.76M
    if (isNull()) {
268
1.19M
      Data.setPointer(D);
269
1.19M
      return;
270
1.19M
    }
271
272
570k
    ASTContext &C = D->getASTContext();
273
570k
    DeclListNode *Node = C.AllocateDeclListNode(D);
274
570k
    Node->Rest = Data.getPointer();
275
570k
    Data.setPointer(Node);
276
570k
  }
277
278
0
  LLVM_DUMP_METHOD void dump() const {
279
0
    Decls D = Data.getPointer();
280
0
    if (!D) {
281
0
      llvm::errs() << "<null>\n";
282
0
      return;
283
0
    }
284
285
0
    while (true) {
286
0
      if (auto *Node = D.dyn_cast<DeclListNode*>()) {
287
0
        llvm::errs() << '[' << Node->D << "] -> ";
288
0
        D = Node->Rest;
289
0
      } else {
290
0
        llvm::errs() << '[' << D.get<NamedDecl*>() << "]\n";
291
0
        return;
292
0
      }
293
0
    }
294
0
  }
295
};
296
297
class StoredDeclsMap
298
    : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> {
299
  friend class ASTContext; // walks the chain deleting these
300
  friend class DeclContext;
301
302
  llvm::PointerIntPair<StoredDeclsMap*, 1> Previous;
303
public:
304
  static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
305
};
306
307
class DependentStoredDeclsMap : public StoredDeclsMap {
308
  friend class DeclContext; // iterates over diagnostics
309
  friend class DependentDiagnostic;
310
311
  DependentDiagnostic *FirstDiagnostic = nullptr;
312
public:
313
439k
  DependentStoredDeclsMap() = default;
314
};
315
316
} // namespace clang
317
318
#endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H