CXXInheritance.cpp revision 198092
1//===------ CXXInheritance.cpp - 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#include "clang/AST/CXXInheritance.h" 14#include "clang/AST/DeclCXX.h" 15#include <algorithm> 16#include <set> 17 18using namespace clang; 19 20/// \brief Computes the set of declarations referenced by these base 21/// paths. 22void CXXBasePaths::ComputeDeclsFound() { 23 assert(NumDeclsFound == 0 && !DeclsFound && 24 "Already computed the set of declarations"); 25 26 std::set<NamedDecl *> Decls; 27 for (CXXBasePaths::paths_iterator Path = begin(), PathEnd = end(); 28 Path != PathEnd; ++Path) 29 Decls.insert(*Path->Decls.first); 30 31 NumDeclsFound = Decls.size(); 32 DeclsFound = new NamedDecl * [NumDeclsFound]; 33 std::copy(Decls.begin(), Decls.end(), DeclsFound); 34} 35 36CXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() { 37 if (NumDeclsFound == 0) 38 ComputeDeclsFound(); 39 return DeclsFound; 40} 41 42CXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() { 43 if (NumDeclsFound == 0) 44 ComputeDeclsFound(); 45 return DeclsFound + NumDeclsFound; 46} 47 48/// isAmbiguous - Determines whether the set of paths provided is 49/// ambiguous, i.e., there are two or more paths that refer to 50/// different base class subobjects of the same type. BaseType must be 51/// an unqualified, canonical class type. 52bool CXXBasePaths::isAmbiguous(QualType BaseType) { 53 assert(BaseType->isCanonical() && "Base type must be the canonical type"); 54 assert(BaseType.hasQualifiers() == 0 && "Base type must be unqualified"); 55 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType]; 56 return Subobjects.second + (Subobjects.first? 1 : 0) > 1; 57} 58 59/// clear - Clear out all prior path information. 60void CXXBasePaths::clear() { 61 Paths.clear(); 62 ClassSubobjects.clear(); 63 ScratchPath.clear(); 64 DetectedVirtual = 0; 65} 66 67/// @brief Swaps the contents of this CXXBasePaths structure with the 68/// contents of Other. 69void CXXBasePaths::swap(CXXBasePaths &Other) { 70 std::swap(Origin, Other.Origin); 71 Paths.swap(Other.Paths); 72 ClassSubobjects.swap(Other.ClassSubobjects); 73 std::swap(FindAmbiguities, Other.FindAmbiguities); 74 std::swap(RecordPaths, Other.RecordPaths); 75 std::swap(DetectVirtual, Other.DetectVirtual); 76 std::swap(DetectedVirtual, Other.DetectedVirtual); 77} 78 79bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base) { 80 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, 81 /*DetectVirtual=*/false); 82 return isDerivedFrom(Base, Paths); 83} 84 85bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base, CXXBasePaths &Paths) { 86 if (getCanonicalDecl() == Base->getCanonicalDecl()) 87 return false; 88 89 Paths.setOrigin(this); 90 return lookupInBases(&FindBaseClass, Base->getCanonicalDecl(), Paths); 91} 92 93bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches, 94 void *UserData, 95 CXXBasePaths &Paths) { 96 bool FoundPath = false; 97 98 ASTContext &Context = getASTContext(); 99 for (base_class_iterator BaseSpec = bases_begin(), BaseSpecEnd = bases_end(); 100 BaseSpec != BaseSpecEnd; ++BaseSpec) { 101 // Find the record of the base class subobjects for this type. 102 QualType BaseType = Context.getCanonicalType(BaseSpec->getType()); 103 BaseType = BaseType.getUnqualifiedType(); 104 105 // C++ [temp.dep]p3: 106 // In the definition of a class template or a member of a class template, 107 // if a base class of the class template depends on a template-parameter, 108 // the base class scope is not examined during unqualified name lookup 109 // either at the point of definition of the class template or member or 110 // during an instantiation of the class tem- plate or member. 111 if (BaseType->isDependentType()) 112 continue; 113 114 // Determine whether we need to visit this base class at all, 115 // updating the count of subobjects appropriately. 116 std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType]; 117 bool VisitBase = true; 118 bool SetVirtual = false; 119 if (BaseSpec->isVirtual()) { 120 VisitBase = !Subobjects.first; 121 Subobjects.first = true; 122 if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) { 123 // If this is the first virtual we find, remember it. If it turns out 124 // there is no base path here, we'll reset it later. 125 Paths.DetectedVirtual = BaseType->getAs<RecordType>(); 126 SetVirtual = true; 127 } 128 } else 129 ++Subobjects.second; 130 131 if (Paths.isRecordingPaths()) { 132 // Add this base specifier to the current path. 133 CXXBasePathElement Element; 134 Element.Base = &*BaseSpec; 135 Element.Class = this; 136 if (BaseSpec->isVirtual()) 137 Element.SubobjectNumber = 0; 138 else 139 Element.SubobjectNumber = Subobjects.second; 140 Paths.ScratchPath.push_back(Element); 141 } 142 143 if (BaseMatches(BaseSpec, Paths.ScratchPath, UserData)) { 144 // We've found a path that terminates that this base. 145 FoundPath = true; 146 if (Paths.isRecordingPaths()) { 147 // We have a path. Make a copy of it before moving on. 148 Paths.Paths.push_back(Paths.ScratchPath); 149 } else if (!Paths.isFindingAmbiguities()) { 150 // We found a path and we don't care about ambiguities; 151 // return immediately. 152 return FoundPath; 153 } 154 } else if (VisitBase) { 155 CXXRecordDecl *BaseRecord 156 = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>() 157 ->getDecl()); 158 if (BaseRecord->lookupInBases(BaseMatches, UserData, Paths)) { 159 // C++ [class.member.lookup]p2: 160 // A member name f in one sub-object B hides a member name f in 161 // a sub-object A if A is a base class sub-object of B. Any 162 // declarations that are so hidden are eliminated from 163 // consideration. 164 165 // There is a path to a base class that meets the criteria. If we're 166 // not collecting paths or finding ambiguities, we're done. 167 FoundPath = true; 168 if (!Paths.isFindingAmbiguities()) 169 return FoundPath; 170 } 171 } 172 173 // Pop this base specifier off the current path (if we're 174 // collecting paths). 175 if (Paths.isRecordingPaths()) 176 Paths.ScratchPath.pop_back(); 177 // If we set a virtual earlier, and this isn't a path, forget it again. 178 if (SetVirtual && !FoundPath) { 179 Paths.DetectedVirtual = 0; 180 } 181 } 182 183 return FoundPath; 184} 185 186bool CXXRecordDecl::FindBaseClass(CXXBaseSpecifier *Specifier, 187 CXXBasePath &Path, 188 void *BaseRecord) { 189 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord && 190 "User data for FindBaseClass is not canonical!"); 191 return Specifier->getType()->getAs<RecordType>()->getDecl() 192 ->getCanonicalDecl() == BaseRecord; 193} 194 195bool CXXRecordDecl::FindTagMember(CXXBaseSpecifier *Specifier, 196 CXXBasePath &Path, 197 void *Name) { 198 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 199 200 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 201 for (Path.Decls = BaseRecord->lookup(N); 202 Path.Decls.first != Path.Decls.second; 203 ++Path.Decls.first) { 204 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 205 return true; 206 } 207 208 return false; 209} 210 211bool CXXRecordDecl::FindOrdinaryMember(CXXBaseSpecifier *Specifier, 212 CXXBasePath &Path, 213 void *Name) { 214 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 215 216 const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member; 217 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 218 for (Path.Decls = BaseRecord->lookup(N); 219 Path.Decls.first != Path.Decls.second; 220 ++Path.Decls.first) { 221 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS)) 222 return true; 223 } 224 225 return false; 226} 227 228bool CXXRecordDecl::FindNestedNameSpecifierMember(CXXBaseSpecifier *Specifier, 229 CXXBasePath &Path, 230 void *Name) { 231 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 232 233 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 234 for (Path.Decls = BaseRecord->lookup(N); 235 Path.Decls.first != Path.Decls.second; 236 ++Path.Decls.first) { 237 // FIXME: Refactor the "is it a nested-name-specifier?" check 238 if (isa<TypedefDecl>(*Path.Decls.first) || 239 (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 240 return true; 241 } 242 243 return false; 244} 245