CXXInheritance.cpp source code [clang_source_code/lib/AST/CXXInheritance.cpp]

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