Coverage Report

Created: 2021-09-21 08:58

/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
39.8k
bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
41
39.8k
  BaseType = BaseType.getUnqualifiedType();
42
39.8k
  IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType];
43
39.8k
  return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 
11.18k
:
038.6k
) > 1;
44
39.8k
}
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
471k
bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
69
471k
  CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
70
471k
                     /*DetectVirtual=*/false);
71
471k
  return isDerivedFrom(Base, Paths);
72
471k
}
73
74
bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
75
576k
                                  CXXBasePaths &Paths) const {
76
576k
  if (getCanonicalDecl() == Base->getCanonicalDecl())
77
29.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
304k
        return FindBaseClass(Specifier, Path, BaseDecl);
85
304k
      },
86
546k
      Paths);
87
576k
}
88
89
8.64k
bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const {
90
8.64k
  if (!getNumVBases())
91
6.76k
    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.8k
bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
110
13.8k
  const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl();
111
14.4k
  return forallBases([TargetDecl](const CXXRecordDecl *Base) {
112
14.4k
    return Base->getCanonicalDecl() != TargetDecl;
113
14.4k
  });
114
13.8k
}
115
116
bool
117
472k
CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const {
118
472k
  assert(isDependentContext());
119
120
495k
  for (; !CurContext->isFileContext(); 
CurContext = CurContext->getParent()23.1k
)
121
480k
    if (CurContext->Equals(this))
122
457k
      return true;
123
124
14.6k
  return false;
125
472k
}
126
127
24.8k
bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches) const {
128
24.8k
  SmallVector<const CXXRecordDecl*, 8> Queue;
129
130
24.8k
  const CXXRecordDecl *Record = this;
131
26.2k
  while (true) {
132
26.2k
    for (const auto &I : Record->bases()) {
133
25.9k
      const RecordType *Ty = I.getType()->getAs<RecordType>();
134
25.9k
      if (!Ty)
135
2.63k
        return false;
136
137
23.3k
      CXXRecordDecl *Base =
138
23.3k
            cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
139
23.3k
      if (!Base ||
140
23.3k
          
(23.3k
Base->isDependentContext()23.3k
&&
141
23.3k
           
!Base->isCurrentInstantiation(Record)6
)) {
142
8
        return false;
143
8
      }
144
145
23.2k
      Queue.push_back(Base);
146
23.2k
      if (!BaseMatches(Base))
147
21.0k
        return false;
148
23.2k
    }
149
150
2.60k
    if (Queue.empty())
151
1.19k
      break;
152
1.40k
    Record = Queue.pop_back_val(); // not actually a queue.
153
1.40k
  }
154
155
1.19k
  return true;
156
24.8k
}
157
158
bool CXXBasePaths::lookupInBases(ASTContext &Context,
159
                                 const CXXRecordDecl *Record,
160
                                 CXXRecordDecl::BaseMatchesCallback BaseMatches,
161
11.0M
                                 bool LookupInDependent) {
162
11.0M
  bool FoundPath = false;
163
164
  // The access of the path down to this record.
165
11.0M
  AccessSpecifier AccessToHere = ScratchPath.Access;
166
11.0M
  bool IsFirstStep = ScratchPath.empty();
167
168
11.0M
  for (const auto &BaseSpec : Record->bases()) {
169
    // Find the record of the base class subobjects for this type.
170
5.22M
    QualType BaseType =
171
5.22M
        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.22M
    if (!LookupInDependent && 
BaseType->isDependentType()5.22M
)
180
778k
      continue;
181
182
    // Determine whether we need to visit this base class at all,
183
    // updating the count of subobjects appropriately.
184
4.44M
    IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType];
185
4.44M
    bool VisitBase = true;
186
4.44M
    bool SetVirtual = false;
187
4.44M
    if (BaseSpec.isVirtual()) {
188
48.8k
      VisitBase = !Subobjects.IsVirtBase;
189
48.8k
      Subobjects.IsVirtBase = true;
190
48.8k
      if (isDetectingVirtual() && 
DetectedVirtual == nullptr7.29k
) {
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.97k
        DetectedVirtual = BaseType->getAs<RecordType>();
194
5.97k
        SetVirtual = true;
195
5.97k
      }
196
4.39M
    } else {
197
4.39M
      ++Subobjects.NumberOfNonVirtBases;
198
4.39M
    }
199
4.44M
    if (isRecordingPaths()) {
200
      // Add this base specifier to the current path.
201
1.25M
      CXXBasePathElement Element;
202
1.25M
      Element.Base = &BaseSpec;
203
1.25M
      Element.Class = Record;
204
1.25M
      if (BaseSpec.isVirtual())
205
9.20k
        Element.SubobjectNumber = 0;
206
1.25M
      else
207
1.25M
        Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases;
208
1.25M
      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.25M
      if (IsFirstStep)
226
1.01M
        ScratchPath.Access = BaseSpec.getAccessSpecifier();
227
242k
      else
228
242k
        ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere,
229
242k
                                                 BaseSpec.getAccessSpecifier());
230
1.25M
    }
