Coverage Report

Created: 2022-05-17 06:19

/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.20M
  void erase_if(Fn ShouldErase) {
47
2.20M
    Decls List = Data.getPointer();
48
2.20M
    if (!List)
49
1.22M
      return;
50
978k
    ASTContext &C = getASTContext();
51
978k
    DeclListNode::Decls NewHead = nullptr;
52
978k
    DeclListNode::Decls *NewLast = nullptr;
53
978k
    DeclListNode::Decls *NewTail = &NewHead;
54
1.45M
    while (true) {
55
1.45M
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
104k
        NewLast = NewTail;
57
104k
        *NewTail = List;
58
104k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
8.11k
          NewTail = &Node->Rest;
60
8.11k
          List = Node->Rest;
61
95.9k
        } else {
62
95.9k
          break;
63
95.9k
        }
64
1.34M
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
463k
        List = N->Rest;
66
463k
        C.DeallocateDeclListNode(N);
67
882k
      } 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
882k
        if (NewLast) {
72
252
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
252
          *NewLast = Node->D;
74
252
          C.DeallocateDeclListNode(Node);
75
252
        }
76
882k
        break;
77
882k
      }
78
1.45M
    }
79
978k
    Data.setPointer(NewHead);
80
81
978k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
978k
  }
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
58.4k
  void erase_if(Fn ShouldErase) {
47
58.4k
    Decls List = Data.getPointer();
48
58.4k
    if (!List)
49
0
      return;
50
58.4k
    ASTContext &C = getASTContext();
51
58.4k
    DeclListNode::Decls NewHead = nullptr;
52
58.4k
    DeclListNode::Decls *NewLast = nullptr;
53
58.4k
    DeclListNode::Decls *NewTail = &NewHead;
54
60.5k
    while (true) {
55
60.5k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
2.06k
        NewLast = NewTail;
57
2.06k
        *NewTail = List;
58
2.06k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
1.79k
          NewTail = &Node->Rest;
60
1.79k
          List = Node->Rest;
61
1.79k
        } else {
62
271
          break;
63
271
        }
64
58.4k
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
270
        List = N->Rest;
66
270
        C.DeallocateDeclListNode(N);
67
58.1k
      } 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
58.1k
        if (NewLast) {
72
48
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
48
          *NewLast = Node->D;
74
48
          C.DeallocateDeclListNode(Node);
75
48
        }
76
58.1k
        break;
77
58.1k
      }
78
60.5k
    }
79
58.4k
    Data.setPointer(NewHead);
80
81
58.4k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
58.4k
  }
void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*))
Line
Count
Source
46
401k
  void erase_if(Fn ShouldErase) {
47
401k
    Decls List = Data.getPointer();
48
401k
    if (!List)
49
400k
      return;
50
990
    ASTContext &C = getASTContext();
51
990
    DeclListNode::Decls NewHead = nullptr;
52
990
    DeclListNode::Decls *NewLast = nullptr;
53
990
    DeclListNode::Decls *NewTail = &NewHead;
54
4.96k
    while (true) {
55
4.96k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
4.96k
        NewLast = NewTail;
57
4.96k
        *NewTail = List;
58
4.96k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
3.97k
          NewTail = &Node->Rest;
60
3.97k
          List = Node->Rest;
61
3.97k
        } else {
62
990
          break;
63
990
        }
64
4.96k
      } 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
4.96k
    }
79
990
    Data.setPointer(NewHead);
80
81
990
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
990
  }
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.74M
  void erase_if(Fn ShouldErase) {
47
1.74M
    Decls List = Data.getPointer();
48
1.74M
    if (!List)
49
827k
      return;
50
919k
    ASTContext &C = getASTContext();
51
919k
    DeclListNode::Decls NewHead = nullptr;
52
919k
    DeclListNode::Decls *NewLast = nullptr;
53
919k
    DeclListNode::Decls *NewTail = &NewHead;
54
1.38M
    while (true) {
55
1.38M
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
96.9k
        NewLast = NewTail;
57
96.9k
        *NewTail = List;
58
96.9k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
2.35k
          NewTail = &Node->Rest;
60
2.35k
          List = Node->Rest;
61
94.6k
        } else {
62
94.6k
          break;
63
94.6k
        }
64
1.28M
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
463k
        List = N->Rest;
66
463k
        C.DeallocateDeclListNode(N);
67
824k
      } 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
824k
        if (NewLast) {
72
204
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
204
          *NewLast = Node->D;
74
204
          C.DeallocateDeclListNode(Node);
75
204
        }
76
824k
        break;
77
824k
      }
78
1.38M
    }
79
919k
    Data.setPointer(NewHead);
80
81
919k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
919k
  }
