Coverage Report

Created: 2018-12-11 17:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/AST/CXXInheritance.h
Line
Count
Source (jump to first uncovered line)
1
//===- CXXInheritance.h - C++ Inheritance -----------------------*- C++ -*-===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This file provides routines that help analyzing C++ inheritance hierarchies.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_CLANG_AST_CXXINHERITANCE_H
15
#define LLVM_CLANG_AST_CXXINHERITANCE_H
16
17
#include "clang/AST/DeclBase.h"
18
#include "clang/AST/DeclCXX.h"
19
#include "clang/AST/DeclarationName.h"
20
#include "clang/AST/Type.h"
21
#include "clang/AST/TypeOrdering.h"
22
#include "clang/Basic/Specifiers.h"
23
#include "llvm/ADT/DenseMap.h"
24
#include "llvm/ADT/DenseSet.h"
25
#include "llvm/ADT/MapVector.h"
26
#include "llvm/ADT/SmallSet.h"
27
#include "llvm/ADT/SmallVector.h"
28
#include "llvm/ADT/iterator_range.h"
29
#include <list>
30
#include <memory>
31
#include <utility>
32
33
namespace clang {
34
35
class ASTContext;
36
class NamedDecl;
37
38
/// Represents an element in a path from a derived class to a
39
/// base class.
40
///
41
/// Each step in the path references the link from a
42
/// derived class to one of its direct base classes, along with a
43
/// base "number" that identifies which base subobject of the
44
/// original derived class we are referencing.
45
struct CXXBasePathElement {
46
  /// The base specifier that states the link from a derived
47
  /// class to a base class, which will be followed by this base
48
  /// path element.
49
  const CXXBaseSpecifier *Base;
50
51
  /// The record decl of the class that the base is a base of.
52
  const CXXRecordDecl *Class;
53
54
  /// Identifies which base class subobject (of type
55
  /// \c Base->getType()) this base path element refers to.
56
  ///
57
  /// This value is only valid if \c !Base->isVirtual(), because there
58
  /// is no base numbering for the zero or one virtual bases of a
59
  /// given type.
60
  int SubobjectNumber;
61
};
62
63
/// Represents a path from a specific derived class
64
/// (which is not represented as part of the path) to a particular
65
/// (direct or indirect) base class subobject.
66
///
67
/// Individual elements in the path are described by the \c CXXBasePathElement
68
/// structure, which captures both the link from a derived class to one of its
69
/// direct bases and identification describing which base class
70
/// subobject is being used.
71
class CXXBasePath : public SmallVector<CXXBasePathElement, 4> {
72
public:
73
  /// The access along this inheritance path.  This is only
74
  /// calculated when recording paths.  AS_none is a special value
75
  /// used to indicate a path which permits no legal access.
76
  AccessSpecifier Access = AS_public;
77
78
19.4M
  CXXBasePath() = default;
79
80
  /// The set of declarations found inside this base class
81
  /// subobject.
82
  DeclContext::lookup_result Decls;
83
84
47
  void clear() {
85
47
    SmallVectorImpl<CXXBasePathElement>::clear();
86
47
    Access = AS_public;
87
47
  }
88
};
89
90
/// BasePaths - Represents the set of paths from a derived class to
91
/// one of its (direct or indirect) bases. For example, given the
92
/// following class hierarchy:
93
///
94
/// @code
95
/// class A { };
96
/// class B : public A { };
97
/// class C : public A { };
98
/// class D : public B, public C{ };
99
/// @endcode
100
///
101
/// There are two potential BasePaths to represent paths from D to a
102
/// base subobject of type A. One path is (D,0) -> (B,0) -> (A,0)
103
/// and another is (D,0)->(C,0)->(A,1). These two paths actually
104
/// refer to two different base class subobjects of the same type,
105
/// so the BasePaths object refers to an ambiguous path. On the
106
/// other hand, consider the following class hierarchy:
107
///
108
/// @code
109
/// class A { };
110
/// class B : public virtual A { };
111
/// class C : public virtual A { };
112
/// class D : public B, public C{ };
113
/// @endcode
114
///
115
/// Here, there are two potential BasePaths again, (D, 0) -> (B, 0)
116
/// -> (A,v) and (D, 0) -> (C, 0) -> (A, v), but since both of them
117
/// refer to the same base class subobject of type A (the virtual
118
/// one), there is no ambiguity.
119
class CXXBasePaths {
120
  friend class CXXRecordDecl;
121
122
  /// The type from which this search originated.
123
  CXXRecordDecl *Origin = nullptr;
124
125
  /// Paths - The actual set of paths that can be taken from the
126
  /// derived class to the same base class.
127
  std::list<CXXBasePath> Paths;
128
129
  /// ClassSubobjects - Records the class subobjects for each class
130
  /// type that we've seen. The first element IsVirtBase says
131
  /// whether we found a path to a virtual base for that class type,
132
  /// while NumberOfNonVirtBases contains the number of non-virtual base
133
  /// class subobjects for that class type. The key of the map is
134
  /// the cv-unqualified canonical type of the base class subobject.
135
  struct IsVirtBaseAndNumberNonVirtBases {
136
    unsigned IsVirtBase : 1;
137
    unsigned NumberOfNonVirtBases : 31;
138
  };
139
  llvm::SmallDenseMap<QualType, IsVirtBaseAndNumberNonVirtBases, 8>
140
      ClassSubobjects;
141
142
  /// VisitedDependentRecords - Records the dependent records that have been
143
  /// already visited.
144
  llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedDependentRecords;
145
146
  /// DetectedVirtual - The base class that is virtual.
147
  const RecordType *DetectedVirtual = nullptr;
148
149
  /// ScratchPath - A BasePath that is used by Sema::lookupInBases
150
  /// to help build the set of paths.
151
  CXXBasePath ScratchPath;
152
153
  /// Array of the declarations that have been found. This
154
  /// array is constructed only if needed, e.g., to iterate over the
155
  /// results within LookupResult.
156
  std::unique_ptr<NamedDecl *[]> DeclsFound;
157
  unsigned NumDeclsFound = 0;
158
159
  /// FindAmbiguities - Whether Sema::IsDerivedFrom should try find
160
  /// ambiguous paths while it is looking for a path from a derived
161
  /// type to a base type.
162
  bool FindAmbiguities;
163
164
  /// RecordPaths - Whether Sema::IsDerivedFrom should record paths
165
  /// while it is determining whether there are paths from a derived
166
  /// type to a base type.
167
  bool RecordPaths;
168
169
  /// DetectVirtual - Whether Sema::IsDerivedFrom should abort the search
170
  /// if it finds a path that goes across a virtual base. The virtual class
171
  /// is also recorded.
172
  bool DetectVirtual;
173
174
  void ComputeDeclsFound();
175
176
  bool lookupInBases(ASTContext &Context, const CXXRecordDecl *Record,
177
                     CXXRecordDecl::BaseMatchesCallback BaseMatches,
178
                     bool LookupInDependent = false);
179
180
public:
181
  using paths_iterator = std::list<CXXBasePath>::iterator;
182
  using const_paths_iterator = std::list<CXXBasePath>::const_iterator;
183
  using decl_iterator = NamedDecl **;
184
185
  /// BasePaths - Construct a new BasePaths structure to record the
186
  /// paths for a derived-to-base search.
187
  explicit CXXBasePaths(bool FindAmbiguities = true, bool RecordPaths = true,
188
                        bool DetectVirtual = true)
189
      : FindAmbiguities(FindAmbiguities), RecordPaths(RecordPaths),
190
19.4M
        DetectVirtual(DetectVirtual) {}
191
192
1.31M
  paths_iterator begin() { return Paths.begin(); }
193
1.34M
  paths_iterator end()   { return Paths.end(); }
194
115
  const_paths_iterator begin() const { return Paths.begin(); }
195
115
  const_paths_iterator end()   const { return Paths.end(); }
196
197
1.35M
  CXXBasePath&       front()       { return Paths.front(); }
198
4.84k
  const CXXBasePath& front() const { return Paths.front(); }
199
200
  using decl_range = llvm::iterator_range<decl_iterator>;
201
202
  decl_range found_decls();
203
204
  /// Determine whether the path from the most-derived type to the
205
  /// given base type is ambiguous (i.e., it refers to multiple subobjects of
206
  /// the same base type).
207
  bool isAmbiguous(CanQualType BaseType);
208
209
  /// Whether we are finding multiple paths to detect ambiguities.
210
2.26M
  bool isFindingAmbiguities() const { return FindAmbiguities; }
211
212
  /// Whether we are recording paths.
213
16.0M
  bool isRecordingPaths() const { return RecordPaths; }
214
215
  /// Specify whether we should be recording paths or not.
216
47
  void setRecordingPaths(bool RP) { RecordPaths = RP; }
217
218
  /// Whether we are detecting virtual bases.
219
106k
  bool isDetectingVirtual() const { return DetectVirtual; }
220
221
  /// The virtual base discovered on the path (if we are merely
222
  /// detecting virtuals).
223
4.91k
  const RecordType* getDetectedVirtual() const {
224
4.91k
    return DetectedVirtual;
225
4.91k
  }
226
227
  /// Retrieve the type from which this base-paths search
228
  /// began
229
725
  CXXRecordDecl *getOrigin() const { return Origin; }
230
14.1M
  void setOrigin(CXXRecordDecl *Rec) { Origin = Rec; }
231
232
  /// Clear the base-paths results.
233
  void clear();
234
235
  /// Swap this data structure's contents with another CXXBasePaths
236
  /// object.
237
  void swap(CXXBasePaths &Other);
238
};
239
240
/// Uniquely identifies a virtual method within a class
241
/// hierarchy by the method itself and a class subobject number.
242
struct UniqueVirtualMethod {
243
  /// The overriding virtual method.
244
  CXXMethodDecl *Method = nullptr;
245
246
  /// The subobject in which the overriding virtual method
247
  /// resides.
248
  unsigned Subobject = 0;
249
250
  /// The virtual base class subobject of which this overridden
251
  /// virtual method is a part. Note that this records the closest
252
  /// derived virtual base class subobject.
253
  const CXXRecordDecl *InVirtualSubobject = nullptr;
254
255
  UniqueVirtualMethod() = default;
256
257
  UniqueVirtualMethod(CXXMethodDecl *Method, unsigned Subobject,
258
                      const CXXRecordDecl *InVirtualSubobject)
259
      : Method(Method), Subobject(Subobject),
260
378k
        InVirtualSubobject(InVirtualSubobject) {}
261
262
  friend bool operator==(const UniqueVirtualMethod &X,
263
1.65k
                         const UniqueVirtualMethod &Y) {
264
1.65k
    return X.Method == Y.Method && 
X.Subobject == Y.Subobject192
&&
265
1.65k
      
X.InVirtualSubobject == Y.InVirtualSubobject185
;
266
1.65k
  }
267
268
  friend bool operator!=(const UniqueVirtualMethod &X,
269
0
                         const UniqueVirtualMethod &Y) {
270
0
    return !(X == Y);
271
0
  }
272
};
273
274
/// The set of methods that override a given virtual method in
275
/// each subobject where it occurs.
276
///
277
/// The first part of the pair is the subobject in which the
278
/// overridden virtual function occurs, while the second part of the
279
/// pair is the virtual method that overrides it (including the
280
/// subobject in which that virtual function occurs).
281
class OverridingMethods {
282
  using ValuesT = SmallVector<UniqueVirtualMethod, 4>;
283
  using MapType = llvm::MapVector<unsigned, ValuesT>;
284
285
  MapType Overrides;
286
287
public:
288
  // Iterate over the set of subobjects that have overriding methods.
289
  using iterator = MapType::iterator;
290
  using const_iterator = MapType::const_iterator;
291
292
480k
  iterator begin() { return Overrides.begin(); }
293
158k
  const_iterator begin() const { return Overrides.begin(); }
294
480k
  iterator end() { return Overrides.end(); }
295
158k
  const_iterator end() const { return Overrides.end(); }
296
0
  unsigned size() const { return Overrides.size(); }
297
298
  // Iterate over the set of overriding virtual methods in a given
299
  // subobject.
300
  using overriding_iterator =
301
      SmallVectorImpl<UniqueVirtualMethod>::iterator;
302
  using overriding_const_iterator =
303
      SmallVectorImpl<UniqueVirtualMethod>::const_iterator;
304
305
  // Add a new overriding method for a particular subobject.
306
  void add(unsigned OverriddenSubobject, UniqueVirtualMethod Overriding);
307
308
  // Add all of the overriding methods from "other" into overrides for
309
  // this method. Used when merging the overrides from multiple base
310
  // class subobjects.
311
  void add(const OverridingMethods &Other);
312
313
  // Replace all overriding virtual methods in all subobjects with the
314
  // given virtual method.
315
  void replaceAll(UniqueVirtualMethod Overriding);
316
};
317
318
/// A mapping from each virtual member function to its set of
319
/// final overriders.
320
///
321
/// Within a class hierarchy for a given derived class, each virtual
322
/// member function in that hierarchy has one or more "final
323
/// overriders" (C++ [class.virtual]p2). A final overrider for a
324
/// virtual function "f" is the virtual function that will actually be
325
/// invoked when dispatching a call to "f" through the
326
/// vtable. Well-formed classes have a single final overrider for each
327
/// virtual function; in abstract classes, the final overrider for at
328
/// least one virtual function is a pure virtual function. Due to
329
/// multiple, virtual inheritance, it is possible for a class to have
330
/// more than one final overrider. Athough this is an error (per C++
331
/// [class.virtual]p2), it is not considered an error here: the final
332
/// overrider map can represent multiple final overriders for a
333
/// method, and it is up to the client to determine whether they are
334
/// problem. For example, the following class \c D has two final
335
/// overriders for the virtual function \c A::f(), one in \c C and one
336
/// in \c D:
337
///
338
/// \code
339
///   struct A { virtual void f(); };
340
///   struct B : virtual A { virtual void f(); };
341
///   struct C : virtual A { virtual void f(); };
342
///   struct D : B, C { };
343
/// \endcode
344
///
345
/// This data structure contains a mapping from every virtual
346
/// function *that does not override an existing virtual function* and
347
/// in every subobject where that virtual function occurs to the set
348
/// of virtual functions that override it. Thus, the same virtual
349
/// function \c A::f can actually occur in multiple subobjects of type
350
/// \c A due to multiple inheritance, and may be overridden by
351
/// different virtual functions in each, as in the following example:
352
///
353
/// \code
354
///   struct A { virtual void f(); };
355
///   struct B : A { virtual void f(); };
356
///   struct C : A { virtual void f(); };
357
///   struct D : B, C { };
358
/// \endcode
359
///
360
/// Unlike in the previous example, where the virtual functions \c
361
/// B::f and \c C::f both overrode \c A::f in the same subobject of
362
/// type \c A, in this example the two virtual functions both override
363
/// \c A::f but in *different* subobjects of type A. This is
364
/// represented by numbering the subobjects in which the overridden
365
/// and the overriding virtual member functions are located. Subobject
366
/// 0 represents the virtual base class subobject of that type, while
367
/// subobject numbers greater than 0 refer to non-virtual base class
368
/// subobjects of that type.
369
class CXXFinalOverriderMap
370
  : public llvm::MapVector<const CXXMethodDecl *, OverridingMethods> {};
371
372
/// A set of all the primary bases for a class.
373
class CXXIndirectPrimaryBaseSet
374
  : public llvm::SmallSet<const CXXRecordDecl*, 32> {};
375
376
} // namespace clang
377
378
#endif // LLVM_CLANG_AST_CXXINHERITANCE_H