| 1 |
//===- CXXInheritance.cpp - C++ Inheritance -------------------------------===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// This file provides routines that help analyzing C++ inheritance hierarchies. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
|
| 13 |
#include "clang/AST/CXXInheritance.h" |
| 14 |
#include "clang/AST/ASTContext.h" |
| 15 |
#include "clang/AST/Decl.h" |
| 16 |
#include "clang/AST/DeclBase.h" |
| 17 |
#include "clang/AST/DeclCXX.h" |
| 18 |
#include "clang/AST/DeclTemplate.h" |
| 19 |
#include "clang/AST/RecordLayout.h" |
| 20 |
#include "clang/AST/TemplateName.h" |
| 21 |
#include "clang/AST/Type.h" |
| 22 |
#include "clang/Basic/LLVM.h" |
| 23 |
#include "llvm/ADT/DenseMap.h" |
| 24 |
#include "llvm/ADT/STLExtras.h" |
| 25 |
#include "llvm/ADT/SmallVector.h" |
| 26 |
#include "llvm/ADT/iterator_range.h" |
| 27 |
#include "llvm/Support/Casting.h" |
| 28 |
#include <algorithm> |
| 29 |
#include <utility> |
| 30 |
#include <cassert> |
| 31 |
#include <vector> |
| 32 |
|
| 33 |
using namespace clang; |
| 34 |
|
| 35 |
/// isAmbiguous - Determines whether the set of paths provided is |
| 36 |
/// ambiguous, i.e., there are two or more paths that refer to |
| 37 |
/// different base class subobjects of the same type. BaseType must be |
| 38 |
/// an unqualified, canonical class type. |
| 39 |
bool CXXBasePaths::isAmbiguous(CanQualType BaseType) { |
| 40 |
BaseType = BaseType.getUnqualifiedType(); |
| 41 |
IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType]; |
| 42 |
return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 1 : 0) > 1; |
| 43 |
} |
| 44 |
|
| 45 |
/// clear - Clear out all prior path information. |
| 46 |
void CXXBasePaths::clear() { |
| 47 |
Paths.clear(); |
| 48 |
ClassSubobjects.clear(); |
| 49 |
VisitedDependentRecords.clear(); |
| 50 |
ScratchPath.clear(); |
| 51 |
DetectedVirtual = nullptr; |
| 52 |
} |
| 53 |
|
| 54 |
/// Swaps the contents of this CXXBasePaths structure with the |
| 55 |
/// contents of Other. |
| 56 |
void CXXBasePaths::swap(CXXBasePaths &Other) { |
| 57 |
std::swap(Origin, Other.Origin); |
| 58 |
Paths.swap(Other.Paths); |
| 59 |
ClassSubobjects.swap(Other.ClassSubobjects); |
| 60 |
VisitedDependentRecords.swap(Other.VisitedDependentRecords); |
| 61 |
std::swap(FindAmbiguities, Other.FindAmbiguities); |
| 62 |
std::swap(RecordPaths, Other.RecordPaths); |
| 63 |
std::swap(DetectVirtual, Other.DetectVirtual); |
| 64 |
std::swap(DetectedVirtual, Other.DetectedVirtual); |
| 65 |
} |
| 66 |
|
| 67 |
bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const { |
| 68 |
CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
| 69 |
/*DetectVirtual=*/false); |
| 70 |
return isDerivedFrom(Base, Paths); |
| 71 |
} |
| 72 |
|
| 73 |
bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base, |
| 74 |
CXXBasePaths &Paths) const { |
| 75 |
if (getCanonicalDecl() == Base->getCanonicalDecl()) |
| 76 |
return false; |
| 77 |
|
| 78 |
Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); |
| 79 |
|
| 80 |
const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl(); |
| 81 |
return lookupInBases( |
| 82 |
[BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
| 83 |
return FindBaseClass(Specifier, Path, BaseDecl); |
| 84 |
}, |
| 85 |
Paths); |
| 86 |
} |
| 87 |
|
| 88 |
bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const { |
| 89 |
if (!getNumVBases()) |
| 90 |
return false; |
| 91 |
|
| 92 |
CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false, |
| 93 |
/*DetectVirtual=*/false); |
| 94 |
|
| 95 |
if (getCanonicalDecl() == Base->getCanonicalDecl()) |
| 96 |
return false; |
| 97 |
|
| 98 |
Paths.setOrigin(const_cast<CXXRecordDecl*>(this)); |
| 99 |
|
| 100 |
const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl(); |
| 101 |
return lookupInBases( |
| 102 |
[BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
| 103 |
return FindVirtualBaseClass(Specifier, Path, BaseDecl); |
| 104 |
}, |
| 105 |
Paths); |
| 106 |
} |
| 107 |
|
| 108 |
bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const { |
| 109 |
const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl(); |
| 110 |
return forallBases([TargetDecl](const CXXRecordDecl *Base) { |
| 111 |
return Base->getCanonicalDecl() != TargetDecl; |
| 112 |
}); |
| 113 |
} |
| 114 |
|
| 115 |
bool |
| 116 |
CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const { |
| 117 |
assert(isDependentContext()); |
| 118 |
|
| 119 |
for (; !CurContext->isFileContext(); CurContext = CurContext->getParent()) |
| 120 |
if (CurContext->Equals(this)) |
| 121 |
return true; |
| 122 |
|
| 123 |
return false; |
| 124 |
} |
| 125 |
|
| 126 |
bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches) const { |
| 127 |
SmallVector<const CXXRecordDecl*, 8> Queue; |
| 128 |
|
| 129 |
const CXXRecordDecl *Record = this; |
| 130 |
while (true) { |
| 131 |
for (const auto &I : Record->bases()) { |
| 132 |
const RecordType *Ty = I.getType()->getAs<RecordType>(); |
| 133 |
if (!Ty) |
| 134 |
return false; |
| 135 |
|
| 136 |
CXXRecordDecl *Base = |
| 137 |
cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition()); |
| 138 |
if (!Base || |
| 139 |
(Base->isDependentContext() && |
| 140 |
!Base->isCurrentInstantiation(Record))) { |
| 141 |
return false; |
| 142 |
} |
| 143 |
|
| 144 |
Queue.push_back(Base); |
| 145 |
if (!BaseMatches(Base)) |
| 146 |
return false; |
| 147 |
} |
| 148 |
|
| 149 |
if (Queue.empty()) |
| 150 |
break; |
| 151 |
Record = Queue.pop_back_val(); // not actually a queue. |
| 152 |
} |
| 153 |
|
| 154 |
return true; |
| 155 |
} |
| 156 |
|
| 157 |
bool CXXBasePaths::lookupInBases(ASTContext &Context, |
| 158 |
const CXXRecordDecl *Record, |
| 159 |
CXXRecordDecl::BaseMatchesCallback BaseMatches, |
| 160 |
bool LookupInDependent) { |
| 161 |
bool FoundPath = false; |
| 162 |
|
| 163 |
// The access of the path down to this record. |
| 164 |
AccessSpecifier AccessToHere = ScratchPath.Access; |
| 165 |
bool IsFirstStep = ScratchPath.empty(); |
| 166 |
|
| 167 |
for (const auto &BaseSpec : Record->bases()) { |
| 168 |
// Find the record of the base class subobjects for this type. |
| 169 |
QualType BaseType = |
| 170 |
Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType(); |
| 171 |
|
| 172 |
// C++ [temp.dep]p3: |
| 173 |
// In the definition of a class template or a member of a class template, |
| 174 |
// if a base class of the class template depends on a template-parameter, |
| 175 |
// the base class scope is not examined during unqualified name lookup |
| 176 |
// either at the point of definition of the class template or member or |
| 177 |
// during an instantiation of the class tem- plate or member. |
| 178 |
if (!LookupInDependent && BaseType->isDependentType()) |
| 179 |
continue; |
| 180 |
|
| 181 |
// Determine whether we need to visit this base class at all, |
| 182 |
// updating the count of subobjects appropriately. |
| 183 |
IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType]; |
| 184 |
bool VisitBase = true; |
| 185 |
bool SetVirtual = false; |
| 186 |
if (BaseSpec.isVirtual()) { |
| 187 |
VisitBase = !Subobjects.IsVirtBase; |
| 188 |
Subobjects.IsVirtBase = true; |
| 189 |
if (isDetectingVirtual() && DetectedVirtual == nullptr) { |
| 190 |
// If this is the first virtual we find, remember it. If it turns out |
| 191 |
// there is no base path here, we'll reset it later. |
| 192 |
DetectedVirtual = BaseType->getAs<RecordType>(); |
| 193 |
SetVirtual = true; |
| 194 |
} |
| 195 |
} else { |
| 196 |
++Subobjects.NumberOfNonVirtBases; |
| 197 |
} |
| 198 |
if (isRecordingPaths()) { |
| 199 |
// Add this base specifier to the current path. |
| 200 |
CXXBasePathElement Element; |
| 201 |
Element.Base = &BaseSpec; |
| 202 |
Element.Class = Record; |
| 203 |
if (BaseSpec.isVirtual()) |
| 204 |
Element.SubobjectNumber = 0; |
| 205 |
else |
| 206 |
Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases; |
| 207 |
ScratchPath.push_back(Element); |
| 208 |
|
| 209 |
// Calculate the "top-down" access to this base class. |
| 210 |
// The spec actually describes this bottom-up, but top-down is |
| 211 |
// equivalent because the definition works out as follows: |
| 212 |
// 1. Write down the access along each step in the inheritance |
| 213 |
// chain, followed by the access of the decl itself. |
| 214 |
// For example, in |
| 215 |
// class A { public: int foo; }; |
| 216 |
// class B : protected A {}; |
| 217 |
// class C : public B {}; |
| 218 |
// class D : private C {}; |
| 219 |
// we would write: |
| 220 |
// private public protected public |
| 221 |
// 2. If 'private' appears anywhere except far-left, access is denied. |
| 222 |
// 3. Otherwise, overall access is determined by the most restrictive |
| 223 |
// access in the sequence. |
| 224 |
if (IsFirstStep) |
| 225 |
ScratchPath.Access = BaseSpec.getAccessSpecifier(); |
| 226 |
else |
| 227 |
ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere, |
| 228 |
BaseSpec.getAccessSpecifier()); |
| 229 |
} |
| 230 |
|
| 231 |
// Track whether there's a path involving this specific base. |
| 232 |
bool FoundPathThroughBase = false; |
| 233 |
|
| 234 |
if (BaseMatches(&BaseSpec, ScratchPath)) { |
| 235 |
// We've found a path that terminates at this base. |
| 236 |
FoundPath = FoundPathThroughBase = true; |
| 237 |
if (isRecordingPaths()) { |
| 238 |
// We have a path. Make a copy of it before moving on. |
| 239 |
Paths.push_back(ScratchPath); |
| 240 |
} else if (!isFindingAmbiguities()) { |
| 241 |
// We found a path and we don't care about ambiguities; |
| 242 |
// return immediately. |
| 243 |
return FoundPath; |
| 244 |
} |
| 245 |
} else if (VisitBase) { |
| 246 |
CXXRecordDecl *BaseRecord; |
| 247 |
if (LookupInDependent) { |
| 248 |
BaseRecord = nullptr; |
| 249 |
const TemplateSpecializationType *TST = |
| 250 |
BaseSpec.getType()->getAs<TemplateSpecializationType>(); |
| 251 |
if (!TST) { |
| 252 |
if (auto *RT = BaseSpec.getType()->getAs<RecordType>()) |
| 253 |
BaseRecord = cast<CXXRecordDecl>(RT->getDecl()); |
| 254 |
} else { |
| 255 |
TemplateName TN = TST->getTemplateName(); |
| 256 |
if (auto *TD = |
| 257 |
dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl())) |
| 258 |
BaseRecord = TD->getTemplatedDecl(); |
| 259 |
} |
| 260 |
if (BaseRecord) { |
| 261 |
if (!BaseRecord->hasDefinition() || |
| 262 |
VisitedDependentRecords.count(BaseRecord)) { |
| 263 |
BaseRecord = nullptr; |
| 264 |
} else { |
| 265 |
VisitedDependentRecords.insert(BaseRecord); |
| 266 |
} |
| 267 |
} |
| 268 |
} else { |
| 269 |
BaseRecord = cast<CXXRecordDecl>( |
| 270 |
BaseSpec.getType()->castAs<RecordType>()->getDecl()); |
| 271 |
} |
| 272 |
if (BaseRecord && |
| 273 |
lookupInBases(Context, BaseRecord, BaseMatches, LookupInDependent)) { |
| 274 |
// C++ [class.member.lookup]p2: |
| 275 |
// A member name f in one sub-object B hides a member name f in |
| 276 |
// a sub-object A if A is a base class sub-object of B. Any |
| 277 |
// declarations that are so hidden are eliminated from |
| 278 |
// consideration. |
| 279 |
|
| 280 |
// There is a path to a base class that meets the criteria. If we're |
| 281 |
// not collecting paths or finding ambiguities, we're done. |
| 282 |
FoundPath = FoundPathThroughBase = true; |
| 283 |
if (!isFindingAmbiguities()) |
| 284 |
return FoundPath; |
| 285 |
} |
| 286 |
} |
| 287 |
|
| 288 |
// Pop this base specifier off the current path (if we're |
| 289 |
// collecting paths). |
| 290 |
if (isRecordingPaths()) { |
| 291 |
ScratchPath.pop_back(); |
| 292 |
} |
| 293 |
|
| 294 |
// If we set a virtual earlier, and this isn't a path, forget it again. |
| 295 |
if (SetVirtual && !FoundPathThroughBase) { |
| 296 |
DetectedVirtual = nullptr; |
| 297 |
} |
| 298 |
} |
| 299 |
|
| 300 |
// Reset the scratch path access. |
| 301 |
ScratchPath.Access = AccessToHere; |
| 302 |
|
| 303 |
return FoundPath; |
| 304 |
} |
| 305 |
|
| 306 |
bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches, |
| 307 |
CXXBasePaths &Paths, |
| 308 |
bool LookupInDependent) const { |
| 309 |
// If we didn't find anything, report that. |
| 310 |
if (!Paths.lookupInBases(getASTContext(), this, BaseMatches, |
| 311 |
LookupInDependent)) |
| 312 |
return false; |
| 313 |
|
| 314 |
// If we're not recording paths or we won't ever find ambiguities, |
| 315 |
// we're done. |
| 316 |
if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities()) |
| 317 |
return true; |
| 318 |
|
| 319 |
// C++ [class.member.lookup]p6: |
| 320 |
// When virtual base classes are used, a hidden declaration can be |
| 321 |
// reached along a path through the sub-object lattice that does |
| 322 |
// not pass through the hiding declaration. This is not an |
| 323 |
// ambiguity. The identical use with nonvirtual base classes is an |
| 324 |
// ambiguity; in that case there is no unique instance of the name |
| 325 |
// that hides all the others. |
| 326 |
// |
| 327 |
// FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy |
| 328 |
// way to make it any faster. |
| 329 |
Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) { |
| 330 |
for (const CXXBasePathElement &PE : Path) { |
| 331 |
if (!PE.Base->isVirtual()) |
| 332 |
continue; |
| 333 |
|
| 334 |
CXXRecordDecl *VBase = nullptr; |
| 335 |
if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>()) |
| 336 |
VBase = cast<CXXRecordDecl>(Record->getDecl()); |
| 337 |
if (!VBase) |
| 338 |
break; |
| 339 |
|
| 340 |
// The declaration(s) we found along this path were found in a |
| 341 |
// subobject of a virtual base. Check whether this virtual |
| 342 |
// base is a subobject of any other path; if so, then the |
| 343 |
// declaration in this path are hidden by that patch. |
| 344 |
for (const CXXBasePath &HidingP : Paths) { |
| 345 |
CXXRecordDecl *HidingClass = nullptr; |
| 346 |
if (const RecordType *Record = |
| 347 |
HidingP.back().Base->getType()->getAs<RecordType>()) |
| 348 |
HidingClass = cast<CXXRecordDecl>(Record->getDecl()); |
| 349 |
if (!HidingClass) |
| 350 |
break; |
| 351 |
|
| 352 |
if (HidingClass->isVirtuallyDerivedFrom(VBase)) |
| 353 |
return true; |
| 354 |
} |
| 355 |
} |
| 356 |
return false; |
| 357 |
}); |
| 358 |
|
| 359 |
return true; |
| 360 |
} |
| 361 |
|
| 362 |
bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier, |
| 363 |
CXXBasePath &Path, |
| 364 |
const CXXRecordDecl *BaseRecord) { |
| 365 |
assert(BaseRecord->getCanonicalDecl() == BaseRecord && |
| 366 |
"User data for FindBaseClass is not canonical!"); |
| 367 |
return Specifier->getType()->castAs<RecordType>()->getDecl() |
| 368 |
->getCanonicalDecl() == BaseRecord; |
| 369 |
} |
| 370 |
|
| 371 |
bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier, |
| 372 |
CXXBasePath &Path, |
| 373 |
const CXXRecordDecl *BaseRecord) { |
| 374 |
assert(BaseRecord->getCanonicalDecl() == BaseRecord && |
| 375 |
"User data for FindBaseClass is not canonical!"); |
| 376 |
return Specifier->isVirtual() && |
| 377 |
Specifier->getType()->castAs<RecordType>()->getDecl() |
| 378 |
->getCanonicalDecl() == BaseRecord; |
| 379 |
} |
| 380 |
|
| 381 |
static bool isOrdinaryMember(const NamedDecl *ND) { |
| 382 |
return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag | |
| 383 |
Decl::IDNS_Member); |
| 384 |
} |
| 385 |
|
| 386 |
static bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path, |
| 387 |
DeclarationName Name) { |
| 388 |
Path.Decls = RD->lookup(Name).begin(); |
| 389 |
for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I) |
| 390 |
if (isOrdinaryMember(*I)) |
| 391 |
return true; |
| 392 |
|
| 393 |
return false; |
| 394 |
} |
| 395 |
|
| 396 |
bool CXXRecordDecl::hasMemberName(DeclarationName Name) const { |
| 397 |
CXXBasePath P; |
| 398 |
if (findOrdinaryMember(this, P, Name)) |
| 399 |
return true; |
| 400 |
|
| 401 |
CXXBasePaths Paths(false, false, false); |
| 402 |
return lookupInBases( |
| 403 |
[Name](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
| 404 |
return findOrdinaryMember(Specifier->getType()->getAsCXXRecordDecl(), |
| 405 |
Path, Name); |
| 406 |
}, |
| 407 |
Paths); |
| 408 |
} |
| 409 |
|
| 410 |
static bool |
| 411 |
findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier, |
| 412 |
CXXBasePath &Path, DeclarationName Name) { |
| 413 |
const TemplateSpecializationType *TST = |
| 414 |
Specifier->getType()->getAs<TemplateSpecializationType>(); |
| 415 |
if (!TST) { |
| 416 |
auto *RT = Specifier->getType()->getAs<RecordType>(); |
| 417 |
if (!RT) |
| 418 |
return false; |
| 419 |
return findOrdinaryMember(cast<CXXRecordDecl>(RT->getDecl()), Path, Name); |
| 420 |
} |
| 421 |
TemplateName TN = TST->getTemplateName(); |
| 422 |
const auto *TD = dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl()); |
| 423 |
if (!TD) |
| 424 |
return false; |
| 425 |
CXXRecordDecl *RD = TD->getTemplatedDecl(); |
| 426 |
if (!RD) |
| 427 |
return false; |
| 428 |
return findOrdinaryMember(RD, Path, Name); |
| 429 |
} |
| 430 |
|
| 431 |
std::vector<const NamedDecl *> CXXRecordDecl::lookupDependentName( |
| 432 |
DeclarationName Name, |
| 433 |
llvm::function_ref<bool(const NamedDecl *ND)> Filter) { |
| 434 |
std::vector<const NamedDecl *> Results; |
| 435 |
// Lookup in the class. |
| 436 |
bool AnyOrdinaryMembers = false; |
| 437 |
for (const NamedDecl *ND : lookup(Name)) { |
| 438 |
if (isOrdinaryMember(ND)) |
| 439 |
AnyOrdinaryMembers = true; |
| 440 |
if (Filter(ND)) |
| 441 |
Results.push_back(ND); |
| 442 |
} |
| 443 |
if (AnyOrdinaryMembers) |
| 444 |
return Results; |
| 445 |
|
| 446 |
// Perform lookup into our base classes. |
| 447 |
CXXBasePaths Paths; |
| 448 |
Paths.setOrigin(this); |
| 449 |
if (!lookupInBases( |
| 450 |
[&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) { |
| 451 |
return findOrdinaryMemberInDependentClasses(Specifier, Path, Name); |
| 452 |
}, |
| 453 |
Paths, /*LookupInDependent=*/true)) |
| 454 |
return Results; |
| 455 |
for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end(); |
| 456 |
I != E; ++I) { |
| 457 |
if (isOrdinaryMember(*I) && Filter(*I)) |
| 458 |
Results.push_back(*I); |
| 459 |
} |
| 460 |
return Results; |
| 461 |
} |
| 462 |
|
| 463 |
void OverridingMethods::add(unsigned OverriddenSubobject, |
| 464 |
UniqueVirtualMethod Overriding) { |
| 465 |
SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides |
| 466 |
= Overrides[OverriddenSubobject]; |
| 467 |
if (!llvm::is_contained(SubobjectOverrides, Overriding)) |
| 468 |
SubobjectOverrides.push_back(Overriding); |
| 469 |
} |
| 470 |
|
| 471 |
void OverridingMethods::add(const OverridingMethods &Other) { |
| 472 |
for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; ++I) { |
| 473 |
for (overriding_const_iterator M = I->second.begin(), |
| 474 |
MEnd = I->second.end(); |
| 475 |
M != MEnd; |
| 476 |
++M) |
| 477 |
add(I->first, *M); |
| 478 |
} |
| 479 |
} |
| 480 |
|
| 481 |
void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) { |
| 482 |
for (iterator I = begin(), IEnd = end(); I != IEnd; ++I) { |
| 483 |
I->second.clear(); |
| 484 |
I->second.push_back(Overriding); |
| 485 |
} |
| 486 |
} |
| 487 |
|
| 488 |
namespace { |
| 489 |
|
| 490 |
class FinalOverriderCollector { |
| 491 |
/// The number of subobjects of a given class type that |
| 492 |
/// occur within the class hierarchy. |
| 493 |
llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount; |
| 494 |
|
| 495 |
/// Overriders for each virtual base subobject. |
| 496 |
llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders; |
| 497 |
|
| 498 |
CXXFinalOverriderMap FinalOverriders; |
| 499 |
|
| 500 |
public: |
| 501 |
~FinalOverriderCollector(); |
| 502 |
|
| 503 |
void Collect(const CXXRecordDecl *RD, bool VirtualBase, |
| 504 |
const CXXRecordDecl *InVirtualSubobject, |
| 505 |
CXXFinalOverriderMap &Overriders); |
| 506 |
}; |
| 507 |
|
| 508 |
} // namespace |
| 509 |
|
| 510 |
void FinalOverriderCollector::Collect(const CXXRecordDecl *RD, |
| 511 |
bool VirtualBase, |
| 512 |
const CXXRecordDecl *InVirtualSubobject, |
| 513 |
CXXFinalOverriderMap &Overriders) { |
| 514 |
unsigned SubobjectNumber = 0; |
| 515 |
if (!VirtualBase) |
| 516 |
SubobjectNumber |
| 517 |
= ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())]; |
| 518 |
|
| 519 |
for (const auto &Base : RD->bases()) { |
| 520 |
if (const RecordType *RT = Base.getType()->getAs<RecordType>()) { |
| 521 |
const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl()); |
| 522 |
if (!BaseDecl->isPolymorphic()) |
| 523 |
continue; |
| 524 |
|
| 525 |
if (Overriders.empty() && !Base.isVirtual()) { |
| 526 |
// There are no other overriders of virtual member functions, |
| 527 |
// so let the base class fill in our overriders for us. |
| 528 |
Collect(BaseDecl, false, InVirtualSubobject, Overriders); |
| 529 |
continue; |
| 530 |
} |
| 531 |
|
| 532 |
// Collect all of the overridders from the base class subobject |
| 533 |
// and merge them into the set of overridders for this class. |
| 534 |
// For virtual base classes, populate or use the cached virtual |
| 535 |
// overrides so that we do not walk the virtual base class (and |
| 536 |
// its base classes) more than once. |
| 537 |
CXXFinalOverriderMap ComputedBaseOverriders; |
| 538 |
CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders; |
| 539 |
if (Base.isVirtual()) { |
| 540 |
CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl]; |
| 541 |
BaseOverriders = MyVirtualOverriders; |
| 542 |
if (!MyVirtualOverriders) { |
| 543 |
MyVirtualOverriders = new CXXFinalOverriderMap; |
| 544 |
|
| 545 |
// Collect may cause VirtualOverriders to reallocate, invalidating the |
| 546 |
// MyVirtualOverriders reference. Set BaseOverriders to the right |
| 547 |
// value now. |
| 548 |
BaseOverriders = MyVirtualOverriders; |
| 549 |
|
| 550 |
Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders); |
| 551 |
} |
| 552 |
} else |
| 553 |
Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders); |
| 554 |
|
| 555 |
// Merge the overriders from this base class into our own set of |
| 556 |
// overriders. |
| 557 |
for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(), |
| 558 |
OMEnd = BaseOverriders->end(); |
| 559 |
OM != OMEnd; |
| 560 |
++OM) { |
| 561 |
const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl(); |
| 562 |
Overriders[CanonOM].add(OM->second); |
| 563 |
} |
| 564 |
} |
| 565 |
} |
| 566 |
|
| 567 |
for (auto *M : RD->methods()) { |
| 568 |
// We only care about virtual methods. |
| 569 |
if (!M->isVirtual()) |
| 570 |
continue; |
| 571 |
|
| 572 |
CXXMethodDecl *CanonM = M->getCanonicalDecl(); |
| 573 |
using OverriddenMethodsRange = |
| 574 |
llvm::iterator_range<CXXMethodDecl::method_iterator>; |
| 575 |
OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods(); |
| 576 |
|
| 577 |
if (OverriddenMethods.begin() == OverriddenMethods.end()) { |
| 578 |
// This is a new virtual function that does not override any |
| 579 |
// other virtual function. Add it to the map of virtual |
| 580 |
// functions for which we are tracking overridders. |
| 581 |
|
| 582 |
// C++ [class.virtual]p2: |
| 583 |
// For convenience we say that any virtual function overrides itself. |
| 584 |
Overriders[CanonM].add(SubobjectNumber, |
| 585 |
UniqueVirtualMethod(CanonM, SubobjectNumber, |
| 586 |
InVirtualSubobject)); |
| 587 |
continue; |
| 588 |
} |
| 589 |
|
| 590 |
// This virtual method overrides other virtual methods, so it does |
| 591 |
// not add any new slots into the set of overriders. Instead, we |
| 592 |
// replace entries in the set of overriders with the new |
| 593 |
// overrider. To do so, we dig down to the original virtual |
| 594 |
// functions using data recursion and update all of the methods it |
| 595 |
// overrides. |
| 596 |
SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods); |
| 597 |
while (!Stack.empty()) { |
| 598 |
for (const CXXMethodDecl *OM : Stack.pop_back_val()) { |
| 599 |
const CXXMethodDecl *CanonOM = OM->getCanonicalDecl(); |
| 600 |
|
| 601 |
// C++ [class.virtual]p2: |
| 602 |
// A virtual member function C::vf of a class object S is |
| 603 |
// a final overrider unless the most derived class (1.8) |
| 604 |
// of which S is a base class subobject (if any) declares |
| 605 |
// or inherits another member function that overrides vf. |
| 606 |
// |
| 607 |
// Treating this object like the most derived class, we |
| 608 |
// replace any overrides from base classes with this |
| 609 |
// overriding virtual function. |
| 610 |
Overriders[CanonOM].replaceAll( |
| 611 |
UniqueVirtualMethod(CanonM, SubobjectNumber, |
| 612 |
InVirtualSubobject)); |
| 613 |
|
| 614 |
auto OverriddenMethods = CanonOM->overridden_methods(); |
| 615 |
if (OverriddenMethods.begin() == OverriddenMethods.end()) |
| 616 |
continue; |
| 617 |
|
| 618 |
// Continue recursion to the methods that this virtual method |
| 619 |
// overrides. |
| 620 |
Stack.push_back(OverriddenMethods); |
| 621 |
} |
| 622 |
} |
| 623 |
|
| 624 |
// C++ [class.virtual]p2: |
| 625 |
// For convenience we say that any virtual function overrides itself. |
| 626 |
Overriders[CanonM].add(SubobjectNumber, |
| 627 |
UniqueVirtualMethod(CanonM, SubobjectNumber, |
| 628 |
InVirtualSubobject)); |
| 629 |
} |
| 630 |
} |
| 631 |
|
| 632 |
FinalOverriderCollector::~FinalOverriderCollector() { |
| 633 |
for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator |
| 634 |
VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end(); |
| 635 |
VO != VOEnd; |
| 636 |
++VO) |
| 637 |
delete VO->second; |
| 638 |
} |
| 639 |
|
| 640 |
void |
| 641 |
CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const { |
| 642 |
FinalOverriderCollector Collector; |
| 643 |
Collector.Collect(this, false, nullptr, FinalOverriders); |
| 644 |
|
| 645 |
// Weed out any final overriders that come from virtual base class |
| 646 |
// subobjects that were hidden by other subobjects along any path. |
| 647 |
// This is the final-overrider variant of C++ [class.member.lookup]p10. |
| 648 |
for (auto &OM : FinalOverriders) { |
| 649 |
for (auto &SO : OM.second) { |
| 650 |
SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second; |
| 651 |
if (Overriding.size() < 2) |
| 652 |
continue; |
| 653 |
|
| 654 |
auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) { |
| 655 |
if (!M.InVirtualSubobject) |
| 656 |
return false; |
| 657 |
|
| 658 |
// We have an overriding method in a virtual base class |
| 659 |
// subobject (or non-virtual base class subobject thereof); |
| 660 |
// determine whether there exists an other overriding method |
| 661 |
// in a base class subobject that hides the virtual base class |
| 662 |
// subobject. |
| 663 |
for (const UniqueVirtualMethod &OP : Overriding) |
| 664 |
if (&M != &OP && |
| 665 |
OP.Method->getParent()->isVirtuallyDerivedFrom( |
| 666 |
M.InVirtualSubobject)) |
| 667 |
return true; |
| 668 |
return false; |
| 669 |
}; |
| 670 |
|
| 671 |
// FIXME: IsHidden reads from Overriding from the middle of a remove_if |
| 672 |
// over the same sequence! Is this guaranteed to work? |
| 673 |
llvm::erase_if(Overriding, IsHidden); |
| 674 |
} |
| 675 |
} |
| 676 |
} |
| 677 |
|
| 678 |
static void |
| 679 |
AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context, |
| 680 |
CXXIndirectPrimaryBaseSet& Bases) { |
| 681 |
// If the record has a virtual primary base class, add it to our set. |
| 682 |
const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); |
| 683 |
if (Layout.isPrimaryBaseVirtual()) |
| 684 |
Bases.insert(Layout.getPrimaryBase()); |
| 685 |
|
| 686 |
for (const auto &I : RD->bases()) { |
| 687 |
assert(!I.getType()->isDependentType() && |
| 688 |
"Cannot get indirect primary bases for class with dependent bases."); |
| 689 |
|
| 690 |
const CXXRecordDecl *BaseDecl = |
| 691 |
cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl()); |
| 692 |
|
| 693 |
// Only bases with virtual bases participate in computing the |
| 694 |
// indirect primary virtual base classes. |
| 695 |
if (BaseDecl->getNumVBases()) |
| 696 |
AddIndirectPrimaryBases(BaseDecl, Context, Bases); |
| 697 |
} |
| 698 |
|
| 699 |
} |
| 700 |
|
| 701 |
void |
| 702 |
CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const { |
| 703 |
ASTContext &Context = getASTContext(); |
| 704 |
|
| 705 |
if (!getNumVBases()) |
| 706 |
return; |
| 707 |
|
| 708 |
for (const auto &I : bases()) { |
| 709 |
assert(!I.getType()->isDependentType() && |
| 710 |
"Cannot get indirect primary bases for class with dependent bases."); |
| 711 |
|
| 712 |
const CXXRecordDecl *BaseDecl = |
| 713 |
cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl()); |
| 714 |
|
| 715 |
// Only bases with virtual bases participate in computing the |
| 716 |
// indirect primary virtual base classes. |
| 717 |
if (BaseDecl->getNumVBases()) |
| 718 |
AddIndirectPrimaryBases(BaseDecl, Context, Bases); |
| 719 |
} |
| 720 |
} |