Coverage Report

Created: 2022-07-16 07:03

/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.24M
  void erase_if(Fn ShouldErase) {
47
2.24M
    Decls List = Data.getPointer();
48
2.24M
    if (!List)
49
1.24M
      return;
50
996k
    ASTContext &C = getASTContext();
51
996k
    DeclListNode::Decls NewHead = nullptr;
52
996k
    DeclListNode::Decls *NewLast = nullptr;
53
996k
    DeclListNode::Decls *NewTail = &NewHead;
54
1.47M
    while (true) {
55
1.47M
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
105k
        NewLast = NewTail;
57
105k
        *NewTail = List;
58
105k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
8.85k
          NewTail = &Node->Rest;
60
8.85k
          List = Node->Rest;
61
96.8k
        } else {
62
96.8k
          break;
63
96.8k
        }
64
1.37M
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
472k
        List = N->Rest;
66
472k
        C.DeallocateDeclListNode(N);
67
900k
      } 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
900k
        if (NewLast) {
72
250
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
250
          *NewLast = Node->D;
74
250
          C.DeallocateDeclListNode(Node);
75
250
        }
76
900k
        break;
77
900k
      }
78
1.47M
    }
79
996k
    Data.setPointer(NewHead);
80
81
996k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
996k
  }
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.6k
  void erase_if(Fn ShouldErase) {
47
58.6k
    Decls List = Data.getPointer();
48
58.6k
    if (!List)
49
0
      return;
50
58.6k
    ASTContext &C = getASTContext();
51
58.6k
    DeclListNode::Decls NewHead = nullptr;
52
58.6k
    DeclListNode::Decls *NewLast = nullptr;
53
58.6k
    DeclListNode::Decls *NewTail = &NewHead;
54
60.7k
    while (true) {
55
60.7k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
2.09k
        NewLast = NewTail;
57
2.09k
        *NewTail = List;
58
2.09k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
1.82k
          NewTail = &Node->Rest;
60
1.82k
          List = Node->Rest;
61
1.82k
        } else {
62
276
          break;
63
276
        }
64
58.6k
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
275
        List = N->Rest;
66
275
        C.DeallocateDeclListNode(N);
67
58.4k
      } 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.4k
        if (NewLast) {
72
49
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
49
          *NewLast = Node->D;
74
49
          C.DeallocateDeclListNode(Node);
75
49
        }
76
58.4k
        break;
77
58.4k
      }
78
60.7k
    }
79
58.6k
    Data.setPointer(NewHead);
80
81
58.6k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
58.6k
  }
void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*))
Line
Count
Source
46
411k
  void erase_if(Fn ShouldErase) {
47
411k
    Decls List = Data.getPointer();
48
411k
    if (!List)
49
409k
      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.86k
    while (true) {
55
5.86k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
5.86k
        NewLast = NewTail;
57
5.86k
        *NewTail = List;
58
5.86k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
4.60k
          NewTail = &Node->Rest;
60
4.60k
          List = Node->Rest;
61
4.60k
        } else {
62
1.25k
          break;
63
1.25k
        }
64
5.86k
      } 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.86k
    }
79
1.25k
    Data.setPointer(NewHead);
80
81
1.25k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
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.77M
  void erase_if(Fn ShouldErase) {
47
1.77M
    Decls List = Data.getPointer();
48
1.77M
    if (!List)
49
840k
      return;
50
936k
    ASTContext &C = getASTContext();
51
936k
    DeclListNode::Decls NewHead = nullptr;
52
936k
    DeclListNode::Decls *NewLast = nullptr;
53
936k
    DeclListNode::Decls *NewTail = &NewHead;
54
1.41M
    while (true) {
55
1.41M
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
97.7k
        NewLast = NewTail;
57
97.7k
        *NewTail = List;
58
97.7k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
2.42k
          NewTail = &Node->Rest;
60
2.42k
          List = Node->Rest;
61
95.2k
        } else {
62
95.2k
          break;
63
95.2k
        }
64
1.31M
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
472k
        List = N->Rest;
66
472k
        C.DeallocateDeclListNode(N);
67
841k
      } 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
841k
        if (NewLast) {
72
201
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
201
          *NewLast = Node->D;
74
201
          C.DeallocateDeclListNode(Node);
75
201
        }
76
841k
        break;
77
841k
      }
78
1.41M
    }
79
936k
    Data.setPointer(NewHead);
80
81
936k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
936k
  }
83
84
58.6k
  void erase(NamedDecl *ND) {
85
62.8k
    erase_if([ND](NamedDecl *D) { return D == ND; });
86
58.6k
  }
87
88
public:
89
29.4M
  StoredDeclsList() = default;
90
91
30.1M
  StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
92
30.1M
    RHS.Data.setPointer(nullptr);
93
30.1M
    RHS.Data.setInt(false);
94
30.1M
  }
95
96
59.5M
  void MaybeDeallocList() {
97
59.5M
    if (isNull())
98
38.4M
      return;
99
    // If this is a list-form, free the list.
100
21.0M
    ASTContext &C = getASTContext();
101
21.0M
    Decls List = Data.getPointer();
102
27.9M
    while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) {
103
6.85M
      List = ToDealloc->Rest;
104
6.85M
      C.DeallocateDeclListNode(ToDealloc);
105
6.85M
    }
106
21.0M
  }
107
108
59.5M
  ~StoredDeclsList() {
109
59.5M
    MaybeDeallocList();
110
59.5M
  }
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
110M
  bool isNull() const { return Data.getPointer().isNull(); }
