Coverage Report

Created: 2022-01-25 06:29

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