clang  9.0.0svn
CXXInheritance.cpp
Go to the documentation of this file.
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 
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  assert(NumDeclsFound == 0 && !DeclsFound &&
40  "Already computed the set of declarations");
41 
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 
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.
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.
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.
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 
92  CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
93  /*DetectVirtual=*/false);
94  return isDerivedFrom(Base, Paths);
95 }
96 
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 
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 
133  const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl();
134  return forallBases([TargetDecl](const CXXRecordDecl *Base) {
135  return Base->getCanonicalDecl() != TargetDecl;
136  });
137 }
138 
139 bool
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 
151  bool AllowShortCircuit) const {
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 
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,
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 
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 
397  CXXBasePath &Path,
398  const CXXRecordDecl *BaseRecord) {
399  assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
400  "User data for FindBaseClass is not canonical!");
401  return Specifier->getType()->castAs<RecordType>()->getDecl()
402  ->getCanonicalDecl() == BaseRecord;
403 }
404 
406  CXXBasePath &Path,
407  const CXXRecordDecl *BaseRecord) {
408  assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
409  "User data for FindBaseClass is not canonical!");
410  return Specifier->isVirtual() &&
411  Specifier->getType()->castAs<RecordType>()->getDecl()
412  ->getCanonicalDecl() == BaseRecord;
413 }
414 
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 |
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 
446  CXXBasePath &Path,
447  DeclarationName Name) {
448  RecordDecl *BaseRecord =
449  Specifier->getType()->castAs<RecordType>()->getDecl();
450  return findOrdinaryMember(BaseRecord, Path, Name);
451 }
452 
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 
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 
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::
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) {
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 
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 
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
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
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  assert(!I.getType()->isDependentType() &&
779  "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
794  ASTContext &Context = getASTContext();
795 
796  if (!getNumVBases())
797  return;
798 
799  for (const auto &I : bases()) {
800  assert(!I.getType()->isDependentType() &&
801  "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 }
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:225
A (possibly-)qualified type.
Definition: Type.h:639
base_class_range bases()
Definition: DeclCXX.h:822
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:97
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:6766
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:1236
bool hasDefinition() const
Definition: DeclCXX.h:775
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:3592
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:154
The results of name lookup within a DeclContext.
Definition: DeclBase.h:1189
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:3773
TemplateName getTemplateName() const
Retrieve the name of the template that we are specializing.
Definition: Type.h:4914
CXXMethodDecl * getCanonicalDecl() override
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclCXX.h:2134
bool Equals(const DeclContext *DC) const
Determine whether this declaration context is equivalent to the declaration context DC...
Definition: DeclBase.h:1880
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:1241
CXXRecordDecl * getCanonicalDecl() override
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclCXX.h:727
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:1601
ASTRecordLayout - This class contains layout information for one RecordDecl, which is a struct/union/...
Definition: RecordLayout.h:38
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:6829
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:2185
bool isFileContext() const
Definition: DeclBase.h:1826
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:217
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:1336
DeclContext * getParent()
getParent - Returns the containing DeclContext.
Definition: DeclBase.h:1760
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:1081
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:1747
decl_range found_decls()
RecordDecl * getDecl() const
Definition: Type.h:4390
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: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:2048
static bool FindOMPMapperMember(const CXXBaseSpecifier *Specifier, CXXBasePath &Path, DeclarationName Name)
Base-class lookup callback that determines whether there exists an OpenMP declare mapper member with ...
paths_iterator begin()
llvm::function_ref< bool(const CXXRecordDecl *BaseDefinition)> ForallBasesCallback
Function type used by forallBases() as a callback.
Definition: DeclCXX.h:1717
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:1265
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:125
static AccessSpecifier MergeAccess(AccessSpecifier PathAccess, AccessSpecifier DeclAccess)
Calculates the access of a decl that is reached along a path.
Definition: DeclCXX.h:1871
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:4380
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:2266
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:2086
Represents a type template specialization; the template must be a class template, a type alias templa...
Definition: Type.h:4851
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:248
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:864
QualType getType() const
Retrieves the type of the base class.
Definition: DeclCXX.h:290