Coverage Report

Created: 2017-10-03 07:32

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