83
84
58.4k
  void erase(NamedDecl *ND) {
85
62.5k
    erase_if([ND](NamedDecl *D) { return D == ND; });
86
58.4k
  }
87
88
public:
89
27.7M
  StoredDeclsList() = default;
90
91
28.3M
  StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
92
28.3M
    RHS.Data.setPointer(nullptr);
93
28.3M
    RHS.Data.setInt(false);
94
28.3M
  }
95
96
56.1M
  void MaybeDeallocList() {
97
56.1M
    if (isNull())
98
36.3M
      return;
99
    // If this is a list-form, free the list.
100
19.7M
    ASTContext &C = getASTContext();
101
19.7M
    Decls List = Data.getPointer();
102
26.2M
    while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) {
103
6.50M
      List = ToDealloc->Rest;
104
6.50M
      C.DeallocateDeclListNode(ToDealloc);
105
6.50M
    }
106
19.7M
  }
107
108
56.1M
  ~StoredDeclsList() {
109
56.1M
    MaybeDeallocList();
110
56.1M
  }
111
112
0
  StoredDeclsList &operator=(StoredDeclsList &&RHS) {
113
0
    MaybeDeallocList();
114
0
115
0
    Data = RHS.Data;
116
0
    RHS.Data.setPointer(nullptr);
117
0
    RHS.Data.setInt(false);
118
0
    return *this;
119
0
  }
120
121
103M
  bool isNull() const { return Data.getPointer().isNull(); }
122
123
20.6M
  ASTContext &getASTContext() {
124
20.6M
    assert(!isNull() && "No ASTContext.");
125
20.6M
    if (NamedDecl *ND = getAsDecl())
126
18.6M
      return ND->getASTContext();
127
2.08M
    return getAsList()->D->getASTContext();
128
20.6M
  }
129
130
41.2M
  DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; }
131
132
26.5M
  NamedDecl *getAsDecl() const {
133
26.5M
    return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>();
134
26.5M
  }
135
136
6.02M
  DeclListNode *getAsList() const {
137
6.02M
    return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>();
138
6.02M
  }
139
140
8.65M
  bool hasExternalDecls() const {
141
8.65M
    return getAsListAndHasExternal().getInt();
142
8.65M
  }
143
144
4.68M
  void setHasExternalDecls() {
145
4.68M
    Data.setInt(true);
146
4.68M
  }
147
148
58.4k
  void remove(NamedDecl *D) {
149
58.4k
    assert(!isNull() && "removing from empty list");
150
0
    erase(D);
151
58.4k
  }
152
153
  /// Remove any declarations which were imported from an external AST source.
154
401k
  void removeExternalDecls() {
155
401k
    erase_if([](NamedDecl *ND) 
{ return ND->isFromASTFile(); }9.92k
);
156
157
    // Don't have any pending external decls any more.
158
401k
    Data.setInt(false);
159
401k
  }
160
161
1.74M
  void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) {
162
    // Remove all declarations that are either external or are replaced with
163
    // external declarations.
164
1.74M
    erase_if([Decls](NamedDecl *ND) {
165
1.48M
      if (ND->isFromASTFile())
166
1.27M
        return true;
167
206k
      for (NamedDecl *D : Decls)
168
21.7k
        if (D->declarationReplaces(ND, /*IsKnownNewer=*/false))
169
12.8k
          return true;
170
193k
      return false;
171
206k
    });
172
173
    // Don't have any pending external decls any more.
174
1.74M
    Data.setInt(false);
175
176
1.74M
    if (Decls.empty())
177
838k
      return;
178
179
    // Convert Decls into a list, in order.
180
907k
    ASTContext &C = Decls.front()->getASTContext();
181
907k
    DeclListNode::Decls DeclsAsList = Decls.back();
182
1.42M
    for (size_t I = Decls.size() - 1; I != 0; 
--I520k
) {
183
520k
      DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]);
184
520k
      Node->Rest = DeclsAsList;
185
520k
      DeclsAsList = Node;
186
520k
    }
187
188
907k
    DeclListNode::Decls Head = Data.getPointer();
189
907k
    if (Head.isNull()) {
190
906k
      Data.setPointer(DeclsAsList);
191
906k
      return;
192
906k
    }
193
194
    // Find the end of the existing list.
195
    // FIXME: It would be possible to preserve information from erase_if to
196
    // avoid this rescan looking for the end of the list.
197
1.08k
    DeclListNode::Decls *Tail = &Head;
198
1.16k
    while (DeclListNode *Node = Tail->dyn_cast<DeclListNode *>())
199
77
      Tail = &Node->Rest;
200
201
    // Append the Decls.
