clang  8.0.0svn
CXXInheritance.h
Go to the documentation of this file.
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"
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.
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.
50 
51  /// The record decl of the class that the base is a base of.
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.
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.
77 
78  CXXBasePath() = default;
79 
80  /// The set of declarations found inside this base class
81  /// subobject.
83 
84  void clear() {
86  Access = AS_public;
87  }
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.
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,
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;
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  DetectVirtual(DetectVirtual) {}
191 
192  paths_iterator begin() { return Paths.begin(); }
193  paths_iterator end() { return Paths.end(); }
194  const_paths_iterator begin() const { return Paths.begin(); }
195  const_paths_iterator end() const { return Paths.end(); }
196 
197  CXXBasePath& front() { return Paths.front(); }
198  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  bool isFindingAmbiguities() const { return FindAmbiguities; }
211 
212  /// Whether we are recording paths.
213  bool isRecordingPaths() const { return RecordPaths; }
214 
215  /// Specify whether we should be recording paths or not.
216  void setRecordingPaths(bool RP) { RecordPaths = RP; }
217 
218  /// Whether we are detecting virtual bases.
219  bool isDetectingVirtual() const { return DetectVirtual; }
220 
221  /// The virtual base discovered on the path (if we are merely
222  /// detecting virtuals).
224  return DetectedVirtual;
225  }
226 
227  /// Retrieve the type from which this base-paths search
228  /// began
229  CXXRecordDecl *getOrigin() const { return Origin; }
230  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.
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  InVirtualSubobject(InVirtualSubobject) {}
261 
262  friend bool operator==(const UniqueVirtualMethod &X,
263  const UniqueVirtualMethod &Y) {
264  return X.Method == Y.Method && X.Subobject == Y.Subobject &&
266  }
267 
268  friend bool operator!=(const UniqueVirtualMethod &X,
269  const UniqueVirtualMethod &Y) {
270  return !(X == Y);
271  }
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).
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  iterator begin() { return Overrides.begin(); }
293  const_iterator begin() const { return Overrides.begin(); }
294  iterator end() { return Overrides.end(); }
295  const_iterator end() const { return Overrides.end(); }
296  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 =
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.
370  : public llvm::MapVector<const CXXMethodDecl *, OverridingMethods> {};
371 
372 /// A set of all the primary bases for a class.
374  : public llvm::SmallSet<const CXXRecordDecl*, 32> {};
375 
376 } // namespace clang
377 
378 #endif // LLVM_CLANG_AST_CXXINHERITANCE_H
void setOrigin(CXXRecordDecl *Rec)
llvm::iterator_range< decl_iterator > decl_range
C Language Family Type Representation.
SmallVectorImpl< UniqueVirtualMethod >::const_iterator overriding_const_iterator
virtual void clear()
AccessSpecifier
A C++ access specifier (public, private, protected), plus the special value "none" which means differ...
Definition: Specifiers.h:98
Represents a path from a specific derived class (which is not represented as part of the path) to a p...
std::list< CXXBasePath >::iterator paths_iterator
DeclContext::lookup_result Decls
The set of declarations found inside this base class subobject.
bool isRecordingPaths() const
Whether we are recording paths.
friend bool operator!=(const UniqueVirtualMethod &X, const UniqueVirtualMethod &Y)
void setRecordingPaths(bool RP)
Specify whether we should be recording paths or not.
bool isFindingAmbiguities() const
Whether we are finding multiple paths to detect ambiguities.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
The results of name lookup within a DeclContext.
Definition: DeclBase.h:1191
CXXMethodDecl * Method
The overriding virtual method.
The set of methods that override a given virtual method in each subobject where it occurs...
const_iterator end() const
const RecordType * getDetectedVirtual() const
The virtual base discovered on the path (if we are merely detecting virtuals).
const_paths_iterator end() const
UniqueVirtualMethod(CXXMethodDecl *Method, unsigned Subobject, const CXXRecordDecl *InVirtualSubobject)
Allows QualTypes to be sorted and hence used in maps and sets.
int SubobjectNumber
Identifies which base class subobject (of type Base->getType()) this base path element refers to...
Uniquely identifies a virtual method within a class hierarchy by the method itself and a class subobj...
llvm::function_ref< bool(const CXXBaseSpecifier *Specifier, CXXBasePath &Path)> BaseMatchesCallback
Function type used by lookupInBases() to determine whether a specific base class subobject matches th...
Definition: DeclCXX.h:1750
const CXXBaseSpecifier * Base
The base specifier that states the link from a derived class to a base class, which will be followed ...
A set of all the primary bases for a class.
Represents a static or instance method of a struct/union/class.
Definition: DeclCXX.h:2043
paths_iterator begin()
bool isDetectingVirtual() const
Whether we are detecting virtual bases.
const_paths_iterator begin() const
CXXRecordDecl * getOrigin() const
Retrieve the type from which this base-paths search began.
Defines various enumerations that describe declaration and type specifiers.
Represents an element in a path from a derived class to a base class.
const_iterator begin() const
std::list< CXXBasePath >::const_iterator const_paths_iterator
Dataflow Directional Tag Classes.
unsigned Subobject
The subobject in which the overriding virtual method resides.
MapType::iterator iterator
A mapping from each virtual member function to its set of final overriders.
A helper class that allows the use of isa/cast/dyncast to detect TagType objects of structs/unions/cl...
Definition: Type.h:4253
MapType::const_iterator const_iterator
friend bool operator==(const UniqueVirtualMethod &X, const UniqueVirtualMethod &Y)
CXXBasePath & front()
Represents a base class of a C++ class.
Definition: DeclCXX.h:192
CXXBasePaths(bool FindAmbiguities=true, bool RecordPaths=true, bool DetectVirtual=true)
BasePaths - Construct a new BasePaths structure to record the paths for a derived-to-base search...
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13824
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate.h) and friends (in DeclFriend.h).
Represents a C++ struct/union/class.
Definition: DeclCXX.h:300
SmallVectorImpl< UniqueVirtualMethod >::iterator overriding_iterator
const CXXBasePath & front() const
BasePaths - Represents the set of paths from a derived class to one of its (direct or indirect) bases...
const CXXRecordDecl * InVirtualSubobject
The virtual base class subobject of which this overridden virtual method is a part.
paths_iterator end()
This represents a decl that may have a name.
Definition: Decl.h:248
const CXXRecordDecl * Class
The record decl of the class that the base is a base of.