231
232
    // Track whether there's a path involving this specific base.
233
4.44M
    bool FoundPathThroughBase = false;
234
235
4.44M
    if (BaseMatches(&BaseSpec, ScratchPath)) {
236
      // We've found a path that terminates at this base.
237
715k
      FoundPath = FoundPathThroughBase = true;
238
715k
      if (isRecordingPaths()) {
239
        // We have a path. Make a copy of it before moving on.
240
615k
        Paths.push_back(ScratchPath);
241
615k
      } else 
if (100k
!isFindingAmbiguities()100k
) {
242
        // We found a path and we don't care about ambiguities;
243
        // return immediately.
244
67.6k
        return FoundPath;
245
67.6k
      }
246
3.72M
    } else if (VisitBase) {
247
3.72M
      CXXRecordDecl *BaseRecord;
248
3.72M
      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.72M
      } else {
270
3.72M
        BaseRecord = cast<CXXRecordDecl>(
271
3.72M
            BaseSpec.getType()->castAs<RecordType>()->getDecl());
272
3.72M
      }
273
3.72M
      if (BaseRecord &&
274
3.72M
          
lookupInBases(Context, BaseRecord, BaseMatches, LookupInDependent)3.72M
) {
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
127k
        FoundPath = FoundPathThroughBase = true;
284
127k
        if (!isFindingAmbiguities())
285
19.2k
          return FoundPath;
286
127k
      }
287
3.72M
    }
288
289
    // Pop this base specifier off the current path (if we're
290
    // collecting paths).
291
4.35M
    if (isRecordingPaths()) {
292
1.25M
      ScratchPath.pop_back();
293
1.25M
    }
294
295
    // If we set a virtual earlier, and this isn't a path, forget it again.
296
4.35M
    if (SetVirtual && 
!FoundPathThroughBase5.97k
) {
297
3.63k
      DetectedVirtual = nullptr;
298
3.63k
    }
299
4.35M
  }
300
301
  // Reset the scratch path access.
302
10.9M
  ScratchPath.Access = AccessToHere;
303
304
10.9M
  return FoundPath;
305
11.0M
}
306
307
bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches,
308
                                  CXXBasePaths &Paths,
309
7.30M
                                  bool LookupInDependent) const {
310
  // If we didn't find anything, report that.
311
7.30M
  if (!Paths.lookupInBases(getASTContext(), this, BaseMatches,
312
7.30M
                           LookupInDependent))
313
6.58M
    return false;
314
315
  // If we're not recording paths or we won't ever find ambiguities,
316
  // we're done.
317
713k
  if (!Paths.isRecordingPaths() || 
!Paths.isFindingAmbiguities()613k
)
318
100k
    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
615k
  
Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) 613k
{
331
722k
    for (const CXXBasePathElement &PE : Path) {
332
722k
      if (!PE.Base->isVirtual())
333
717k
        continue;
334
335
4.70k
      CXXRecordDecl *VBase = nullptr;
336
4.70k
      if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>())
337
4.70k
        VBase = cast<CXXRecordDecl>(Record->getDecl());
338
4.70k
      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.34k
      
for (const CXXBasePath &HidingP : Paths)4.70k
{
346
8.34k
        CXXRecordDecl *HidingClass = nullptr;
347
8.34k
        if (const RecordType *Record =
348
8.34k
                HidingP.back().Base->getType()->getAs<RecordType>())
349
8.34k
          HidingClass = cast<CXXRecordDecl>(Record->getDecl());
350
8.34k
        if (!HidingClass)
351
0
          break;
352
353
8.34k
        if (HidingClass->isVirtuallyDerivedFrom(VBase))
354
21
          return true;
355
8.34k
      }
356
4.70k
    }
357
615k
    return false;
358
615k
  });
359
360
613k
  return true;
361
713k
}
362
363
bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
364
                                  CXXBasePath &Path,
365
304k
                                  const CXXRecordDecl *BaseRecord) {
366
304k
  assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
367
304k
         "User data for FindBaseClass is not canonical!");
368
0
  return Specifier->getType()->castAs<RecordType>()->getDecl()
369
304k
            ->getCanonicalDecl() == BaseRecord;
370
304k
}
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
272
static bool isOrdinaryMember(const NamedDecl *ND) {
383
272
  return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag |
384
272
                                     Decl::IDNS_Member);
