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
| 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
|
93bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches, 94 void *UserData, 95 CXXBasePaths &Paths) const { 96 bool FoundPath = false; 97 98 ASTContext &Context = getASTContext(); 99 for (base_class_const_iterator BaseSpec = bases_begin(), 100 BaseSpecEnd = bases_end(); BaseSpec != BaseSpecEnd; ++BaseSpec) { 101 // Find the record of the base class subobjects for this type. 102 QualType BaseType = Context.getCanonicalType(BaseSpec->getType()) 103 .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(const 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(const 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(const 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:: 229FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, 230 CXXBasePath &Path, 231 void *Name) { 232 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 233 234 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 235 for (Path.Decls = BaseRecord->lookup(N); 236 Path.Decls.first != Path.Decls.second; 237 ++Path.Decls.first) { 238 // FIXME: Refactor the "is it a nested-name-specifier?" check 239 if (isa<TypedefDecl>(*Path.Decls.first) || 240 (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 241 return true; 242 } 243 244 return false; 245}
| 144bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches, 145 void *UserData, 146 CXXBasePaths &Paths) const { 147 bool FoundPath = false; 148 149 ASTContext &Context = getASTContext(); 150 for (base_class_const_iterator BaseSpec = bases_begin(), 151 BaseSpecEnd = bases_end(); BaseSpec != BaseSpecEnd; ++BaseSpec) { 152 // Find the record of the base class subobjects for this type. 153 QualType BaseType = Context.getCanonicalType(BaseSpec->getType()) 154 .getUnqualifiedType(); 155 156 // C++ [temp.dep]p3: 157 // In the definition of a class template or a member of a class template, 158 // if a base class of the class template depends on a template-parameter, 159 // the base class scope is not examined during unqualified name lookup 160 // either at the point of definition of the class template or member or 161 // during an instantiation of the class tem- plate or member. 162 if (BaseType->isDependentType()) 163 continue; 164 165 // Determine whether we need to visit this base class at all, 166 // updating the count of subobjects appropriately. 167 std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType]; 168 bool VisitBase = true; 169 bool SetVirtual = false; 170 if (BaseSpec->isVirtual()) { 171 VisitBase = !Subobjects.first; 172 Subobjects.first = true; 173 if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) { 174 // If this is the first virtual we find, remember it. If it turns out 175 // there is no base path here, we'll reset it later. 176 Paths.DetectedVirtual = BaseType->getAs<RecordType>(); 177 SetVirtual = true; 178 } 179 } else 180 ++Subobjects.second; 181 182 if (Paths.isRecordingPaths()) { 183 // Add this base specifier to the current path. 184 CXXBasePathElement Element; 185 Element.Base = &*BaseSpec; 186 Element.Class = this; 187 if (BaseSpec->isVirtual()) 188 Element.SubobjectNumber = 0; 189 else 190 Element.SubobjectNumber = Subobjects.second; 191 Paths.ScratchPath.push_back(Element); 192 } 193 194 if (BaseMatches(BaseSpec, Paths.ScratchPath, UserData)) { 195 // We've found a path that terminates that this base. 196 FoundPath = true; 197 if (Paths.isRecordingPaths()) { 198 // We have a path. Make a copy of it before moving on. 199 Paths.Paths.push_back(Paths.ScratchPath); 200 } else if (!Paths.isFindingAmbiguities()) { 201 // We found a path and we don't care about ambiguities; 202 // return immediately. 203 return FoundPath; 204 } 205 } else if (VisitBase) { 206 CXXRecordDecl *BaseRecord 207 = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>() 208 ->getDecl()); 209 if (BaseRecord->lookupInBases(BaseMatches, UserData, Paths)) { 210 // C++ [class.member.lookup]p2: 211 // A member name f in one sub-object B hides a member name f in 212 // a sub-object A if A is a base class sub-object of B. Any 213 // declarations that are so hidden are eliminated from 214 // consideration. 215 216 // There is a path to a base class that meets the criteria. If we're 217 // not collecting paths or finding ambiguities, we're done. 218 FoundPath = true; 219 if (!Paths.isFindingAmbiguities()) 220 return FoundPath; 221 } 222 } 223 224 // Pop this base specifier off the current path (if we're 225 // collecting paths). 226 if (Paths.isRecordingPaths()) 227 Paths.ScratchPath.pop_back(); 228 // If we set a virtual earlier, and this isn't a path, forget it again. 229 if (SetVirtual && !FoundPath) { 230 Paths.DetectedVirtual = 0; 231 } 232 } 233 234 return FoundPath; 235} 236 237bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, 238 CXXBasePath &Path, 239 void *BaseRecord) { 240 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord && 241 "User data for FindBaseClass is not canonical!"); 242 return Specifier->getType()->getAs<RecordType>()->getDecl() 243 ->getCanonicalDecl() == BaseRecord; 244} 245 246bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier, 247 CXXBasePath &Path, 248 void *Name) { 249 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 250 251 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 252 for (Path.Decls = BaseRecord->lookup(N); 253 Path.Decls.first != Path.Decls.second; 254 ++Path.Decls.first) { 255 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 256 return true; 257 } 258 259 return false; 260} 261 262bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier, 263 CXXBasePath &Path, 264 void *Name) { 265 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 266 267 const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member; 268 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 269 for (Path.Decls = BaseRecord->lookup(N); 270 Path.Decls.first != Path.Decls.second; 271 ++Path.Decls.first) { 272 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS)) 273 return true; 274 } 275 276 return false; 277} 278 279bool CXXRecordDecl:: 280FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier, 281 CXXBasePath &Path, 282 void *Name) { 283 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 284 285 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 286 for (Path.Decls = BaseRecord->lookup(N); 287 Path.Decls.first != Path.Decls.second; 288 ++Path.Decls.first) { 289 // FIXME: Refactor the "is it a nested-name-specifier?" check 290 if (isa<TypedefDecl>(*Path.Decls.first) || 291 (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag)) 292 return true; 293 } 294 295 return false; 296}
|