Coverage Report

Created: 2022-01-25 06:29

/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
1.79M
  void erase_if(Fn ShouldErase) {
47
1.79M
    Decls List = Data.getPointer();
48
1.79M
    if (!List)
49
1.21M
      return;
50
574k
    ASTContext &C = getASTContext();
51
574k
    DeclListNode::Decls NewHead = nullptr;
52
574k
    DeclListNode::Decls *NewLast = nullptr;
53
574k
    DeclListNode::Decls *NewTail = &NewHead;
54
889k
    while (true) {
55
889k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
102k
        NewLast = NewTail;
57
102k
        *NewTail = List;
58
102k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
8.48k
          NewTail = &Node->Rest;
60
8.48k
          List = Node->Rest;
61
94.4k
        } else {
62
94.4k
          break;
63
94.4k
        }
64
786k
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
306k
        List = N->Rest;
66
306k
        C.DeallocateDeclListNode(N);
67
479k
      } 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
479k
        if (NewLast) {
72
256
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
256
          *NewLast = Node->D;
74
256
          C.DeallocateDeclListNode(Node);
75
256
        }
76
479k
        break;
77
479k
      }
78
889k
    }
79
574k
    Data.setPointer(NewHead);
80
81
574k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
574k
  }
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
26.6k
  void erase_if(Fn ShouldErase) {
47
26.6k
    Decls List = Data.getPointer();
48
26.6k
    if (!List)
49
0
      return;
50
26.6k
    ASTContext &C = getASTContext();
51
26.6k
    DeclListNode::Decls NewHead = nullptr;
52
26.6k
    DeclListNode::Decls *NewLast = nullptr;
53
26.6k
    DeclListNode::Decls *NewTail = &NewHead;
54
28.6k
    while (true) {
55
28.6k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
2.04k
        NewLast = NewTail;
57
2.04k
        *NewTail = List;
58
2.04k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
1.78k
          NewTail = &Node->Rest;
60
1.78k
          List = Node->Rest;
61
1.78k
        } else {
62
265
          break;
63
265
        }
64
26.6k
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
264
        List = N->Rest;
66
264
        C.DeallocateDeclListNode(N);
67
26.3k
      } 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
26.3k
        if (NewLast) {
72
54
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
54
          *NewLast = Node->D;
74
54
          C.DeallocateDeclListNode(Node);
75
54
        }
76
26.3k
        break;
77
26.3k
      }
78
28.6k
    }
79
26.6k
    Data.setPointer(NewHead);
80
81
26.6k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
26.6k
  }
void clang::StoredDeclsList::erase_if<clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*)>(clang::StoredDeclsList::removeExternalDecls()::'lambda'(clang::NamedDecl*))
Line
Count
Source
46
398k
  void erase_if(Fn ShouldErase) {
47
398k
    Decls List = Data.getPointer();
48
398k
    if (!List)
49
397k
      return;
50
1.14k
    ASTContext &C = getASTContext();
51
1.14k
    DeclListNode::Decls NewHead = nullptr;
52
1.14k
    DeclListNode::Decls *NewLast = nullptr;
53
1.14k
    DeclListNode::Decls *NewTail = &NewHead;
54
5.48k
    while (true) {
55
5.48k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
5.48k
        NewLast = NewTail;
57
5.48k
        *NewTail = List;
58
5.48k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
4.33k
          NewTail = &Node->Rest;
60
4.33k
          List = Node->Rest;
61
4.33k
        } else {
62
1.14k
          break;
63
1.14k
        }
64
5.48k
      } 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.48k
    }
79
1.14k
    Data.setPointer(NewHead);