385
272
}
386
387
static bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path,
388
570
                               DeclarationName Name) {
389
570
  Path.Decls = RD->lookup(Name).begin();
390
570
  for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; 
++I0
)
391
236
    if (isOrdinaryMember(*I))
392
236
      return true;
393
394
334
  return false;
395
570
}
396
397
504
bool CXXRecordDecl::hasMemberName(DeclarationName Name) const {
398
504
  CXXBasePath P;
399
504
  if (findOrdinaryMember(this, P, Name))
400
224
    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
504
}
410
411
static bool
412
findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier,
413
21
                                     CXXBasePath &Path, DeclarationName Name) {
414
21
  const TemplateSpecializationType *TST =
415
21
      Specifier->getType()->getAs<TemplateSpecializationType>();
416
21
  if (!TST) {
417
8
    auto *RT = Specifier->getType()->getAs<RecordType>();
418
8
    if (!RT)
419
0
      return false;
420
8
    return findOrdinaryMember(cast<CXXRecordDecl>(RT->getDecl()), Path, Name);
421
8
  }
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
39
    llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
435
39
  std::vector<const NamedDecl *> Results;
436
  // Lookup in the class.
437
39
  bool AnyOrdinaryMembers = false;
438
39
  for (const NamedDecl *ND : lookup(Name)) {
439
30
    if (isOrdinaryMember(ND))
440
30
      AnyOrdinaryMembers = true;
441
30
    if (Filter(ND))
442
22
      Results.push_back(ND);
443
30
  }
444
39
  if (AnyOrdinaryMembers)
445
27
    return Results;
446
447
  // Perform lookup into our base classes.
448
12
  CXXBasePaths Paths;
449
12
  Paths.setOrigin(this);
450
12
  if (!lookupInBases(
451
21
          [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
452
21
            return findOrdinaryMemberInDependentClasses(Specifier, Path, Name);
453
21
          },
454
12
          Paths, /*LookupInDependent=*/true))
455
6
    return Results;
456
6
  for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
457
12
       I != E; 
++I6
) {
458
6
    if (isOrdinaryMember(*I) && Filter(*I))
459
6
      Results.push_back(*I);
460
6
  }
461
6
  return Results;
462
12
}
463
464
void OverridingMethods::add(unsigned OverriddenSubobject,
465
77.3k
                            UniqueVirtualMethod Overriding) {
466
77.3k
  SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides
467
77.3k
    = Overrides[OverriddenSubobject];
468
77.3k
  if (llvm::find(SubobjectOverrides, Overriding) == SubobjectOverrides.end())
469
77.1k
    SubobjectOverrides.push_back(Overriding);
470
77.3k
}
471
472
31.3k
void OverridingMethods::add(const OverridingMethods &Other) {
473
62.7k
  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.7k
         M != MEnd;
477
31.3k
         ++M)
478
31.3k
      add(I->first, *M);
479
31.3k
  }
480
31.3k
}
481
482
42.4k
void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
483
85.1k
  for (iterator I = begin(), IEnd = end(); I != IEnd; 
++I42.7k
) {
484
42.7k
    I->second.clear();
485
42.7k
    I->second.push_back(Overriding);
486
42.7k
  }
487
42.4k
}
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.4k
                                      CXXFinalOverriderMap &Overriders) {
515
40.4k
  unsigned SubobjectNumber = 0;
516
40.4k
  if (!VirtualBase)
517
35.5k
    SubobjectNumber
518
35.5k
      = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())];
519
520
40.4k
  for (const auto &Base : RD->bases()) {
521
36.2k
    if (const RecordType *RT = Base.getType()->getAs<RecordType>()) {
522
36.2k
      const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl());
523
36.2k
      if (!BaseDecl->isPolymorphic())
524
20.7k
        continue;
525
526
15.4k
      if (Overriders.empty() && 
!Base.isVirtual()13.6k
) {
527
        // There are no other overriders of virtual member functions,
528
        // so let the base class fill in our overriders for us.
529
8.68k
        Collect(BaseDecl, false, InVirtualSubobject, Overriders);
530
8.68k
        continue;
531
8.68k
      }
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.74k
      CXXFinalOverriderMap ComputedBaseOverriders;
539
6.74k
      CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
540
6.74k
      if (Base.isVirtual()) {
541
5.34k
        CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
542
5.34k
        BaseOverriders = MyVirtualOverriders;
543
5.34k
        if (!MyVirtualOverriders) {
544
4.93k
          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.93k
          BaseOverriders = MyVirtualOverriders;
550
551
4.93k
          Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
552
4.93k
        }
553
5.34k
      } else
554
1.40k
        Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
555
556
      // Merge the overriders from this base class into our own set of
557
      // overriders.
558
6.74k
      for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(),
559
6.74k
                               OMEnd = BaseOverriders->end();
560
38.0k
           OM != OMEnd;
561
31.3k
           ++OM) {
562
31.3k
        const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl();
563
31.3k
        Overriders[CanonOM].add(OM->second);
564
31.3k
      }