202
1.08k
    DeclListNode *Node = C.AllocateDeclListNode(Tail->get<NamedDecl *>());
203
1.08k
    Node->Rest = DeclsAsList;
204
1.08k
    *Tail = Node;
205
1.08k
    Data.setPointer(Head);
206
1.08k
  }
207
208
  /// Return an array of all the decls that this list represents.
209
87.3M
  DeclContext::lookup_result getLookupResult() const {
210
87.3M
    return DeclContext::lookup_result(Data.getPointer());
211
87.3M
  }
212
213
  /// If this is a redeclaration of an existing decl, replace the old one with
214
  /// D. Otherwise, append D.
215
23.3M
  void addOrReplaceDecl(NamedDecl *D) {
216
23.3M
    const bool IsKnownNewer = true;
217
218
23.3M
    if (isNull()) {
219
17.4M
      Data.setPointer(D);
220
17.4M
      return;
221
17.4M
    }
222
223
    // Most decls only have one entry in their list, special case it.
224
5.90M
    if (NamedDecl *OldD = getAsDecl()) {
225
1.95M
      if (D->declarationReplaces(OldD, IsKnownNewer)) {
226
439k
        Data.setPointer(D);
227
439k
        return;
228
439k
      }
229
230
      // Add D after OldD.
231
1.51M
      ASTContext &C = D->getASTContext();
232
1.51M
      DeclListNode *Node = C.AllocateDeclListNode(OldD);
233
1.51M
      Node->Rest = D;
234
1.51M
      Data.setPointer(Node);
235
1.51M
      return;
236
1.95M
    }
237
238
    // FIXME: Move the assert before the single decl case when we fix the
239
    // duplication coming from the ASTReader reading builtin types.
240
3.94M
    assert(!llvm::is_contained(getLookupResult(), D) && "Already exists!");
241
    // Determine if this declaration is actually a redeclaration.
242
0
    for (DeclListNode *N = getAsList(); /*return in loop*/;
243
24.8M
         
N = N->Rest.dyn_cast<DeclListNode *>()20.9M
) {
244
24.8M
      if (D->declarationReplaces(N->D, IsKnownNewer)) {
245
102k
        N->D = D;
246
102k
        return;
247
102k
      }
248
24.7M
      if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) {
249
3.84M
        if (D->declarationReplaces(ND, IsKnownNewer)) {
250
31.3k
          N->Rest = D;
251
31.3k
          return;
252
31.3k
        }
253
254
        // Add D after ND.
255
3.81M
        ASTContext &C = D->getASTContext();
256
3.81M
        DeclListNode *Node = C.AllocateDeclListNode(ND);
257
3.81M
        N->Rest = Node;
258
3.81M
        Node->Rest = D;
259
3.81M
        return;
260
3.84M
      }
261
24.7M
    }
262
3.94M
  }
263
264
  /// Add a declaration to the list without checking if it replaces anything.
265
3.37M
  void prependDeclNoReplace(NamedDecl *D) {
266
3.37M
    if (isNull()) {
267
2.25M
      Data.setPointer(D);
268
2.25M
      return;
269
2.25M
    }
270
271
1.12M
    ASTContext &C = D->getASTContext();
272
1.12M
    DeclListNode *Node = C.AllocateDeclListNode(D);
273
1.12M
    Node->Rest = Data.getPointer();
274
1.12M
    Data.setPointer(Node);
275
1.12M
  }
276
277
0
  LLVM_DUMP_METHOD void dump() const {
278
0
    Decls D = Data.getPointer();
279
0
    if (!D) {
280
0
      llvm::errs() << "<null>\n";
281
0
      return;
282
0
    }
283
284
0
    while (true) {
285
0
      if (auto *Node = D.dyn_cast<DeclListNode*>()) {
286
0
        llvm::errs() << '[' << Node->D << "] -> ";
287
0
        D = Node->Rest;
288
0
      } else {
289
0
        llvm::errs() << '[' << D.get<NamedDecl*>() << "]\n";
290
0
        return;
291
0
      }
292
0
    }
293
0
  }
294
};
295
296
class StoredDeclsMap
297
    : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> {
298
  friend class ASTContext; // walks the chain deleting these
299
  friend class DeclContext;
300
301
  llvm::PointerIntPair<StoredDeclsMap*, 1> Previous;
302
public:
303
  static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
304
};
305
306
class DependentStoredDeclsMap : public StoredDeclsMap {
307
  friend class DeclContext; // iterates over diagnostics
308
  friend class DependentDiagnostic;
309
310
  DependentDiagnostic *FirstDiagnostic = nullptr;
311
public:
312
466k
  DependentStoredDeclsMap() = default;
313
};
314
315
} // namespace clang
316
317
#endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H