80
81
1.14k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
1.14k
  }
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.36M
  void erase_if(Fn ShouldErase) {
47
1.36M
    Decls List = Data.getPointer();
48
1.36M
    if (!List)
49
817k
      return;
50
546k
    ASTContext &C = getASTContext();
51
546k
    DeclListNode::Decls NewHead = nullptr;
52
546k
    DeclListNode::Decls *NewLast = nullptr;
53
546k
    DeclListNode::Decls *NewTail = &NewHead;
54
854k
    while (true) {
55
854k
      if (!ShouldErase(*DeclListNode::iterator(List))) {
56
95.4k
        NewLast = NewTail;
57
95.4k
        *NewTail = List;
58
95.4k
        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
59
2.35k
          NewTail = &Node->Rest;
60
2.35k
          List = Node->Rest;
61
93.0k
        } else {
62
93.0k
          break;
63
93.0k
        }
64
759k
      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
65
305k
        List = N->Rest;
66
305k
        C.DeallocateDeclListNode(N);
67
453k
      } 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
453k
        if (NewLast) {
72
202
          DeclListNode *Node = NewLast->get<DeclListNode*>();
73
202
          *NewLast = Node->D;
74
202
          C.DeallocateDeclListNode(Node);
75
202
        }
76
453k
        break;
77
453k
      }
78
854k
    }
79
546k
    Data.setPointer(NewHead);
80
81
546k
    assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
82
546k
  }
83
84
26.6k
  void erase(NamedDecl *ND) {
85
30.7k
    erase_if([ND](NamedDecl *D) { return D == ND; });
86
26.6k
  }
87
88
public:
89
25.9M
  StoredDeclsList() = default;
90
91
27.2M
  StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
92
27.2M
    RHS.Data.setPointer(nullptr);
93
27.2M
    RHS.Data.setInt(false);
94
27.2M
  }
95
96
53.2M
  void MaybeDeallocList() {
97
53.2M
    if (isNull())
98
34.2M
      return;
99
    // If this is a list-form, free the list.
100
18.9M
    ASTContext &C = getASTContext();
101
18.9M
    Decls List = Data.getPointer();
102
25.0M
    while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) {
103
6.06M
      List = ToDealloc->Rest;
104
6.06M
      C.DeallocateDeclListNode(ToDealloc);
105
6.06M
    }
106
18.9M
  }
107
108
53.2M
  ~StoredDeclsList() {
109
53.2M
    MaybeDeallocList();
110
53.2M
  }
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
98.3M
  bool isNull() const { return Data.getPointer().isNull(); }
122
123
19.5M
  ASTContext &getASTContext() {
124
19.5M
    assert(!isNull() && "No ASTContext.");
125
19.5M
    if (NamedDecl *ND = getAsDecl())
126
17.6M
      return ND->getASTContext();
127
1.89M
    return getAsList()->D->getASTContext();
128
19.5M
  }
129
130
38.8M
  DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; }
131
132
25.4M
  NamedDecl *getAsDecl() const {
133
25.4M
    return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>();
134
25.4M
  }
135
136
5.78M
  DeclListNode *getAsList() const {
137
5.78M
    return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>();
138
5.78M
  }
139
140
7.55M
  bool hasExternalDecls() const {
141
7.55M
    return getAsListAndHasExternal().getInt();
142
7.55M
  }
143
144
3.31M
  void setHasExternalDecls() {
145
3.31M
    Data.setInt(true);
146
3.31M
  }
147
148
26.6k
  void remove(NamedDecl *D) {
149
26.6k
    assert(!isNull() && "removing from empty list");
150
0
    erase(D);
151
26.6k
  }
152
153
  /// Remove any declarations which were imported from an external AST source.
154
398k
  void removeExternalDecls() {
155
398k
    erase_if([](NamedDecl *ND) 
{ return ND->isFromASTFile(); }10.9k
);
156
157
    // Don't have any pending external decls any more.
158
398k
    Data.setInt(false);
159
398k
  }
