1a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor//===------ CXXInheritance.h - C++ Inheritance ------------------*- C++ -*-===// 2a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// 3a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// The LLVM Compiler Infrastructure 4a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// 5a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// This file is distributed under the University of Illinois Open Source 6a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// License. See LICENSE.TXT for details. 7a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// 8a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor//===----------------------------------------------------------------------===// 9a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// 10a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// This file provides routines that help analyzing C++ inheritance hierarchies. 11a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor// 12a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor//===----------------------------------------------------------------------===// 13a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 14a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor#ifndef LLVM_CLANG_AST_CXXINHERITANCE_H 15a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor#define LLVM_CLANG_AST_CXXINHERITANCE_H 16a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 17a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor#include "clang/AST/DeclBase.h" 1889b7702c9a64e12093ed34fc02dc3cfbb6eb133aDouglas Gregor#include "clang/AST/DeclCXX.h" 1930a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "clang/AST/DeclarationName.h" 20a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor#include "clang/AST/Type.h" 21a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor#include "clang/AST/TypeOrdering.h" 22490dd9c70dc25bd7b1936a05d7878dc151f96c46Rafael Espindola#include "llvm/ADT/MapVector.h" 2346170f9c7d561d0f94af34a4b5da909d2584370aAnders Carlsson#include "llvm/ADT/SmallSet.h" 24a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor#include "llvm/ADT/SmallVector.h" 2530a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include <cassert> 26a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor#include <list> 27a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor#include <map> 28a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 29a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregornamespace clang { 30a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 31a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregorclass CXXBaseSpecifier; 32a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregorclass CXXMethodDecl; 33a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregorclass CXXRecordDecl; 34a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregorclass NamedDecl; 35a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 36a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// \brief Represents an element in a path from a derived class to a 37a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// base class. 38a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// 39a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// Each step in the path references the link from a 40a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// derived class to one of its direct base classes, along with a 41a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// base "number" that identifies which base subobject of the 42a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// original derived class we are referencing. 43a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregorstruct CXXBasePathElement { 44a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief The base specifier that states the link from a derived 45a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// class to a base class, which will be followed by this base 46a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// path element. 47a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor const CXXBaseSpecifier *Base; 48a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 49a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief The record decl of the class that the base is a base of. 50a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor const CXXRecordDecl *Class; 51a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 52a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Identifies which base class subobject (of type 53a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \c Base->getType()) this base path element refers to. 54a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// 55a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// This value is only valid if \c !Base->isVirtual(), because there 56a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// is no base numbering for the zero or one virtual bases of a 57a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// given type. 58a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor int SubobjectNumber; 59a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor}; 60a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 61a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// \brief Represents a path from a specific derived class 62a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// (which is not represented as part of the path) to a particular 63a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// (direct or indirect) base class subobject. 64a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// 65a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// Individual elements in the path are described by the \c CXXBasePathElement 66a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// structure, which captures both the link from a derived class to one of its 67a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// direct bases and identification describing which base class 68a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// subobject is being used. 69686775deca8b8685eb90801495880e3abdd844c2Chris Lattnerclass CXXBasePath : public SmallVector<CXXBasePathElement, 4> { 704e0e2f1c5fde88a235d71a6f4f87f5c3fcaab7acBenjamin Kramerpublic: 7192f883177b162928a8e632e4e3b93fafd2b26072John McCall CXXBasePath() : Access(AS_public) {} 7292f883177b162928a8e632e4e3b93fafd2b26072John McCall 7392f883177b162928a8e632e4e3b93fafd2b26072John McCall /// \brief The access along this inheritance path. This is only 7492f883177b162928a8e632e4e3b93fafd2b26072John McCall /// calculated when recording paths. AS_none is a special value 7592f883177b162928a8e632e4e3b93fafd2b26072John McCall /// used to indicate a path which permits no legal access. 7646460a68f6508775e98c19b4bb8454bb471aac24John McCall AccessSpecifier Access; 7746460a68f6508775e98c19b4bb8454bb471aac24John McCall 78a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief The set of declarations found inside this base class 79a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// subobject. 80a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor DeclContext::lookup_result Decls; 8192f883177b162928a8e632e4e3b93fafd2b26072John McCall 8292f883177b162928a8e632e4e3b93fafd2b26072John McCall void clear() { 83686775deca8b8685eb90801495880e3abdd844c2Chris Lattner SmallVectorImpl<CXXBasePathElement>::clear(); 8492f883177b162928a8e632e4e3b93fafd2b26072John McCall Access = AS_public; 8592f883177b162928a8e632e4e3b93fafd2b26072John McCall } 86a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor}; 87a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 88a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// BasePaths - Represents the set of paths from a derived class to 89a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// one of its (direct or indirect) bases. For example, given the 90fc8f0e14ad142ed811e90fbd9a30e419e301c717Chris Lattner/// following class hierarchy: 91a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// 92a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// @code 93a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// class A { }; 94a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// class B : public A { }; 95a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// class C : public A { }; 96a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// class D : public B, public C{ }; 97a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// @endcode 98a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// 99a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// There are two potential BasePaths to represent paths from D to a 100a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// base subobject of type A. One path is (D,0) -> (B,0) -> (A,0) 101a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// and another is (D,0)->(C,0)->(A,1). These two paths actually 102a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// refer to two different base class subobjects of the same type, 103a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// so the BasePaths object refers to an ambiguous path. On the 104a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// other hand, consider the following class hierarchy: 105a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// 106a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// @code 107a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// class A { }; 108a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// class B : public virtual A { }; 109a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// class C : public virtual A { }; 110a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// class D : public B, public C{ }; 111a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// @endcode 112a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// 113a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// Here, there are two potential BasePaths again, (D, 0) -> (B, 0) 114a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// -> (A,v) and (D, 0) -> (C, 0) -> (A, v), but since both of them 115a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// refer to the same base class subobject of type A (the virtual 116a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor/// one), there is no ambiguity. 117a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregorclass CXXBasePaths { 118a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief The type from which this search originated. 119a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor CXXRecordDecl *Origin; 120a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 121a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// Paths - The actual set of paths that can be taken from the 122a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// derived class to the same base class. 123a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor std::list<CXXBasePath> Paths; 124a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 125a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// ClassSubobjects - Records the class subobjects for each class 126a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// type that we've seen. The first element in the pair says 127a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// whether we found a path to a virtual base for that class type, 128a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// while the element contains the number of non-virtual base 129a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// class subobjects for that class type. The key of the map is 130a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// the cv-unqualified canonical type of the base class subobject. 1317553ad2b7513fce1acd85658279da204fa99426fChandler Carruth llvm::SmallDenseMap<QualType, std::pair<bool, unsigned>, 8> ClassSubobjects; 132a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 133a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// FindAmbiguities - Whether Sema::IsDerivedFrom should try find 134a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// ambiguous paths while it is looking for a path from a derived 135a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// type to a base type. 136a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor bool FindAmbiguities; 137a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 138a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// RecordPaths - Whether Sema::IsDerivedFrom should record paths 139a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// while it is determining whether there are paths from a derived 140a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// type to a base type. 141a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor bool RecordPaths; 142a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 143a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// DetectVirtual - Whether Sema::IsDerivedFrom should abort the search 144a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// if it finds a path that goes across a virtual base. The virtual class 145a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// is also recorded. 146a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor bool DetectVirtual; 147a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 14846460a68f6508775e98c19b4bb8454bb471aac24John McCall /// ScratchPath - A BasePath that is used by Sema::lookupInBases 149a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// to help build the set of paths. 150a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor CXXBasePath ScratchPath; 15146460a68f6508775e98c19b4bb8454bb471aac24John McCall 152a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// DetectedVirtual - The base class that is virtual. 153a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor const RecordType *DetectedVirtual; 154a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 155a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Array of the declarations that have been found. This 156a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// array is constructed only if needed, e.g., to iterate over the 157a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// results within LookupResult. 158a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor NamedDecl **DeclsFound; 159a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor unsigned NumDeclsFound; 160a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 161a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor friend class CXXRecordDecl; 162a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 163a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor void ComputeDeclsFound(); 16489b7702c9a64e12093ed34fc02dc3cfbb6eb133aDouglas Gregor 16589b7702c9a64e12093ed34fc02dc3cfbb6eb133aDouglas Gregor bool lookupInBases(ASTContext &Context, 16689b7702c9a64e12093ed34fc02dc3cfbb6eb133aDouglas Gregor const CXXRecordDecl *Record, 16789b7702c9a64e12093ed34fc02dc3cfbb6eb133aDouglas Gregor CXXRecordDecl::BaseMatchesCallback *BaseMatches, 16889b7702c9a64e12093ed34fc02dc3cfbb6eb133aDouglas Gregor void *UserData); 169a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregorpublic: 1706b2accb4793e16b2e93a8c2589f5df702231f17aJohn McCall typedef std::list<CXXBasePath>::iterator paths_iterator; 1716b2accb4793e16b2e93a8c2589f5df702231f17aJohn McCall typedef std::list<CXXBasePath>::const_iterator const_paths_iterator; 172a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor typedef NamedDecl **decl_iterator; 173a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 174a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// BasePaths - Construct a new BasePaths structure to record the 175a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// paths for a derived-to-base search. 176a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor explicit CXXBasePaths(bool FindAmbiguities = true, 177a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor bool RecordPaths = true, 178a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor bool DetectVirtual = true) 179a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor : FindAmbiguities(FindAmbiguities), RecordPaths(RecordPaths), 1806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines DetectVirtual(DetectVirtual), DetectedVirtual(nullptr), 1816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines DeclsFound(nullptr), NumDeclsFound(0) { } 182a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 183a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor ~CXXBasePaths() { delete [] DeclsFound; } 184a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 1856b2accb4793e16b2e93a8c2589f5df702231f17aJohn McCall paths_iterator begin() { return Paths.begin(); } 1866b2accb4793e16b2e93a8c2589f5df702231f17aJohn McCall paths_iterator end() { return Paths.end(); } 1876b2accb4793e16b2e93a8c2589f5df702231f17aJohn McCall const_paths_iterator begin() const { return Paths.begin(); } 1886b2accb4793e16b2e93a8c2589f5df702231f17aJohn McCall const_paths_iterator end() const { return Paths.end(); } 189a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 190a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor CXXBasePath& front() { return Paths.front(); } 191a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor const CXXBasePath& front() const { return Paths.front(); } 192a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 193651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines typedef llvm::iterator_range<decl_iterator> decl_range; 194651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines decl_range found_decls(); 195a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 196a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Determine whether the path from the most-derived type to the 197a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// given base type is ambiguous (i.e., it refers to multiple subobjects of 198a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// the same base type). 199e0d5fe2a417b84ac8b51927ebeb8f1c9ae492760Douglas Gregor bool isAmbiguous(CanQualType BaseType); 200a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 201a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Whether we are finding multiple paths to detect ambiguities. 202a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor bool isFindingAmbiguities() const { return FindAmbiguities; } 203a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 204a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Whether we are recording paths. 205a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor bool isRecordingPaths() const { return RecordPaths; } 206a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 207a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Specify whether we should be recording paths or not. 208a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor void setRecordingPaths(bool RP) { RecordPaths = RP; } 209a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 210a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Whether we are detecting virtual bases. 211a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor bool isDetectingVirtual() const { return DetectVirtual; } 212a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 213a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief The virtual base discovered on the path (if we are merely 214a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// detecting virtuals). 215a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor const RecordType* getDetectedVirtual() const { 216a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor return DetectedVirtual; 217a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor } 2186b2accb4793e16b2e93a8c2589f5df702231f17aJohn McCall 219a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Retrieve the type from which this base-paths search 220a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// began 221a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor CXXRecordDecl *getOrigin() const { return Origin; } 222a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor void setOrigin(CXXRecordDecl *Rec) { Origin = Rec; } 223a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 224a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Clear the base-paths results. 225a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor void clear(); 226a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 227a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// \brief Swap this data structure's contents with another CXXBasePaths 228a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor /// object. 229a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor void swap(CXXBasePaths &Other); 230a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor}; 2317b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2327b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \brief Uniquely identifies a virtual method within a class 2337b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// hierarchy by the method itself and a class subobject number. 2347b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregorstruct UniqueVirtualMethod { 2356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines UniqueVirtualMethod() 2366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : Method(nullptr), Subobject(0), InVirtualSubobject(nullptr) { } 2377b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2387b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor UniqueVirtualMethod(CXXMethodDecl *Method, unsigned Subobject, 2397b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor const CXXRecordDecl *InVirtualSubobject) 2407b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor : Method(Method), Subobject(Subobject), 2417b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor InVirtualSubobject(InVirtualSubobject) { } 2427b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2437b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor /// \brief The overriding virtual method. 2447b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor CXXMethodDecl *Method; 2457b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2467b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor /// \brief The subobject in which the overriding virtual method 2477b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor /// resides. 2487b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor unsigned Subobject; 2497b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2507b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor /// \brief The virtual base class subobject of which this overridden 2517b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor /// virtual method is a part. Note that this records the closest 2527b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor /// derived virtual base class subobject. 2537b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor const CXXRecordDecl *InVirtualSubobject; 2547b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2557b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor friend bool operator==(const UniqueVirtualMethod &X, 2567b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor const UniqueVirtualMethod &Y) { 2577b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor return X.Method == Y.Method && X.Subobject == Y.Subobject && 2587b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor X.InVirtualSubobject == Y.InVirtualSubobject; 2597b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor } 2607b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2617b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor friend bool operator!=(const UniqueVirtualMethod &X, 2627b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor const UniqueVirtualMethod &Y) { 2637b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor return !(X == Y); 2647b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor } 2657b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor}; 2667b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2677b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \brief The set of methods that override a given virtual method in 2687b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// each subobject where it occurs. 2697b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// 2707b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// The first part of the pair is the subobject in which the 2717b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// overridden virtual function occurs, while the second part of the 2727b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// pair is the virtual method that overrides it (including the 2737b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// subobject in which that virtual function occurs). 2747b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregorclass OverridingMethods { 2753bd762deaace1d62dab413d22c7430434e57a0d5Rafael Espindola typedef SmallVector<UniqueVirtualMethod, 4> ValuesT; 276490dd9c70dc25bd7b1936a05d7878dc151f96c46Rafael Espindola typedef llvm::MapVector<unsigned, ValuesT> MapType; 2773bd762deaace1d62dab413d22c7430434e57a0d5Rafael Espindola MapType Overrides; 2787b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2797b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregorpublic: 2807b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // Iterate over the set of subobjects that have overriding methods. 2813bd762deaace1d62dab413d22c7430434e57a0d5Rafael Espindola typedef MapType::iterator iterator; 2823bd762deaace1d62dab413d22c7430434e57a0d5Rafael Espindola typedef MapType::const_iterator const_iterator; 2837b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor iterator begin() { return Overrides.begin(); } 2847b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor const_iterator begin() const { return Overrides.begin(); } 2857b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor iterator end() { return Overrides.end(); } 2867b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor const_iterator end() const { return Overrides.end(); } 2877b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor unsigned size() const { return Overrides.size(); } 2887b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2897b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // Iterate over the set of overriding virtual methods in a given 2907b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // subobject. 29109d19efaa147762f84aed55efa7930bb3616a4e5Craig Topper typedef SmallVectorImpl<UniqueVirtualMethod>::iterator 2927b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor overriding_iterator; 29309d19efaa147762f84aed55efa7930bb3616a4e5Craig Topper typedef SmallVectorImpl<UniqueVirtualMethod>::const_iterator 2947b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor overriding_const_iterator; 2957b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2967b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // Add a new overriding method for a particular subobject. 2977b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor void add(unsigned OverriddenSubobject, UniqueVirtualMethod Overriding); 2987b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 2997b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // Add all of the overriding methods from "other" into overrides for 3007b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // this method. Used when merging the overrides from multiple base 3017b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // class subobjects. 3027b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor void add(const OverridingMethods &Other); 3037b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 3047b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // Replace all overriding virtual methods in all subobjects with the 3057b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor // given virtual method. 3067b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor void replaceAll(UniqueVirtualMethod Overriding); 3077b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor}; 3087b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor 3097b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \brief A mapping from each virtual member function to its set of 3107b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// final overriders. 3117b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// 3127b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// Within a class hierarchy for a given derived class, each virtual 3137b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// member function in that hierarchy has one or more "final 3147b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// overriders" (C++ [class.virtual]p2). A final overrider for a 3157b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// virtual function "f" is the virtual function that will actually be 3167b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// invoked when dispatching a call to "f" through the 3177b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// vtable. Well-formed classes have a single final overrider for each 3187b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// virtual function; in abstract classes, the final overrider for at 3197b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// least one virtual function is a pure virtual function. Due to 3207b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// multiple, virtual inheritance, it is possible for a class to have 3217b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// more than one final overrider. Athough this is an error (per C++ 3227b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// [class.virtual]p2), it is not considered an error here: the final 3237b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// overrider map can represent multiple final overriders for a 3247b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// method, and it is up to the client to determine whether they are 3257b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// problem. For example, the following class \c D has two final 3267b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// overriders for the virtual function \c A::f(), one in \c C and one 3277b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// in \c D: 3287b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// 3297b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \code 3307b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// struct A { virtual void f(); }; 3317b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// struct B : virtual A { virtual void f(); }; 3327b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// struct C : virtual A { virtual void f(); }; 3337b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// struct D : B, C { }; 3347b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \endcode 3357b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// 3367b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// This data structure contaings a mapping from every virtual 3377b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// function *that does not override an existing virtual function* and 3387b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// in every subobject where that virtual function occurs to the set 3397b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// of virtual functions that override it. Thus, the same virtual 3407b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// function \c A::f can actually occur in multiple subobjects of type 3417b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \c A due to multiple inheritance, and may be overriden by 3427b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// different virtual functions in each, as in the following example: 3437b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// 3447b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \code 3457b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// struct A { virtual void f(); }; 3467b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// struct B : A { virtual void f(); }; 3477b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// struct C : A { virtual void f(); }; 3487b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// struct D : B, C { }; 3497b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \endcode 3507b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// 3517b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// Unlike in the previous example, where the virtual functions \c 3527b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// B::f and \c C::f both overrode \c A::f in the same subobject of 3537b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// type \c A, in this example the two virtual functions both override 3547b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// \c A::f but in *different* subobjects of type A. This is 3557b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// represented by numbering the subobjects in which the overridden 3567b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// and the overriding virtual member functions are located. Subobject 3577b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// 0 represents the virtua base class subobject of that type, while 3587b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// subobject numbers greater than 0 refer to non-virtual base class 3597b2fc9d3c97f2526528a8b686af1589054025ca0Douglas Gregor/// subobjects of that type. 360490dd9c70dc25bd7b1936a05d7878dc151f96c46Rafael Espindolaclass CXXFinalOverriderMap 361490dd9c70dc25bd7b1936a05d7878dc151f96c46Rafael Espindola : public llvm::MapVector<const CXXMethodDecl *, OverridingMethods> { }; 36246170f9c7d561d0f94af34a4b5da909d2584370aAnders Carlsson 36346170f9c7d561d0f94af34a4b5da909d2584370aAnders Carlsson/// \brief A set of all the primary bases for a class. 36446170f9c7d561d0f94af34a4b5da909d2584370aAnders Carlssonclass CXXIndirectPrimaryBaseSet 36546170f9c7d561d0f94af34a4b5da909d2584370aAnders Carlsson : public llvm::SmallSet<const CXXRecordDecl*, 32> { }; 36646170f9c7d561d0f94af34a4b5da909d2584370aAnders Carlsson 367a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor} // end namespace clang 368a8f32e0965ee19ecc53cd796e34268377a20357cDouglas Gregor 369da5529121eb3102432170ee0a1797b9e58044a2fMike Stump#endif 370