122
123
22.0M
  ASTContext &getASTContext() {
124
22.0M
    assert(!isNull() && "No ASTContext.");
125
22.0M
    if (NamedDecl *ND = getAsDecl())
126
19.8M
      return ND->getASTContext();
127
2.26M
    return getAsList()->D->getASTContext();
128
22.0M
  }
129
130
43.9M
  DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; }
131
132
28.5M
  NamedDecl *getAsDecl() const {
133
28.5M
    return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>();
134
28.5M
  }
135
136
6.42M
  DeclListNode *getAsList() const {
137
6.42M
    return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>();
138
6.42M
  }
139
140
8.96M
  bool hasExternalDecls() const {
141
8.96M
    return getAsListAndHasExternal().getInt();
142
8.96M
  }
143
144
4.88M
  void setHasExternalDecls() {
145
4.88M
    Data.setInt(true);
146
4.88M
  }
147
148
58.6k
  void remove(NamedDecl *D) {
149
58.6k
    assert(!isNull() && "removing from empty list");
150
0
    erase(D);
151
58.6k
  }
152
153
  /// Remove any declarations which were imported from an external AST source.
154
411k
  void removeExternalDecls() {
155
411k
    erase_if([](NamedDecl *ND) 
{ return ND->isFromASTFile(); }11.7k
);
156
157
    // Don't have any pending external decls any more.
158
411k
    Data.setInt(false);
159
411k
  }
160
161
1.77M
  void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) {
162
    // Remove all declarations that are either external or are replaced with
163
    // external declarations.
164
1.77M
    erase_if([Decls](NamedDecl *ND) {
165
1.50M
      if (ND->isFromASTFile())
166
1.30M
        return true;
167
208k
      for (NamedDecl *D : Decls)
168
22.1k
        if (D->declarationReplaces(ND, /*IsKnownNewer=*/false))
169
13.2k
          return true;
170
195k
      return false;
171
208k
    });
172
173
    // Don't have any pending external decls any more.
174
1.77M
    Data.setInt(false);
175
176
1.77M
    if (Decls.empty())
177
851k
      return;
178
179
    // Convert Decls into a list, in order.
180
925k
    ASTContext &C = Decls.front()->getASTContext();
181
925k
    DeclListNode::Decls DeclsAsList = Decls.back();
182
1.45M
    for (size_t I = Decls.size() - 1; I != 0; 
--I530k
) {
183
530k
      DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]);
184
530k
      Node->Rest = DeclsAsList;
185
530k
      DeclsAsList = Node;
186
530k
    }
187
188
925k
    DeclListNode::Decls Head = Data.getPointer();
189
925k
    if (Head.isNull()) {
190
924k
      Data.setPointer(DeclsAsList);
191
924k
      return;
192
924k
    }
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
101M
  DeclContext::lookup_result getLookupResult() const {
210
101M
    return DeclContext::lookup_result(Data.getPointer());
211
101M
  }
212
213
  /// If this is a redeclaration of an existing decl, replace the old one with
214
  /// D. Otherwise, append D.
215
25.2M
  void addOrReplaceDecl(NamedDecl *D) {
216
25.2M
    const bool IsKnownNewer = true;
217
218
25.2M
    if (isNull()) {
219
18.7M
      Data.setPointer(D);
220
18.7M
      return;
221
18.7M
    }
222
223
    // Most decls only have one entry in their list, special case it.
224
6.52M
    if (NamedDecl *OldD = getAsDecl()) {
225
2.37M
      if (D->declarationReplaces(OldD, IsKnownNewer)) {
226
684k
        Data.setPointer(D);
227
684k
        return;
228
684k
      }
229
230
      // Add D after OldD.
231
1.68M
      ASTContext &C = D->getASTContext();
232
1.68M
      DeclListNode *Node = C.AllocateDeclListNode(OldD);
233
1.68M
      Node->Rest = D;
234
1.68M
      Data.setPointer(Node);
235
1.68M
      return;
236
2.37M
    }
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
4.15M
    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
26.2M
         
N = N->Rest.dyn_cast<DeclListNode *>()22.0M
) {
244
26.2M
      if (D->declarationReplaces(N->D, IsKnownNewer)) {
245
144k
        N->D = D;
246
144k
        return;
247
144k
      }
248
26.1M
      if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) {
249
4.01M
        if (D->declarationReplaces(ND, IsKnownNewer)) {
250
45.0k
          N->Rest = D;
251
45.0k
          return;
252
45.0k
        }
253
254
        // Add D after ND.
255
3.96M
        ASTContext &C = D->getASTContext();
256
3.96M
        DeclListNode *Node = C.AllocateDeclListNode(ND);
257
3.96M
        N->Rest = Node;
258
3.96M
        Node->Rest = D;
259
3.96M
        return;
260
4.01M
      }
261
26.1M
    }
262
4.15M
  }
263
264
  /// Add a declaration to the list without checking if it replaces anything.
265
3.49M
  void prependDeclNoReplace(NamedDecl *D) {
266
3.49M
    if (isNull()) {
267
2.35M
      Data.setPointer(D);
268
2.35M
      return;
269
2.35M
    }
270
271
1.14M
    ASTContext &C = D->getASTContext();
272
1.14M
    DeclListNode *Node = C.AllocateDeclListNode(D);
273
1.14M
    Node->Rest = Data.getPointer();
274
1.14M
    Data.setPointer(Node);
275
1.14M
  }
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
545k
  DependentStoredDeclsMap() = default;
313
};
314
315
} // namespace clang
316
317
#endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H