CXXInheritance.h revision 327952
1327952Sdim//===- CXXInheritance.h - C++ Inheritance -----------------------*- C++ -*-===// 2198092Srdivacky// 3198092Srdivacky// The LLVM Compiler Infrastructure 4198092Srdivacky// 5198092Srdivacky// This file is distributed under the University of Illinois Open Source 6198092Srdivacky// License. See LICENSE.TXT for details. 7198092Srdivacky// 8198092Srdivacky//===----------------------------------------------------------------------===// 9198092Srdivacky// 10198092Srdivacky// This file provides routines that help analyzing C++ inheritance hierarchies. 11198092Srdivacky// 12198092Srdivacky//===----------------------------------------------------------------------===// 13198092Srdivacky 14198092Srdivacky#ifndef LLVM_CLANG_AST_CXXINHERITANCE_H 15198092Srdivacky#define LLVM_CLANG_AST_CXXINHERITANCE_H 16198092Srdivacky 17198092Srdivacky#include "clang/AST/DeclBase.h" 18204643Srdivacky#include "clang/AST/DeclCXX.h" 19327952Sdim#include "clang/AST/DeclarationName.h" 20198092Srdivacky#include "clang/AST/Type.h" 21198092Srdivacky#include "clang/AST/TypeOrdering.h" 22327952Sdim#include "clang/Basic/Specifiers.h" 23327952Sdim#include "llvm/ADT/DenseMap.h" 24327952Sdim#include "llvm/ADT/DenseSet.h" 25243830Sdim#include "llvm/ADT/MapVector.h" 26218893Sdim#include "llvm/ADT/SmallSet.h" 27198092Srdivacky#include "llvm/ADT/SmallVector.h" 28327952Sdim#include "llvm/ADT/iterator_range.h" 29198092Srdivacky#include <list> 30327952Sdim#include <memory> 31327952Sdim#include <utility> 32198092Srdivacky 33198092Srdivackynamespace clang { 34327952Sdim 35327952Sdimclass ASTContext; 36198092Srdivackyclass NamedDecl; 37198092Srdivacky 38198092Srdivacky/// \brief Represents an element in a path from a derived class to a 39198092Srdivacky/// base class. 40198092Srdivacky/// 41198092Srdivacky/// Each step in the path references the link from a 42198092Srdivacky/// derived class to one of its direct base classes, along with a 43198092Srdivacky/// base "number" that identifies which base subobject of the 44198092Srdivacky/// original derived class we are referencing. 45198092Srdivackystruct CXXBasePathElement { 46198092Srdivacky /// \brief The base specifier that states the link from a derived 47198092Srdivacky /// class to a base class, which will be followed by this base 48198092Srdivacky /// path element. 49198092Srdivacky const CXXBaseSpecifier *Base; 50198092Srdivacky 51198092Srdivacky /// \brief The record decl of the class that the base is a base of. 52198092Srdivacky const CXXRecordDecl *Class; 53198092Srdivacky 54198092Srdivacky /// \brief Identifies which base class subobject (of type 55198092Srdivacky /// \c Base->getType()) this base path element refers to. 56198092Srdivacky /// 57198092Srdivacky /// This value is only valid if \c !Base->isVirtual(), because there 58198092Srdivacky /// is no base numbering for the zero or one virtual bases of a 59198092Srdivacky /// given type. 60198092Srdivacky int SubobjectNumber; 61198092Srdivacky}; 62198092Srdivacky 63198092Srdivacky/// \brief Represents a path from a specific derived class 64198092Srdivacky/// (which is not represented as part of the path) to a particular 65198092Srdivacky/// (direct or indirect) base class subobject. 66198092Srdivacky/// 67198092Srdivacky/// Individual elements in the path are described by the \c CXXBasePathElement 68198092Srdivacky/// structure, which captures both the link from a derived class to one of its 69198092Srdivacky/// direct bases and identification describing which base class 70198092Srdivacky/// subobject is being used. 71226633Sdimclass CXXBasePath : public SmallVector<CXXBasePathElement, 4> { 72198398Srdivackypublic: 73202879Srdivacky /// \brief The access along this inheritance path. This is only 74202879Srdivacky /// calculated when recording paths. AS_none is a special value 75202879Srdivacky /// used to indicate a path which permits no legal access. 76327952Sdim AccessSpecifier Access = AS_public; 77202879Srdivacky 78327952Sdim CXXBasePath() = default; 79327952Sdim 80198092Srdivacky /// \brief The set of declarations found inside this base class 81198092Srdivacky /// subobject. 82198092Srdivacky DeclContext::lookup_result Decls; 83202879Srdivacky 84202879Srdivacky void clear() { 85226633Sdim SmallVectorImpl<CXXBasePathElement>::clear(); 86202879Srdivacky Access = AS_public; 87202879Srdivacky } 88198092Srdivacky}; 89198092Srdivacky 90198092Srdivacky/// BasePaths - Represents the set of paths from a derived class to 91198092Srdivacky/// one of its (direct or indirect) bases. For example, given the 92221345Sdim/// following class hierarchy: 93198092Srdivacky/// 94198092Srdivacky/// @code 95198092Srdivacky/// class A { }; 96198092Srdivacky/// class B : public A { }; 97198092Srdivacky/// class C : public A { }; 98198092Srdivacky/// class D : public B, public C{ }; 99198092Srdivacky/// @endcode 100198092Srdivacky/// 101198092Srdivacky/// There are two potential BasePaths to represent paths from D to a 102198092Srdivacky/// base subobject of type A. One path is (D,0) -> (B,0) -> (A,0) 103198092Srdivacky/// and another is (D,0)->(C,0)->(A,1). These two paths actually 104198092Srdivacky/// refer to two different base class subobjects of the same type, 105198092Srdivacky/// so the BasePaths object refers to an ambiguous path. On the 106198092Srdivacky/// other hand, consider the following class hierarchy: 107198092Srdivacky/// 108198092Srdivacky/// @code 109198092Srdivacky/// class A { }; 110198092Srdivacky/// class B : public virtual A { }; 111198092Srdivacky/// class C : public virtual A { }; 112198092Srdivacky/// class D : public B, public C{ }; 113198092Srdivacky/// @endcode 114198092Srdivacky/// 115198092Srdivacky/// Here, there are two potential BasePaths again, (D, 0) -> (B, 0) 116198092Srdivacky/// -> (A,v) and (D, 0) -> (C, 0) -> (A, v), but since both of them 117198092Srdivacky/// refer to the same base class subobject of type A (the virtual 118198092Srdivacky/// one), there is no ambiguity. 119198092Srdivackyclass CXXBasePaths { 120327952Sdim friend class CXXRecordDecl; 121327952Sdim 122198092Srdivacky /// \brief The type from which this search originated. 123327952Sdim CXXRecordDecl *Origin = nullptr; 124198092Srdivacky 125198092Srdivacky /// Paths - The actual set of paths that can be taken from the 126198092Srdivacky /// derived class to the same base class. 127198092Srdivacky std::list<CXXBasePath> Paths; 128198092Srdivacky 129198092Srdivacky /// ClassSubobjects - Records the class subobjects for each class 130198092Srdivacky /// type that we've seen. The first element in the pair says 131198092Srdivacky /// whether we found a path to a virtual base for that class type, 132198092Srdivacky /// while the element contains the number of non-virtual base 133198092Srdivacky /// class subobjects for that class type. The key of the map is 134198092Srdivacky /// the cv-unqualified canonical type of the base class subobject. 135239462Sdim llvm::SmallDenseMap<QualType, std::pair<bool, unsigned>, 8> ClassSubobjects; 136321369Sdim 137321369Sdim /// VisitedDependentRecords - Records the dependent records that have been 138321369Sdim /// already visited. 139321369Sdim llvm::SmallDenseSet<const CXXRecordDecl *, 4> VisitedDependentRecords; 140321369Sdim 141198092Srdivacky /// FindAmbiguities - Whether Sema::IsDerivedFrom should try find 142198092Srdivacky /// ambiguous paths while it is looking for a path from a derived 143198092Srdivacky /// type to a base type. 144198092Srdivacky bool FindAmbiguities; 145198092Srdivacky 146198092Srdivacky /// RecordPaths - Whether Sema::IsDerivedFrom should record paths 147198092Srdivacky /// while it is determining whether there are paths from a derived 148198092Srdivacky /// type to a base type. 149198092Srdivacky bool RecordPaths; 150198092Srdivacky 151198092Srdivacky /// DetectVirtual - Whether Sema::IsDerivedFrom should abort the search 152198092Srdivacky /// if it finds a path that goes across a virtual base. The virtual class 153198092Srdivacky /// is also recorded. 154198092Srdivacky bool DetectVirtual; 155198092Srdivacky 156202879Srdivacky /// ScratchPath - A BasePath that is used by Sema::lookupInBases 157198092Srdivacky /// to help build the set of paths. 158198092Srdivacky CXXBasePath ScratchPath; 159202879Srdivacky 160198092Srdivacky /// DetectedVirtual - The base class that is virtual. 161327952Sdim const RecordType *DetectedVirtual = nullptr; 162198092Srdivacky 163198092Srdivacky /// \brief Array of the declarations that have been found. This 164198092Srdivacky /// array is constructed only if needed, e.g., to iterate over the 165198092Srdivacky /// results within LookupResult. 166296417Sdim std::unique_ptr<NamedDecl *[]> DeclsFound; 167327952Sdim unsigned NumDeclsFound = 0; 168198092Srdivacky 169198092Srdivacky void ComputeDeclsFound(); 170204643Srdivacky 171296417Sdim bool lookupInBases(ASTContext &Context, const CXXRecordDecl *Record, 172321369Sdim CXXRecordDecl::BaseMatchesCallback BaseMatches, 173321369Sdim bool LookupInDependent = false); 174296417Sdim 175198092Srdivackypublic: 176327952Sdim using paths_iterator = std::list<CXXBasePath>::iterator; 177327952Sdim using const_paths_iterator = std::list<CXXBasePath>::const_iterator; 178327952Sdim using decl_iterator = NamedDecl **; 179198092Srdivacky 180198092Srdivacky /// BasePaths - Construct a new BasePaths structure to record the 181198092Srdivacky /// paths for a derived-to-base search. 182296417Sdim explicit CXXBasePaths(bool FindAmbiguities = true, bool RecordPaths = true, 183198092Srdivacky bool DetectVirtual = true) 184327952Sdim : FindAmbiguities(FindAmbiguities), RecordPaths(RecordPaths), 185327952Sdim DetectVirtual(DetectVirtual) {} 186296417Sdim 187203955Srdivacky paths_iterator begin() { return Paths.begin(); } 188203955Srdivacky paths_iterator end() { return Paths.end(); } 189203955Srdivacky const_paths_iterator begin() const { return Paths.begin(); } 190203955Srdivacky const_paths_iterator end() const { return Paths.end(); } 191198092Srdivacky 192198092Srdivacky CXXBasePath& front() { return Paths.front(); } 193198092Srdivacky const CXXBasePath& front() const { return Paths.front(); } 194198092Srdivacky 195327952Sdim using decl_range = llvm::iterator_range<decl_iterator>; 196327952Sdim 197276479Sdim decl_range found_decls(); 198198092Srdivacky 199198092Srdivacky /// \brief Determine whether the path from the most-derived type to the 200198092Srdivacky /// given base type is ambiguous (i.e., it refers to multiple subobjects of 201198092Srdivacky /// the same base type). 202208600Srdivacky bool isAmbiguous(CanQualType BaseType); 203198092Srdivacky 204198092Srdivacky /// \brief Whether we are finding multiple paths to detect ambiguities. 205198092Srdivacky bool isFindingAmbiguities() const { return FindAmbiguities; } 206198092Srdivacky 207198092Srdivacky /// \brief Whether we are recording paths. 208198092Srdivacky bool isRecordingPaths() const { return RecordPaths; } 209198092Srdivacky 210198092Srdivacky /// \brief Specify whether we should be recording paths or not. 211198092Srdivacky void setRecordingPaths(bool RP) { RecordPaths = RP; } 212198092Srdivacky 213198092Srdivacky /// \brief Whether we are detecting virtual bases. 214198092Srdivacky bool isDetectingVirtual() const { return DetectVirtual; } 215198092Srdivacky 216198092Srdivacky /// \brief The virtual base discovered on the path (if we are merely 217198092Srdivacky /// detecting virtuals). 218198092Srdivacky const RecordType* getDetectedVirtual() const { 219198092Srdivacky return DetectedVirtual; 220198092Srdivacky } 221203955Srdivacky 222198092Srdivacky /// \brief Retrieve the type from which this base-paths search 223198092Srdivacky /// began 224198092Srdivacky CXXRecordDecl *getOrigin() const { return Origin; } 225198092Srdivacky void setOrigin(CXXRecordDecl *Rec) { Origin = Rec; } 226198092Srdivacky 227198092Srdivacky /// \brief Clear the base-paths results. 228198092Srdivacky void clear(); 229198092Srdivacky 230198092Srdivacky /// \brief Swap this data structure's contents with another CXXBasePaths 231198092Srdivacky /// object. 232198092Srdivacky void swap(CXXBasePaths &Other); 233198092Srdivacky}; 234206084Srdivacky 235206084Srdivacky/// \brief Uniquely identifies a virtual method within a class 236206084Srdivacky/// hierarchy by the method itself and a class subobject number. 237206084Srdivackystruct UniqueVirtualMethod { 238206084Srdivacky /// \brief The overriding virtual method. 239327952Sdim CXXMethodDecl *Method = nullptr; 240206084Srdivacky 241206084Srdivacky /// \brief The subobject in which the overriding virtual method 242206084Srdivacky /// resides. 243327952Sdim unsigned Subobject = 0; 244206084Srdivacky 245206084Srdivacky /// \brief The virtual base class subobject of which this overridden 246206084Srdivacky /// virtual method is a part. Note that this records the closest 247206084Srdivacky /// derived virtual base class subobject. 248327952Sdim const CXXRecordDecl *InVirtualSubobject = nullptr; 249206084Srdivacky 250327952Sdim UniqueVirtualMethod() = default; 251327952Sdim 252327952Sdim UniqueVirtualMethod(CXXMethodDecl *Method, unsigned Subobject, 253327952Sdim const CXXRecordDecl *InVirtualSubobject) 254327952Sdim : Method(Method), Subobject(Subobject), 255327952Sdim InVirtualSubobject(InVirtualSubobject) {} 256327952Sdim 257206084Srdivacky friend bool operator==(const UniqueVirtualMethod &X, 258206084Srdivacky const UniqueVirtualMethod &Y) { 259206084Srdivacky return X.Method == Y.Method && X.Subobject == Y.Subobject && 260206084Srdivacky X.InVirtualSubobject == Y.InVirtualSubobject; 261206084Srdivacky } 262206084Srdivacky 263206084Srdivacky friend bool operator!=(const UniqueVirtualMethod &X, 264206084Srdivacky const UniqueVirtualMethod &Y) { 265206084Srdivacky return !(X == Y); 266206084Srdivacky } 267206084Srdivacky}; 268206084Srdivacky 269206084Srdivacky/// \brief The set of methods that override a given virtual method in 270206084Srdivacky/// each subobject where it occurs. 271206084Srdivacky/// 272206084Srdivacky/// The first part of the pair is the subobject in which the 273206084Srdivacky/// overridden virtual function occurs, while the second part of the 274206084Srdivacky/// pair is the virtual method that overrides it (including the 275206084Srdivacky/// subobject in which that virtual function occurs). 276206084Srdivackyclass OverridingMethods { 277327952Sdim using ValuesT = SmallVector<UniqueVirtualMethod, 4>; 278327952Sdim using MapType = llvm::MapVector<unsigned, ValuesT>; 279327952Sdim 280243830Sdim MapType Overrides; 281206084Srdivacky 282206084Srdivackypublic: 283206084Srdivacky // Iterate over the set of subobjects that have overriding methods. 284327952Sdim using iterator = MapType::iterator; 285327952Sdim using const_iterator = MapType::const_iterator; 286327952Sdim 287206084Srdivacky iterator begin() { return Overrides.begin(); } 288206084Srdivacky const_iterator begin() const { return Overrides.begin(); } 289206084Srdivacky iterator end() { return Overrides.end(); } 290206084Srdivacky const_iterator end() const { return Overrides.end(); } 291206084Srdivacky unsigned size() const { return Overrides.size(); } 292206084Srdivacky 293206084Srdivacky // Iterate over the set of overriding virtual methods in a given 294206084Srdivacky // subobject. 295327952Sdim using overriding_iterator = 296327952Sdim SmallVectorImpl<UniqueVirtualMethod>::iterator; 297327952Sdim using overriding_const_iterator = 298327952Sdim SmallVectorImpl<UniqueVirtualMethod>::const_iterator; 299206084Srdivacky 300206084Srdivacky // Add a new overriding method for a particular subobject. 301206084Srdivacky void add(unsigned OverriddenSubobject, UniqueVirtualMethod Overriding); 302206084Srdivacky 303206084Srdivacky // Add all of the overriding methods from "other" into overrides for 304206084Srdivacky // this method. Used when merging the overrides from multiple base 305206084Srdivacky // class subobjects. 306206084Srdivacky void add(const OverridingMethods &Other); 307206084Srdivacky 308206084Srdivacky // Replace all overriding virtual methods in all subobjects with the 309206084Srdivacky // given virtual method. 310206084Srdivacky void replaceAll(UniqueVirtualMethod Overriding); 311206084Srdivacky}; 312206084Srdivacky 313206084Srdivacky/// \brief A mapping from each virtual member function to its set of 314206084Srdivacky/// final overriders. 315206084Srdivacky/// 316206084Srdivacky/// Within a class hierarchy for a given derived class, each virtual 317206084Srdivacky/// member function in that hierarchy has one or more "final 318206084Srdivacky/// overriders" (C++ [class.virtual]p2). A final overrider for a 319206084Srdivacky/// virtual function "f" is the virtual function that will actually be 320206084Srdivacky/// invoked when dispatching a call to "f" through the 321206084Srdivacky/// vtable. Well-formed classes have a single final overrider for each 322206084Srdivacky/// virtual function; in abstract classes, the final overrider for at 323206084Srdivacky/// least one virtual function is a pure virtual function. Due to 324206084Srdivacky/// multiple, virtual inheritance, it is possible for a class to have 325206084Srdivacky/// more than one final overrider. Athough this is an error (per C++ 326206084Srdivacky/// [class.virtual]p2), it is not considered an error here: the final 327206084Srdivacky/// overrider map can represent multiple final overriders for a 328206084Srdivacky/// method, and it is up to the client to determine whether they are 329206084Srdivacky/// problem. For example, the following class \c D has two final 330206084Srdivacky/// overriders for the virtual function \c A::f(), one in \c C and one 331206084Srdivacky/// in \c D: 332206084Srdivacky/// 333206084Srdivacky/// \code 334206084Srdivacky/// struct A { virtual void f(); }; 335206084Srdivacky/// struct B : virtual A { virtual void f(); }; 336206084Srdivacky/// struct C : virtual A { virtual void f(); }; 337206084Srdivacky/// struct D : B, C { }; 338206084Srdivacky/// \endcode 339206084Srdivacky/// 340288943Sdim/// This data structure contains a mapping from every virtual 341206084Srdivacky/// function *that does not override an existing virtual function* and 342206084Srdivacky/// in every subobject where that virtual function occurs to the set 343206084Srdivacky/// of virtual functions that override it. Thus, the same virtual 344206084Srdivacky/// function \c A::f can actually occur in multiple subobjects of type 345288943Sdim/// \c A due to multiple inheritance, and may be overridden by 346206084Srdivacky/// different virtual functions in each, as in the following example: 347206084Srdivacky/// 348206084Srdivacky/// \code 349206084Srdivacky/// struct A { virtual void f(); }; 350206084Srdivacky/// struct B : A { virtual void f(); }; 351206084Srdivacky/// struct C : A { virtual void f(); }; 352206084Srdivacky/// struct D : B, C { }; 353206084Srdivacky/// \endcode 354206084Srdivacky/// 355206084Srdivacky/// Unlike in the previous example, where the virtual functions \c 356206084Srdivacky/// B::f and \c C::f both overrode \c A::f in the same subobject of 357206084Srdivacky/// type \c A, in this example the two virtual functions both override 358206084Srdivacky/// \c A::f but in *different* subobjects of type A. This is 359206084Srdivacky/// represented by numbering the subobjects in which the overridden 360206084Srdivacky/// and the overriding virtual member functions are located. Subobject 361288943Sdim/// 0 represents the virtual base class subobject of that type, while 362206084Srdivacky/// subobject numbers greater than 0 refer to non-virtual base class 363206084Srdivacky/// subobjects of that type. 364243830Sdimclass CXXFinalOverriderMap 365327952Sdim : public llvm::MapVector<const CXXMethodDecl *, OverridingMethods> {}; 366218893Sdim 367218893Sdim/// \brief A set of all the primary bases for a class. 368218893Sdimclass CXXIndirectPrimaryBaseSet 369327952Sdim : public llvm::SmallSet<const CXXRecordDecl*, 32> {}; 370218893Sdim 371327952Sdim} // namespace clang 372198092Srdivacky 373327952Sdim#endif // LLVM_CLANG_AST_CXXINHERITANCE_H 374