565
6.74k
    }
566
36.2k
  }
567
568
303k
  for (auto *M : RD->methods()) {
569
    // We only care about virtual methods.
570
303k
    if (!M->isVirtual())
571
257k
      continue;
572
573
45.9k
    CXXMethodDecl *CanonM = M->getCanonicalDecl();
574
45.9k
    using OverriddenMethodsRange =
575
45.9k
        llvm::iterator_range<CXXMethodDecl::method_iterator>;
576
45.9k
    OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods();
577
578
45.9k
    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
29.1k
      Overriders[CanonM].add(SubobjectNumber,
586
29.1k
                             UniqueVirtualMethod(CanonM, SubobjectNumber,
587
29.1k
                                                 InVirtualSubobject));
588
29.1k
      continue;
589
29.1k
    }
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
16.7k
    SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods);
598
58.3k
    while (!Stack.empty()) {
599
42.4k
      for (const CXXMethodDecl *OM : Stack.pop_back_val()) {
600
42.4k
        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
42.4k
        Overriders[CanonOM].replaceAll(
612
42.4k
                               UniqueVirtualMethod(CanonM, SubobjectNumber,
613
42.4k
                                                   InVirtualSubobject));
614
615
42.4k
        auto OverriddenMethods = CanonOM->overridden_methods();
616
42.4k
        if (OverriddenMethods.begin() == OverriddenMethods.end())
617
17.7k
          continue;
618
619
        // Continue recursion to the methods that this virtual method
620
        // overrides.
621
24.7k
        Stack.push_back(OverriddenMethods);
622
24.7k
      }
623
41.5k
    }
624
625
    // C++ [class.virtual]p2:
626
    //   For convenience we say that any virtual function overrides itself.
627
16.7k
    Overriders[CanonM].add(SubobjectNumber,
628
16.7k
                           UniqueVirtualMethod(CanonM, SubobjectNumber,
629
16.7k
                                               InVirtualSubobject));
630
16.7k
  }
631
40.4k
}
632
633
25.4k
FinalOverriderCollector::~FinalOverriderCollector() {
634
25.4k
  for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
635
25.4k
         VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
636
30.3k
       VO != VOEnd;
637
25.4k
       
++VO4.93k
)
638
4.93k
    delete VO->second;
639
25.4k
}
640
641
void
642
25.4k
CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
643
25.4k
  FinalOverriderCollector Collector;
644
25.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
45.5k
  for (auto &OM : FinalOverriders) {
650
45.9k
    for (auto &SO : OM.second) {
651
45.9k
      SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second;
652
45.9k
      if (Overriding.size() < 2)
653
45.8k
        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
      Overriding.erase(
675
98
          std::remove_if(Overriding.begin(), Overriding.end(), IsHidden),
676
98
          Overriding.end());
677
98
    }
678
45.5k
  }
679
25.4k
}
680
681
static void
682
AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
683
1.05k
                        CXXIndirectPrimaryBaseSet& Bases) {
684
  // If the record has a virtual primary base class, add it to our set.
685
1.05k
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
686
1.05k
  if (Layout.isPrimaryBaseVirtual())
687
187
    Bases.insert(Layout.getPrimaryBase());
688
689
1.46k
  for (const auto &I : RD->bases()) {
690
1.46k
    assert(!I.getType()->isDependentType() &&
691
1.46k
           "Cannot get indirect primary bases for class with dependent bases.");
692
693
0
    const CXXRecordDecl *BaseDecl =
694
1.46k
      cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
695
696
    // Only bases with virtual bases participate in computing the
697
    // indirect primary virtual base classes.
698
1.46k
    if (BaseDecl->getNumVBases())
699
442
      AddIndirectPrimaryBases(BaseDecl, Context, Bases);
700
1.46k
  }
701
702
1.05k
}
703
704
void
705
15.5k
CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
706
15.5k
  ASTContext &Context = getASTContext();
707
708
15.5k
  if (!getNumVBases())
709
14.3k
    return;
710
711
1.64k
  
for (const auto &I : bases())1.23k
{
712
1.64k
    assert(!I.getType()->isDependentType() &&
713
1.64k
           "Cannot get indirect primary bases for class with dependent bases.");
714
715
0
    const CXXRecordDecl *BaseDecl =
716
1.64k
      cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
717
718
    // Only bases with virtual bases participate in computing the
719
    // indirect primary virtual base classes.
720
1.64k
    if (BaseDecl->getNumVBases())
721
614
      AddIndirectPrimaryBases(BaseDecl, Context, Bases);
722
1.64k
  }
723
1.23k
}