160
161
1.36M
  void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) {
162
    // Remove all declarations that are either external or are replaced with
163
    // external declarations.
164
1.36M
    erase_if([Decls](NamedDecl *ND) {
165
950k
      if (ND->isFromASTFile())
166
746k
        return true;
167
203k
      for (NamedDecl *D : Decls)
168
21.5k
        if (D->declarationReplaces(ND, /*IsKnownNewer=*/false))
169
12.5k
          return true;
170
190k
      return false;
171
203k
    });
172
173
    // Don't have any pending external decls any more.
174
1.36M
    Data.setInt(false);
175
176
1.36M
    if (Decls.empty())
177
839k
      return;
178
179
    // Convert Decls into a list, in order.
180
524k
    ASTContext &C = Decls.front()->getASTContext();
181
524k
    DeclListNode::Decls DeclsAsList = Decls.back();
182
882k
    for (size_t I = Decls.size() - 1; I != 0; 
--I357k
) {
183
357k
      DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]);
184
357k
      Node->Rest = DeclsAsList;
185
357k
      DeclsAsList = Node;
186
357k
    }
187
188
524k
    DeclListNode::Decls Head = Data.getPointer();
189
524k
    if (Head.isNull()) {
190
523k
      Data.setPointer(DeclsAsList);
191
523k
      return;
192
523k
    }
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.07k
    DeclListNode::Decls *Tail = &Head;
198
1.15k
    while (DeclListNode *Node = Tail->dyn_cast<DeclListNode *>())
199
82
      Tail = &Node->Rest;
200
201
    // Append the Decls.
202
1.07k
    DeclListNode *Node = C.AllocateDeclListNode(Tail->get<NamedDecl *>());
203
1.07k
    Node->Rest = DeclsAsList;
204
1.07k
    *Tail = Node;
205
1.07k
    Data.setPointer(Head);
206
1.07k
  }
207
208
  /// Return an array of all the decls that this list represents.
209
89.2M
  DeclContext::lookup_result getLookupResult() const {
210
89.2M
    return DeclContext::lookup_result(Data.getPointer());
211
89.2M
  }
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.94M
    if (NamedDecl *OldD = getAsDecl()) {
225
2.05M
      if (D->declarationReplaces(OldD, IsKnownNewer)) {
226
502k
        Data.setPointer(D);
227
502k
        return;
228
502k
      }
229
230
      // Add D after OldD.
231
1.55M
      ASTContext &C = D->getASTContext();
232
1.55M
      DeclListNode *Node = C.AllocateDeclListNode(OldD);
233
1.55M
      Node->Rest = D;
234
1.55M
      Data.setPointer(Node);
235
1.55M
      return;
236
2.05M
    }
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.88M
    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.5M
         
N = N->Rest.dyn_cast<DeclListNode *>()20.6M
) {
244
24.5M
      if (D->declarationReplaces(N->D, IsKnownNewer)) {
245
106k
        N->D = D;
246
106k
        return;
247
106k
      }
248
24.4M
      if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) {
249
3.78M
        if (D->declarationReplaces(ND, IsKnownNewer)) {
250
33.9k
          N->Rest = D;
251
33.9k
          return;
252
33.9k
        }
253
254
        // Add D after ND.
255
3.74M
        ASTContext &C = D->getASTContext();
256
3.74M
        DeclListNode *Node = C.AllocateDeclListNode(ND);
257
3.74M
        N->Rest = Node;
258
3.74M
        Node->Rest = D;
259
3.74M
        return;
260
3.78M
      }
261
24.4M
    }
262
3.88M
  }
263
264
  /// Add a declaration to the list without checking if it replaces anything.
265
2.20M
  void prependDeclNoReplace(NamedDecl *D) {
266
2.20M
    if (isNull()) {
267
1.49M
      Data.setPointer(D);
268
1.49M
      return;
269
1.49M
    }
270
271
713k
    ASTContext &C = D->getASTContext();
272
713k
    DeclListNode *Node = C.AllocateDeclListNode(D);
273
713k
    Node->Rest = Data.getPointer();
274
713k
    Data.setPointer(Node);
275
713k
  }
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
449k
  DependentStoredDeclsMap() = default;
313
};
314
315
} // namespace clang
316
317
#endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H