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