1327952Sdim//===- CXXInheritance.h - C++ Inheritance -----------------------*- C++ -*-===// 2198092Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6198092Srdivacky// 7198092Srdivacky//===----------------------------------------------------------------------===// 8198092Srdivacky// 9198092Srdivacky// This file provides routines that help analyzing C++ inheritance hierarchies. 10198092Srdivacky// 11198092Srdivacky//===----------------------------------------------------------------------===// 12198092Srdivacky 13198092Srdivacky#ifndef LLVM_CLANG_AST_CXXINHERITANCE_H 14198092Srdivacky#define LLVM_CLANG_AST_CXXINHERITANCE_H 15198092Srdivacky 16198092Srdivacky#include "clang/AST/DeclBase.h" 17204643Srdivacky#include "clang/AST/DeclCXX.h" 18327952Sdim#include "clang/AST/DeclarationName.h" 19198092Srdivacky#include "clang/AST/Type.h" 20198092Srdivacky#include "clang/AST/TypeOrdering.h" 21327952Sdim#include "clang/Basic/Specifiers.h" 22327952Sdim#include "llvm/ADT/DenseMap.h" 23327952Sdim#include "llvm/ADT/DenseSet.h" 24243830Sdim#include "llvm/ADT/MapVector.h" 25218893Sdim#include "llvm/ADT/SmallSet.h" 26198092Srdivacky#include "llvm/ADT/SmallVector.h" 27327952Sdim#include "llvm/ADT/iterator_range.h" 28198092Srdivacky#include <list> 29327952Sdim#include <memory> 30327952Sdim#include <utility> 31198092Srdivacky 32198092Srdivackynamespace clang { 33327952Sdim 34327952Sdimclass ASTContext; 35198092Srdivackyclass NamedDecl; 36341825Sdim 37341825Sdim/// Represents an element in a path from a derived class to a 38341825Sdim/// base class. 39341825Sdim/// 40198092Srdivacky/// Each step in the path references the link from a 41198092Srdivacky/// derived class to one of its direct base classes, along with a 42198092Srdivacky/// base "number" that identifies which base subobject of the 43198092Srdivacky/// original derived class we are referencing. 44198092Srdivackystruct CXXBasePathElement { 45341825Sdim /// The base specifier that states the link from a derived 46198092Srdivacky /// class to a base class, which will be followed by this base 47198092Srdivacky /// path element. 48198092Srdivacky const CXXBaseSpecifier *Base; 49341825Sdim 50341825Sdim /// The record decl of the class that the base is a base of. 51198092Srdivacky const CXXRecordDecl *Class; 52341825Sdim 53341825Sdim /// Identifies which base class subobject (of type 54341825Sdim /// \c Base->getType()) this base path element refers to. 55198092Srdivacky /// 56198092Srdivacky /// This value is only valid if \c !Base->isVirtual(), because there 57198092Srdivacky /// is no base numbering for the zero or one virtual bases of a 58198092Srdivacky /// given type. 59198092Srdivacky int SubobjectNumber; 60198092Srdivacky}; 61198092Srdivacky 62341825Sdim/// Represents a path from a specific derived class 63198092Srdivacky/// (which is not represented as part of the path) to a particular 64198092Srdivacky/// (direct or indirect) base class subobject. 65198092Srdivacky/// 66341825Sdim/// Individual elements in the path are described by the \c CXXBasePathElement 67198092Srdivacky/// structure, which captures both the link from a derived class to one of its 68198092Srdivacky/// direct bases and identification describing which base class 69198092Srdivacky/// subobject is being used. 70226633Sdimclass CXXBasePath : public SmallVector<CXXBasePathElement, 4> { 71198398Srdivackypublic: 72341825Sdim /// The access along this inheritance path. This is only 73202879Srdivacky /// calculated when recording paths. AS_none is a special value 74202879Srdivacky /// used to indicate a path which permits no legal access. 75327952Sdim AccessSpecifier Access = AS_public; 76202879Srdivacky 77327952Sdim CXXBasePath() = default; 78327952Sdim 79341825Sdim /// The set of declarations found inside this base class 80198092Srdivacky /// subobject. 81198092Srdivacky DeclContext::lookup_result Decls; 82202879Srdivacky 83202879Srdivacky void clear() { 84226633Sdim SmallVectorImpl<CXXBasePathElement>::clear(); 85202879Srdivacky Access = AS_public; 86202879Srdivacky } 87198092Srdivacky}; 88198092Srdivacky 89198092Srdivacky/// BasePaths - Represents the set of paths from a derived class to 90198092Srdivacky/// one of its (direct or indirect) bases. For example, given the 91221345Sdim/// following class hierarchy: 92198092Srdivacky/// 93198092Srdivacky/// @code 94198092Srdivacky/// class A { }; 95198092Srdivacky/// class B : public A { }; 96198092Srdivacky/// class C : public A { }; 97198092Srdivacky/// class D : public B, public C{ }; 98198092Srdivacky/// @endcode 99198092Srdivacky/// 100198092Srdivacky/// There are two potential BasePaths to represent paths from D to a 101198092Srdivacky/// base subobject of type A. One path is (D,0) -> (B,0) -> (A,0) 102198092Srdivacky/// and another is (D,0)->(C,0)->(A,1). These two paths actually 103198092Srdivacky/// refer to two different base class subobjects of the same type, 104198092Srdivacky/// so the BasePaths object refers to an ambiguous path. On the 105198092Srdivacky/// other hand, consider the following class hierarchy: 106198092Srdivacky/// 107198092Srdivacky/// @code 108198092Srdivacky/// class A { }; 109198092Srdivacky/// class B : public virtual A { }; 110198092Srdivacky/// class C : public virtual A { }; 111198092Srdivacky/// class D : public B, public C{ }; 112198092Srdivacky/// @endcode 113198092Srdivacky/// 114198092Srdivacky/// Here, there are two potential BasePaths again, (D, 0) -> (B, 0) 115198092Srdivacky/// -> (A,v) and (D, 0) -> (C, 0) -> (A, v), but since both of them 116198092Srdivacky/// refer to the same base class subobject of type A (the virtual 117198092Srdivacky/// one), there is no ambiguity. 118198092Srdivackyclass CXXBasePaths { 119327952Sdim friend class CXXRecordDecl; 120327952Sdim 121341825Sdim /// The type from which this search originated. 122327952Sdim CXXRecordDecl *Origin = nullptr; 123341825Sdim 124198092Srdivacky /// Paths - The actual set of paths that can be taken from the 125198092Srdivacky /// derived class to the same base class. 126198092Srdivacky std::list<CXXBasePath> Paths; 127341825Sdim 128198092Srdivacky /// ClassSubobjects - Records the class subobjects for each class 129341825Sdim /// type that we've seen. The first element IsVirtBase says 130198092Srdivacky /// whether we found a path to a virtual base for that class type, 131341825Sdim /// while NumberOfNonVirtBases contains the number of non-virtual base 132198092Srdivacky /// class subobjects for that class type. The key of the map is 133198092Srdivacky /// the cv-unqualified canonical type of the base class subobject. 134341825Sdim struct IsVirtBaseAndNumberNonVirtBases { 135341825Sdim unsigned IsVirtBase : 1; 136341825Sdim unsigned NumberOfNonVirtBases : 31; 137341825Sdim }; 138341825Sdim llvm::SmallDenseMap<QualType, IsVirtBaseAndNumberNonVirtBases, 8> 139341825Sdim ClassSubobjects; 140321369Sdim 141321369Sdim /// VisitedDependentRecords - Records the dependent records that have been 142321369Sdim /// already visited. 143341825Sdim llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedDependentRecords; 144321369Sdim 145341825Sdim /// DetectedVirtual - The base class that is virtual. 146341825Sdim const RecordType *DetectedVirtual = nullptr; 147341825Sdim 148341825Sdim /// ScratchPath - A BasePath that is used by Sema::lookupInBases 149341825Sdim /// to help build the set of paths. 150341825Sdim CXXBasePath ScratchPath; 151341825Sdim 152341825Sdim /// Array of the declarations that have been found. This 153341825Sdim /// array is constructed only if needed, e.g., to iterate over the 154341825Sdim /// results within LookupResult. 155341825Sdim std::unique_ptr<NamedDecl *[]> DeclsFound; 156341825Sdim unsigned NumDeclsFound = 0; 157341825Sdim 158198092Srdivacky /// FindAmbiguities - Whether Sema::IsDerivedFrom should try find 159198092Srdivacky /// ambiguous paths while it is looking for a path from a derived 160198092Srdivacky /// type to a base type. 161198092Srdivacky bool FindAmbiguities; 162341825Sdim 163198092Srdivacky /// RecordPaths - Whether Sema::IsDerivedFrom should record paths 164198092Srdivacky /// while it is determining whether there are paths from a derived 165198092Srdivacky /// type to a base type. 166198092Srdivacky bool RecordPaths; 167341825Sdim 168198092Srdivacky /// DetectVirtual - Whether Sema::IsDerivedFrom should abort the search 169198092Srdivacky /// if it finds a path that goes across a virtual base. The virtual class 170198092Srdivacky /// is also recorded. 171198092Srdivacky bool DetectVirtual; 172202879Srdivacky 173198092Srdivacky void ComputeDeclsFound(); 174204643Srdivacky 175296417Sdim bool lookupInBases(ASTContext &Context, const CXXRecordDecl *Record, 176321369Sdim CXXRecordDecl::BaseMatchesCallback BaseMatches, 177321369Sdim bool LookupInDependent = false); 178296417Sdim 179198092Srdivackypublic: 180327952Sdim using paths_iterator = std::list<CXXBasePath>::iterator; 181327952Sdim using const_paths_iterator = std::list<CXXBasePath>::const_iterator; 182327952Sdim using decl_iterator = NamedDecl **; 183341825Sdim 184198092Srdivacky /// BasePaths - Construct a new BasePaths structure to record the 185198092Srdivacky /// paths for a derived-to-base search. 186296417Sdim explicit CXXBasePaths(bool FindAmbiguities = true, bool RecordPaths = true, 187198092Srdivacky bool DetectVirtual = true) 188327952Sdim : FindAmbiguities(FindAmbiguities), RecordPaths(RecordPaths), 189327952Sdim DetectVirtual(DetectVirtual) {} 190296417Sdim 191203955Srdivacky paths_iterator begin() { return Paths.begin(); } 192203955Srdivacky paths_iterator end() { return Paths.end(); } 193203955Srdivacky const_paths_iterator begin() const { return Paths.begin(); } 194203955Srdivacky const_paths_iterator end() const { return Paths.end(); } 195341825Sdim 196198092Srdivacky CXXBasePath& front() { return Paths.front(); } 197198092Srdivacky const CXXBasePath& front() const { return Paths.front(); } 198341825Sdim 199327952Sdim using decl_range = llvm::iterator_range<decl_iterator>; 200327952Sdim 201276479Sdim decl_range found_decls(); 202341825Sdim 203341825Sdim /// Determine whether the path from the most-derived type to the 204198092Srdivacky /// given base type is ambiguous (i.e., it refers to multiple subobjects of 205198092Srdivacky /// the same base type). 206208600Srdivacky bool isAmbiguous(CanQualType BaseType); 207341825Sdim 208341825Sdim /// Whether we are finding multiple paths to detect ambiguities. 209198092Srdivacky bool isFindingAmbiguities() const { return FindAmbiguities; } 210341825Sdim 211341825Sdim /// Whether we are recording paths. 212198092Srdivacky bool isRecordingPaths() const { return RecordPaths; } 213341825Sdim 214341825Sdim /// Specify whether we should be recording paths or not. 215198092Srdivacky void setRecordingPaths(bool RP) { RecordPaths = RP; } 216341825Sdim 217341825Sdim /// Whether we are detecting virtual bases. 218198092Srdivacky bool isDetectingVirtual() const { return DetectVirtual; } 219341825Sdim 220341825Sdim /// The virtual base discovered on the path (if we are merely 221198092Srdivacky /// detecting virtuals). 222198092Srdivacky const RecordType* getDetectedVirtual() const { 223198092Srdivacky return DetectedVirtual; 224198092Srdivacky } 225203955Srdivacky 226341825Sdim /// Retrieve the type from which this base-paths search 227198092Srdivacky /// began 228198092Srdivacky CXXRecordDecl *getOrigin() const { return Origin; } 229198092Srdivacky void setOrigin(CXXRecordDecl *Rec) { Origin = Rec; } 230341825Sdim 231341825Sdim /// Clear the base-paths results. 232198092Srdivacky void clear(); 233341825Sdim 234341825Sdim /// Swap this data structure's contents with another CXXBasePaths 235198092Srdivacky /// object. 236198092Srdivacky void swap(CXXBasePaths &Other); 237198092Srdivacky}; 238206084Srdivacky 239341825Sdim/// Uniquely identifies a virtual method within a class 240206084Srdivacky/// hierarchy by the method itself and a class subobject number. 241206084Srdivackystruct UniqueVirtualMethod { 242341825Sdim /// The overriding virtual method. 243327952Sdim CXXMethodDecl *Method = nullptr; 244206084Srdivacky 245341825Sdim /// The subobject in which the overriding virtual method 246206084Srdivacky /// resides. 247327952Sdim unsigned Subobject = 0; 248206084Srdivacky 249341825Sdim /// The virtual base class subobject of which this overridden 250206084Srdivacky /// virtual method is a part. Note that this records the closest 251206084Srdivacky /// derived virtual base class subobject. 252327952Sdim const CXXRecordDecl *InVirtualSubobject = nullptr; 253206084Srdivacky 254327952Sdim UniqueVirtualMethod() = default; 255327952Sdim 256327952Sdim UniqueVirtualMethod(CXXMethodDecl *Method, unsigned Subobject, 257327952Sdim const CXXRecordDecl *InVirtualSubobject) 258327952Sdim : Method(Method), Subobject(Subobject), 259327952Sdim InVirtualSubobject(InVirtualSubobject) {} 260327952Sdim 261206084Srdivacky friend bool operator==(const UniqueVirtualMethod &X, 262206084Srdivacky const UniqueVirtualMethod &Y) { 263206084Srdivacky return X.Method == Y.Method && X.Subobject == Y.Subobject && 264206084Srdivacky X.InVirtualSubobject == Y.InVirtualSubobject; 265206084Srdivacky } 266206084Srdivacky 267206084Srdivacky friend bool operator!=(const UniqueVirtualMethod &X, 268206084Srdivacky const UniqueVirtualMethod &Y) { 269206084Srdivacky return !(X == Y); 270206084Srdivacky } 271206084Srdivacky}; 272206084Srdivacky 273341825Sdim/// The set of methods that override a given virtual method in 274206084Srdivacky/// each subobject where it occurs. 275206084Srdivacky/// 276206084Srdivacky/// The first part of the pair is the subobject in which the 277206084Srdivacky/// overridden virtual function occurs, while the second part of the 278206084Srdivacky/// pair is the virtual method that overrides it (including the 279206084Srdivacky/// subobject in which that virtual function occurs). 280206084Srdivackyclass OverridingMethods { 281327952Sdim using ValuesT = SmallVector<UniqueVirtualMethod, 4>; 282327952Sdim using MapType = llvm::MapVector<unsigned, ValuesT>; 283327952Sdim 284243830Sdim MapType Overrides; 285206084Srdivacky 286206084Srdivackypublic: 287206084Srdivacky // Iterate over the set of subobjects that have overriding methods. 288327952Sdim using iterator = MapType::iterator; 289327952Sdim using const_iterator = MapType::const_iterator; 290327952Sdim 291206084Srdivacky iterator begin() { return Overrides.begin(); } 292206084Srdivacky const_iterator begin() const { return Overrides.begin(); } 293206084Srdivacky iterator end() { return Overrides.end(); } 294206084Srdivacky const_iterator end() const { return Overrides.end(); } 295206084Srdivacky unsigned size() const { return Overrides.size(); } 296206084Srdivacky 297206084Srdivacky // Iterate over the set of overriding virtual methods in a given 298206084Srdivacky // subobject. 299327952Sdim using overriding_iterator = 300327952Sdim SmallVectorImpl<UniqueVirtualMethod>::iterator; 301327952Sdim using overriding_const_iterator = 302327952Sdim SmallVectorImpl<UniqueVirtualMethod>::const_iterator; 303206084Srdivacky 304206084Srdivacky // Add a new overriding method for a particular subobject. 305206084Srdivacky void add(unsigned OverriddenSubobject, UniqueVirtualMethod Overriding); 306206084Srdivacky 307206084Srdivacky // Add all of the overriding methods from "other" into overrides for 308206084Srdivacky // this method. Used when merging the overrides from multiple base 309206084Srdivacky // class subobjects. 310206084Srdivacky void add(const OverridingMethods &Other); 311206084Srdivacky 312206084Srdivacky // Replace all overriding virtual methods in all subobjects with the 313206084Srdivacky // given virtual method. 314206084Srdivacky void replaceAll(UniqueVirtualMethod Overriding); 315206084Srdivacky}; 316206084Srdivacky 317341825Sdim/// A mapping from each virtual member function to its set of 318206084Srdivacky/// final overriders. 319206084Srdivacky/// 320206084Srdivacky/// Within a class hierarchy for a given derived class, each virtual 321206084Srdivacky/// member function in that hierarchy has one or more "final 322206084Srdivacky/// overriders" (C++ [class.virtual]p2). A final overrider for a 323206084Srdivacky/// virtual function "f" is the virtual function that will actually be 324206084Srdivacky/// invoked when dispatching a call to "f" through the 325206084Srdivacky/// vtable. Well-formed classes have a single final overrider for each 326206084Srdivacky/// virtual function; in abstract classes, the final overrider for at 327206084Srdivacky/// least one virtual function is a pure virtual function. Due to 328206084Srdivacky/// multiple, virtual inheritance, it is possible for a class to have 329206084Srdivacky/// more than one final overrider. Athough this is an error (per C++ 330206084Srdivacky/// [class.virtual]p2), it is not considered an error here: the final 331206084Srdivacky/// overrider map can represent multiple final overriders for a 332206084Srdivacky/// method, and it is up to the client to determine whether they are 333206084Srdivacky/// problem. For example, the following class \c D has two final 334206084Srdivacky/// overriders for the virtual function \c A::f(), one in \c C and one 335206084Srdivacky/// in \c D: 336206084Srdivacky/// 337206084Srdivacky/// \code 338206084Srdivacky/// struct A { virtual void f(); }; 339206084Srdivacky/// struct B : virtual A { virtual void f(); }; 340206084Srdivacky/// struct C : virtual A { virtual void f(); }; 341206084Srdivacky/// struct D : B, C { }; 342206084Srdivacky/// \endcode 343206084Srdivacky/// 344288943Sdim/// This data structure contains a mapping from every virtual 345206084Srdivacky/// function *that does not override an existing virtual function* and 346206084Srdivacky/// in every subobject where that virtual function occurs to the set 347206084Srdivacky/// of virtual functions that override it. Thus, the same virtual 348206084Srdivacky/// function \c A::f can actually occur in multiple subobjects of type 349288943Sdim/// \c A due to multiple inheritance, and may be overridden by 350206084Srdivacky/// different virtual functions in each, as in the following example: 351206084Srdivacky/// 352206084Srdivacky/// \code 353206084Srdivacky/// struct A { virtual void f(); }; 354206084Srdivacky/// struct B : A { virtual void f(); }; 355206084Srdivacky/// struct C : A { virtual void f(); }; 356206084Srdivacky/// struct D : B, C { }; 357206084Srdivacky/// \endcode 358206084Srdivacky/// 359206084Srdivacky/// Unlike in the previous example, where the virtual functions \c 360206084Srdivacky/// B::f and \c C::f both overrode \c A::f in the same subobject of 361206084Srdivacky/// type \c A, in this example the two virtual functions both override 362206084Srdivacky/// \c A::f but in *different* subobjects of type A. This is 363206084Srdivacky/// represented by numbering the subobjects in which the overridden 364206084Srdivacky/// and the overriding virtual member functions are located. Subobject 365288943Sdim/// 0 represents the virtual base class subobject of that type, while 366206084Srdivacky/// subobject numbers greater than 0 refer to non-virtual base class 367206084Srdivacky/// subobjects of that type. 368243830Sdimclass CXXFinalOverriderMap 369327952Sdim : public llvm::MapVector<const CXXMethodDecl *, OverridingMethods> {}; 370218893Sdim 371341825Sdim/// A set of all the primary bases for a class. 372218893Sdimclass CXXIndirectPrimaryBaseSet 373327952Sdim : public llvm::SmallSet<const CXXRecordDecl*, 32> {}; 374218893Sdim 375360784Sdiminline bool 376360784SdiminheritanceModelHasVBPtrOffsetField(MSInheritanceModel Inheritance) { 377360784Sdim return Inheritance == MSInheritanceModel::Unspecified; 378360784Sdim} 379360784Sdim 380360784Sdim// Only member pointers to functions need a this adjustment, since it can be 381360784Sdim// combined with the field offset for data pointers. 382360784Sdiminline bool inheritanceModelHasNVOffsetField(bool IsMemberFunction, 383360784Sdim MSInheritanceModel Inheritance) { 384360784Sdim return IsMemberFunction && Inheritance >= MSInheritanceModel::Multiple; 385360784Sdim} 386360784Sdim 387360784Sdiminline bool 388360784SdiminheritanceModelHasVBTableOffsetField(MSInheritanceModel Inheritance) { 389360784Sdim return Inheritance >= MSInheritanceModel::Virtual; 390360784Sdim} 391360784Sdim 392360784Sdiminline bool inheritanceModelHasOnlyOneField(bool IsMemberFunction, 393360784Sdim MSInheritanceModel Inheritance) { 394360784Sdim if (IsMemberFunction) 395360784Sdim return Inheritance <= MSInheritanceModel::Single; 396360784Sdim return Inheritance <= MSInheritanceModel::Multiple; 397360784Sdim} 398360784Sdim 399327952Sdim} // namespace clang 400198092Srdivacky 401327952Sdim#endif // LLVM_CLANG_AST_CXXINHERITANCE_H 402