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