CXXInheritance.cpp revision 202879
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) const { 80 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, 81 /*DetectVirtual=*/false); 82 return isDerivedFrom(Base, Paths); 83} 84 85bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base, CXXBasePaths &Paths) const { 86 if (getCanonicalDecl() == Base->getCanonicalDecl()) 87 return false; 88 89 Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); 90 return lookupInBases(&FindBaseClass, Base->getCanonicalDecl(), Paths); 91} 92 93static bool BaseIsNot(const CXXRecordDecl *Base, void *OpaqueTarget) { 94 // OpaqueTarget is a CXXRecordDecl*. 95 return Base->getCanonicalDecl() != (const CXXRecordDecl*) OpaqueTarget; 96} 97 98bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const { 99 return forallBases(BaseIsNot, (void*) Base->getCanonicalDecl()); 100} 101 102bool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches, 103 void *OpaqueData, 104 bool AllowShortCircuit) const { 105 ASTContext &Context = getASTContext(); 106 llvm::SmallVector<const CXXRecordDecl*, 8> Queue; 107 108 const CXXRecordDecl *Record = this; 109 bool AllMatches = true; 110 while (true) { 111 for (CXXRecordDecl::base_class_const_iterator 112 I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) { 113 const RecordType *Ty = I->getType()->getAs<RecordType>(); 114 if (!Ty) { 115 if (AllowShortCircuit) return false; 116 AllMatches = false; 117 continue; 118 } 119 120 CXXRecordDecl *Base = 121 cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition(Context)); 122 if (!Base) { 123 if (AllowShortCircuit) return false; 124 AllMatches = false; 125 continue; 126 } 127 128 Queue.push_back(Base); 129 if (!BaseMatches(Base, OpaqueData)) { 130 if (AllowShortCircuit) return false; 131 AllMatches = false; 132 continue; 133 } 134 } 135 136 if (Queue.empty()) break; 137 Record = Queue.back(); // not actually a queue. 138 Queue.pop_back(); 139 } 140 141 return AllMatches; 142} 143 144bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches, 145 void *UserData, 146 CXXBasePaths &Paths) const { 147 bool FoundPath = false; 148 149 // The access of the path down to this record. 150 AccessSpecifier AccessToHere = Paths.ScratchPath.Access; 151 bool IsFirstStep = Paths.ScratchPath.empty(); 152 153 ASTContext &Context = getASTContext(); 154 for (base_class_const_iterator BaseSpec = bases_begin(), 155 BaseSpecEnd = bases_end(); BaseSpec != BaseSpecEnd; ++BaseSpec) { 156 // Find the record of the base class subobjects for this type. 157 QualType BaseType = Context.getCanonicalType(BaseSpec->getType()) 158 .getUnqualifiedType(); 159 160 // C++ [temp.dep]p3: 161 // In the definition of a class template or a member of a class template, 162 // if a base class of the class template depends on a template-parameter, 163 // the base class scope is not examined during unqualified name lookup 164 // either at the point of definition of the class template or member or 165 // during an instantiation of the class tem- plate or member. 166 if (BaseType->isDependentType()) 167 continue; 168 169 // Determine whether we need to visit this base class at all, 170 // updating the count of subobjects appropriately. 171 std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType]; 172 bool VisitBase = true; 173 bool SetVirtual = false; 174 if (BaseSpec->isVirtual()) { 175 VisitBase = !Subobjects.first; 176 Subobjects.first = true; 177 if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) { 178 // If this is the first virtual we find, remember it. If it turns out 179 // there is no base path here, we'll reset it later. 180 Paths.DetectedVirtual = BaseType->getAs<RecordType>(); 181 SetVirtual = true; 182 } 183 } else 184 ++Subobjects.second; 185 186 if (Paths.isRecordingPaths()) { 187 // Add this base specifier to the current path. 188 CXXBasePathElement Element; 189 Element.Base = &*BaseSpec; 190 Element.Class = this; 191 if (BaseSpec->isVirtual()) 192 Element.SubobjectNumber = 0; 193 else 194 Element.SubobjectNumber = Subobjects.second; 195 Paths.ScratchPath.push_back(Element); 196 197 // Calculate the "top-down" access to this base class. 198 // The spec actually describes this bottom-up, but top-down is 199 // equivalent because the definition works out as follows: 200 // 1. Write down the access along each step in the inheritance 201 // chain, followed by the access of the decl itself. 202 // For example, in 203 // class A { public: int foo; }; 204 // class B : protected A {}; 205 // class C : public B {}; 206 // class D : private C {}; 207 // we would write: 208 // private public protected public 209 // 2. If 'private' appears anywhere except far-left, access is denied. 210 // 3. Otherwise, overall access is determined by the most restrictive 211 // access in the sequence. 212 if (IsFirstStep) 213 Paths.ScratchPath.Access = BaseSpec->getAccessSpecifier(); 214 else 215 Paths.ScratchPath.Access 216 = MergeAccess(AccessToHere, BaseSpec->getAccessSpecifier()); 217 } 218 219 if (BaseMatches(BaseSpec, Paths.ScratchPath, UserData)) { 220 // We've found a path that terminates at this base. 221 FoundPath = true; 222 if (Paths.isRecordingPaths()) { 223 // We have a path. Make a copy of it before moving on. 224 Paths.Paths.push_back(Paths.ScratchPath); 225 } else if (!Paths.isFindingAmbiguities()) { 226 // We found a path and we don't care about ambiguities; 227 // return immediately. 228 return FoundPath; 229 } 230 } else if (VisitBase) { 231 CXXRecordDecl *BaseRecord 232 = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>() 233 ->getDecl()); 234 if (BaseRecord->lookupInBases(BaseMatches, UserData, Paths)) { 235 // C++ [class.member.lookup]p2: 236 // A member name f in one sub-object B hides a member name f in 237 // a sub-object A if A is a base class sub-object of B. Any 238 // declarations that are so hidden are eliminated from 239 // consideration. 240 241 // There is a path to a base class that meets the criteria. If we're 242 // not collecting paths or finding ambiguities, we're done. 243 FoundPath = true; 244 if (!Paths.isFindingAmbiguities()) 245 return FoundPath; 246 } 247 } 248 249 // Pop this base specifier off the current path (if we're 250 // collecting paths). 251 if (Paths.isRecordingPaths()) { 252 Paths.ScratchPath.pop_back(); 253 } 254 255 // If we set a virtual earlier, and this isn't a path, forget it again. 256 if (SetVirtual && !FoundPath) { 257 Paths.DetectedVirtual = 0; 258 } 259 } 260 261 // Reset the scratch path access. 262 Paths.ScratchPath.Access = AccessToHere; 263 264 return FoundPath; 265} 266 267bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, 268 CXXBasePath &Path, 269 void *BaseRecord) { 270 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord && 271 "User data for FindBaseClass is not canonical!"); 272 return Specifier->getType()->getAs<RecordType>()->getDecl() 273 ->getCanonicalDecl() == BaseRecord; 274} 275 276bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier, 277 CXXBasePath &Path, 278 void *Name) { 279 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 280 281 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 282 for (Path.Decls = BaseRecord->lookup(N); 283 Path.Decls.first != Path.Decls.second; 284 ++Path.Decls.first) { 285 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 286 return true; 287 } 288 289 return false; 290} 291 292bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier, 293 CXXBasePath &Path, 294 void *Name) { 295 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 296 297 const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member; 298 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 299 for (Path.Decls = BaseRecord->lookup(N); 300 Path.Decls.first != Path.Decls.second; 301 ++Path.Decls.first) { 302 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS)) 303 return true; 304 } 305 306 return false; 307} 308 309bool CXXRecordDecl:: 310FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, 311 CXXBasePath &Path, 312 void *Name) { 313 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 314 315 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 316 for (Path.Decls = BaseRecord->lookup(N); 317 Path.Decls.first != Path.Decls.second; 318 ++Path.Decls.first) { 319 // FIXME: Refactor the "is it a nested-name-specifier?" check 320 if (isa<TypedefDecl>(*Path.Decls.first) || 321 (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 322 return true; 323 } 324 325 return false; 326} 327