Coverage Report

Created: 2020-11-24 06:42

/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
/// Computes the set of declarations referenced by these base
37
/// paths.
38
30.3k
void CXXBasePaths::ComputeDeclsFound() {
39
30.3k
  assert(NumDeclsFound == 0 && !DeclsFound &&
40
30.3k
         "Already computed the set of declarations");
41
42
30.3k
  llvm::SmallSetVector<NamedDecl *, 8> Decls;
43
60.9k
  for (paths_iterator Path = begin(), PathEnd = end(); Path != PathEnd; 
++Path30.6k
)
44
30.6k
    Decls.insert(Path->Decls.front());
45
46
30.3k
  NumDeclsFound = Decls.size();
47
30.3k
  DeclsFound = std::make_unique<NamedDecl *[]>(NumDeclsFound);
48
30.3k
  std::copy(Decls.begin(), Decls.end(), DeclsFound.get());
49
30.3k
}
50
51
30.3k
CXXBasePaths::decl_range CXXBasePaths::found_decls() {
52
30.3k
  if (NumDeclsFound == 0)
53
30.3k
    ComputeDeclsFound();
54
55
30.3k
  return decl_range(decl_iterator(DeclsFound.get()),
56
30.3k
                    decl_iterator(DeclsFound.get() + NumDeclsFound));
57
30.3k
}
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.
63
39.1k
bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
64
39.1k
  BaseType = BaseType.getUnqualifiedType();
65
39.1k
  IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType];
66
37.9k
  return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 
11.15k
: 0) > 1;
67
39.1k
}
68
69
/// clear - Clear out all prior path information.
70
53
void CXXBasePaths::clear() {
71
53
  Paths.clear();
72
53
  ClassSubobjects.clear();
73
53
  VisitedDependentRecords.clear();
74
53
  ScratchPath.clear();
75
53
  DetectedVirtual = nullptr;
76
53
}
77
78
/// Swaps the contents of this CXXBasePaths structure with the
79
/// contents of Other.
80
118
void CXXBasePaths::swap(CXXBasePaths &Other) {
81
118
  std::swap(Origin, Other.Origin);
82
118
  Paths.swap(Other.Paths);
83
118
  ClassSubobjects.swap(Other.ClassSubobjects);
84
118
  VisitedDependentRecords.swap(Other.VisitedDependentRecords);
85
118
  std::swap(FindAmbiguities, Other.FindAmbiguities);
86
118
  std::swap(RecordPaths, Other.RecordPaths);
87
118
  std::swap(DetectVirtual, Other.DetectVirtual);
88
118
  std::swap(DetectedVirtual, Other.DetectedVirtual);
89
118
}
90
91
456k
bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
92
456k
  CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
93
456k
                     /*DetectVirtual=*/false);
94
456k
  return isDerivedFrom(Base, Paths);
95
456k
}
96
97
bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
98
557k
                                  CXXBasePaths &Paths) const {
99
557k
  if (getCanonicalDecl() == Base->getCanonicalDecl())
100
27.6k
    return false;
101
102
530k
  Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
103
104
530k
  const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
105
530k
  return lookupInBases(
106
272k
      [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
107
272k
        return FindBaseClass(Specifier, Path, BaseDecl);
108
272k
      },
109
530k
      Paths);
110
530k
}
111
112
9.60k
bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const {
113
9.60k
  if (!getNumVBases())
114
7.58k
    return false;
115
116
2.02k
  CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
117
2.02k
                     /*DetectVirtual=*/false);
118
119
2.02k
  if (getCanonicalDecl() == Base->getCanonicalDecl())
120
830
    return false;
121
122
1.19k
  Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
123
124
1.19k
  const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
125
1.19k
  return lookupInBases(
126
3.43k
      [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
127
3.43k
        return FindVirtualBaseClass(Specifier, Path, BaseDecl);
128
3.43k
      },
129
1.19k
      Paths);
130
1.19k
}
131
132
11.8k
bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
133
11.8k
  const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl();
134
12.4k
  return forallBases([TargetDecl](const CXXRecordDecl *Base) {
135
12.4k
    return Base->getCanonicalDecl() != TargetDecl;
136
12.4k
  });
137
11.8k
}
138
139
bool
140
436k
CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const {
141
436k
  assert(isDependentContext());
142
143
456k
  for (; !CurContext->isFileContext(); 
CurContext = CurContext->getParent()19.7k
)
144
443k
    if (CurContext->Equals(this))
145
423k
      return true;
146
147
13.6k
  return false;
148
436k
}
149
150
21.2k
bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches) const {
151
21.2k
  SmallVector<const CXXRecordDecl*, 8> Queue;
152
153
21.2k
  const CXXRecordDecl *Record = this;
154
22.7k
  while (true) {
155
22.5k
    for (const auto &I : Record->bases()) {
156
22.5k
      const RecordType *Ty = I.getType()->getAs<RecordType>();
157
22.5k
      if (!Ty)
158
2.42k
        return false;
159
160
20.1k
      CXXRecordDecl *Base =
161
20.1k
            cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
162
20.1k
      if (!Base ||
163
20.1k
          (Base->isDependentContext() &&
164
8
           
!Base->isCurrentInstantiation(Record)6
)) {
165
8
        return false;
166
8
      }
167
168
20.1k
      Queue.push_back(Base);
169
20.1k
      if (!BaseMatches(Base))
170
17.8k
        return false;
171
20.1k
    }
172
173
2.48k
    if (Queue.empty())
174
964
      break;
175
1.52k
    Record = Queue.pop_back_val(); // not actually a queue.
176
1.52k
  }
177
178
964
  return true;
179
21.2k
}
180
181
bool CXXBasePaths::lookupInBases(ASTContext &Context,
182
                                 const CXXRecordDecl *Record,
183
                                 CXXRecordDecl::BaseMatchesCallback BaseMatches,
184
10.4M
                                 bool LookupInDependent) {
185
10.4M
  bool FoundPath = false;
186
187
  // The access of the path down to this record.
188
10.4M
  AccessSpecifier AccessToHere = ScratchPath.Access;
189
10.4M
  bool IsFirstStep = ScratchPath.empty();
190
191
5.01M
  for (const auto &BaseSpec : Record->bases()) {
192
    // Find the record of the base class subobjects for this type.
193
5.01M
    QualType BaseType =
194
5.01M
        Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType();
195
196
    // C++ [temp.dep]p3:
197
    //   In the definition of a class template or a member of a class template,
198
    //   if a base class of the class template depends on a template-parameter,
199
    //   the base class scope is not examined during unqualified name lookup
200
    //   either at the point of definition of the class template or member or
201
    //   during an instantiation of the class tem- plate or member.
202
5.01M
    if (!LookupInDependent && 
BaseType->isDependentType()5.01M
)
203
681k
      continue;
204
205
    // Determine whether we need to visit this base class at all,
206
    // updating the count of subobjects appropriately.
207
4.33M
    IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType];
208
4.33M
    bool VisitBase = true;
209
4.33M
    bool SetVirtual = false;
210
4.33M
    if (BaseSpec.isVirtual()) {
211
48.0k
      VisitBase = !Subobjects.IsVirtBase;
212
48.0k
      Subobjects.IsVirtBase = true;
213
48.0k
      if (isDetectingVirtual() && 
DetectedVirtual == nullptr42.0k
) {
214
        // If this is the first virtual we find, remember it. If it turns out
215
        // there is no base path here, we'll reset it later.
216
35.0k
        DetectedVirtual = BaseType->getAs<RecordType>();
217
35.0k
        SetVirtual = true;
218
35.0k
      }
219
4.28M
    } else {
220
4.28M
      ++Subobjects.NumberOfNonVirtBases;
221
4.28M
    }
222
4.33M
    if (isRecordingPaths()) {
223
      // Add this base specifier to the current path.
224
4.16M
      CXXBasePathElement Element;
225
4.16M
      Element.Base = &BaseSpec;
226
4.16M
      Element.Class = Record;
227
4.16M
      if (BaseSpec.isVirtual())
228
43.8k
        Element.SubobjectNumber = 0;
229
4.12M
      else
230
4.12M
        Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases;
231
4.16M
      ScratchPath.push_back(Element);
232
233
      // Calculate the "top-down" access to this base class.
234
      // The spec actually describes this bottom-up, but top-down is
235
      // equivalent because the definition works out as follows:
236
      // 1. Write down the access along each step in the inheritance
237
      //    chain, followed by the access of the decl itself.
238
      //    For example, in
239
      //      class A { public: int foo; };
240
      //      class B : protected A {};
241
      //      class C : public B {};
242
      //      class D : private C {};
243
      //    we would write:
244
      //      private public protected public
245
      // 2. If 'private' appears anywhere except far-left, access is denied.
246
      // 3. Otherwise, overall access is determined by the most restrictive
247
      //    access in the sequence.
248
4.16M
      if (IsFirstStep)
249
1.70M
        ScratchPath.Access = BaseSpec.getAccessSpecifier();
250
2.45M
      else
251
2.45M
        ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere,
252
2.45M
                                                 BaseSpec.getAccessSpecifier());
253
4.16M
    }
254
255
    // Track whether there's a path involving this specific base.
256
4.33M
    bool FoundPathThroughBase = false;
257
258
4.33M
    if (BaseMatches(&BaseSpec, ScratchPath)) {
259
      // We've found a path that terminates at this base.
260
708k
      FoundPath = FoundPathThroughBase = true;
261
708k
      if (isRecordingPaths()) {
262
        // We have a path. Make a copy of it before moving on.
263
636k
        Paths.push_back(ScratchPath);
264
72.1k
      } else if (!isFindingAmbiguities()) {
265
        // We found a path and we don't care about ambiguities;
266
        // return immediately.
267
72.1k
        return FoundPath;
268
72.1k
      }
269
3.62M
    } else if (VisitBase) {
270
3.62M
      CXXRecordDecl *BaseRecord;
271
3.62M
      if (LookupInDependent) {
272
272
        BaseRecord = nullptr;
273
272
        const TemplateSpecializationType *TST =
274
272
            BaseSpec.getType()->getAs<TemplateSpecializationType>();
275
272
        if (!TST) {
276
253
          if (auto *RT = BaseSpec.getType()->getAs<RecordType>())
277
249
            BaseRecord = cast<CXXRecordDecl>(RT->getDecl());
278
19
        } else {
279
19
          TemplateName TN = TST->getTemplateName();
280
19
          if (auto *TD =
281
19
                  dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl()))
282
19
            BaseRecord = TD->getTemplatedDecl();
283
19
        }
284
272
        if (BaseRecord) {
285
268
          if (!BaseRecord->hasDefinition() ||
286
266
              VisitedDependentRecords.count(BaseRecord)) {
287
3
            BaseRecord = nullptr;
288
265
          } else {
289
265
            VisitedDependentRecords.insert(BaseRecord);
290
265
          }
291
268
        }
292
3.62M
      } else {
293
3.62M
        BaseRecord = cast<CXXRecordDecl>(
294
3.62M
            BaseSpec.getType()->castAs<RecordType>()->getDecl());
295
3.62M
      }
296
3.62M
      if (BaseRecord &&
297
3.62M
          lookupInBases(Context, BaseRecord, BaseMatches, LookupInDependent)) {
298
        // C++ [class.member.lookup]p2:
299
        //   A member name f in one sub-object B hides a member name f in
300
        //   a sub-object A if A is a base class sub-object of B. Any
301
        //   declarations that are so hidden are eliminated from
302
        //   consideration.
303
304
        // There is a path to a base class that meets the criteria. If we're
305
        // not collecting paths or finding ambiguities, we're done.
306
121k
        FoundPath = FoundPathThroughBase = true;
307
121k
        if (!isFindingAmbiguities())
308
18.7k
          return FoundPath;
309
4.24M
      }
310
3.62M
    }
311
312
    // Pop this base specifier off the current path (if we're
313
    // collecting paths).
314
4.24M
    if (isRecordingPaths()) {
315
4.16M
      ScratchPath.pop_back();
316
4.16M
    }
317
318
    // If we set a virtual earlier, and this isn't a path, forget it again.
319
4.24M
    if (SetVirtual && 
!FoundPathThroughBase35.0k
) {
320
31.8k
      DetectedVirtual = nullptr;
321
31.8k
    }
322
4.24M
  }
323
324
  // Reset the scratch path access.
325
10.3M
  ScratchPath.Access = AccessToHere;
326
327
10.3M
  return FoundPath;
328
10.4M
}
329
330
bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches,
331
                                  CXXBasePaths &Paths,
332
6.77M
                                  bool LookupInDependent) const {
333
  // If we didn't find anything, report that.
334
6.77M
  if (!Paths.lookupInBases(getASTContext(), this, BaseMatches,
335
6.77M
                           LookupInDependent))
336
6.07M
    return false;
337
338
  // If we're not recording paths or we won't ever find ambiguities,
339
  // we're done.
340
705k
  if (!Paths.isRecordingPaths() || 
!Paths.isFindingAmbiguities()633k
)
341
72.5k
    return true;
342
343
  // C++ [class.member.lookup]p6:
344
  //   When virtual base classes are used, a hidden declaration can be
345
  //   reached along a path through the sub-object lattice that does
346
  //   not pass through the hiding declaration. This is not an
347
  //   ambiguity. The identical use with nonvirtual base classes is an
348
  //   ambiguity; in that case there is no unique instance of the name
349
  //   that hides all the others.
350
  //
351
  // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy
352
  // way to make it any faster.
353
635k
  
Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) 633k
{
354
738k
    for (const CXXBasePathElement &PE : Path) {
355
738k
      if (!PE.Base->isVirtual())
356
733k
        continue;
357
358
5.55k
      CXXRecordDecl *VBase = nullptr;
359
5.55k
      if (const RecordType *Record = PE.Base->getType()->getAs<RecordType>())
360
5.55k
        VBase = cast<CXXRecordDecl>(Record->getDecl());
361
5.55k
      if (!VBase)
362
0
        break;
363
364
      // The declaration(s) we found along this path were found in a
365
      // subobject of a virtual base. Check whether this virtual
366
      // base is a subobject of any other path; if so, then the
367
      // declaration in this path are hidden by that patch.
368
9.30k
      
for (const CXXBasePath &HidingP : Paths)5.55k
{
369
9.30k
        CXXRecordDecl *HidingClass = nullptr;
370
9.30k
        if (const RecordType *Record =
371
9.30k
                HidingP.back().Base->getType()->getAs<RecordType>())
372
9.30k
          HidingClass = cast<CXXRecordDecl>(Record->getDecl());
373
9.30k
        if (!HidingClass)
374
0
          break;
375
376
9.30k
        if (HidingClass->isVirtuallyDerivedFrom(VBase))
377
41
          return true;
378
9.30k
      }
379
5.55k
    }
380
635k
    return false;
381
635k
  });
382
383
633k
  return true;
384
633k
}
385
386
bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
387
                                  CXXBasePath &Path,
388
272k
                                  const CXXRecordDecl *BaseRecord) {
389
272k
  assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
390
272k
         "User data for FindBaseClass is not canonical!");
391
272k
  return Specifier->getType()->castAs<RecordType>()->getDecl()
392
272k
            ->getCanonicalDecl() == BaseRecord;
393
272k
}
394
395
bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier,
396
                                         CXXBasePath &Path,
397
3.43k
                                         const CXXRecordDecl *BaseRecord) {
398
3.43k
  assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
399
3.43k
         "User data for FindBaseClass is not canonical!");
400
3.43k
  return Specifier->isVirtual() &&
401
2.33k
         Specifier->getType()->castAs<RecordType>()->getDecl()
402
2.33k
            ->getCanonicalDecl() == BaseRecord;
403
3.43k
}
404
405
bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier,
406
                                  CXXBasePath &Path,
407
50
                                  DeclarationName Name) {
408
50
  RecordDecl *BaseRecord =
409
50
    Specifier->getType()->castAs<RecordType>()->getDecl();
410
411
50
  for (Path.Decls = BaseRecord->lookup(Name);
412
60
       !Path.Decls.empty();
413
24
       
Path.Decls = Path.Decls.slice(1)10
) {
414
24
    if (Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag))
415
14
      return true;
416
24
  }
417
418
36
  return false;
419
50
}
420
421
static bool findOrdinaryMember(RecordDecl *BaseRecord, CXXBasePath &Path,
422
1.00M
                               DeclarationName Name) {
423
1.00M
  const unsigned IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag |
424
1.00M
                        Decl::IDNS_Member;
425
1.00M
  for (Path.Decls = BaseRecord->lookup(Name);
426
1.00M
       !Path.Decls.empty();
427
531k
       
Path.Decls = Path.Decls.slice(1)42
) {
428
531k
    if (Path.Decls.front()->isInIdentifierNamespace(IDNS))
429
531k
      return true;
430
531k
  }
431
432
472k
  return false;
433
1.00M
}
434
435
bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier,
436
                                       CXXBasePath &Path,
437
1.00M
                                       DeclarationName Name) {
438
1.00M
  RecordDecl *BaseRecord =
439
1.00M
      Specifier->getType()->castAs<RecordType>()->getDecl();
440
1.00M
  return findOrdinaryMember(BaseRecord, Path, Name);
441
1.00M
}
442
443
bool CXXRecordDecl::FindOrdinaryMemberInDependentClasses(
444
    const CXXBaseSpecifier *Specifier, CXXBasePath &Path,
445
21
    DeclarationName Name) {
446
21
  const TemplateSpecializationType *TST =
447
21
      Specifier->getType()->getAs<TemplateSpecializationType>();
448
21
  if (!TST) {
449
8
    auto *RT = Specifier->getType()->getAs<RecordType>();
450
8
    if (!RT)
451
0
      return false;
452
8
    return findOrdinaryMember(RT->getDecl(), Path, Name);
453
8
  }
454
13
  TemplateName TN = TST->getTemplateName();
455
13
  const auto *TD = dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl());
456
13
  if (!TD)
457
0
    return false;
458
13
  CXXRecordDecl *RD = TD->getTemplatedDecl();
459
13
  if (!RD)
460
0
    return false;
461
13
  return findOrdinaryMember(RD, Path, Name);
462
13
}
463
464
bool CXXRecordDecl::FindOMPReductionMember(const CXXBaseSpecifier *Specifier,
465
                                           CXXBasePath &Path,
466
368
                                           DeclarationName Name) {
467
368
  RecordDecl *BaseRecord =
468
368
      Specifier->getType()->castAs<RecordType>()->getDecl();
469
470
416
  for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty();
471
48
       Path.Decls = Path.Decls.slice(1)) {
472
48
    if (Path.Decls.front()->isInIdentifierNamespace(IDNS_OMPReduction))
473
0
      return true;
474
48
  }
475
476
368
  return false;
477
368
}
478
479
bool CXXRecordDecl::FindOMPMapperMember(const CXXBaseSpecifier *Specifier,
480
                                        CXXBasePath &Path,
481
362
                                        DeclarationName Name) {
482
362
  RecordDecl *BaseRecord =
483
362
      Specifier->getType()->castAs<RecordType>()->getDecl();
484
485
362
  for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty();
486
0
       Path.Decls = Path.Decls.slice(1)) {
487
0
    if (Path.Decls.front()->isInIdentifierNamespace(IDNS_OMPMapper))
488
0
      return true;
489
0
  }
490
491
362
  return false;
492
362
}
493
494
bool CXXRecordDecl::
495
FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier,
496
                              CXXBasePath &Path,
497
112k
                              DeclarationName Name) {
498
112k
  RecordDecl *BaseRecord =
499
112k
    Specifier->getType()->castAs<RecordType>()->getDecl();
500
501
112k
  for (Path.Decls = BaseRecord->lookup(Name);
502
112k
       !Path.Decls.empty();
503
4.59k
       
Path.Decls = Path.Decls.slice(1)0
) {
504
    // FIXME: Refactor the "is it a nested-name-specifier?" check
505
4.59k
    if (isa<TypedefNameDecl>(Path.Decls.front()) ||
506
4.58k
        Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag))
507
4.59k
      return true;
508
4.59k
  }
509
510
108k
  return false;
511
112k
}
512
513
std::vector<const NamedDecl *> CXXRecordDecl::lookupDependentName(
514
    const DeclarationName &Name,
515
39
    llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
516
39
  std::vector<const NamedDecl *> Results;
517
  // Lookup in the class.
518
39
  DeclContext::lookup_result DirectResult = lookup(Name);
519
39
  if (!DirectResult.empty()) {
520
30
    for (const NamedDecl *ND : DirectResult) {
521
30
      if (Filter(ND))
522
22
        Results.push_back(ND);
523
30
    }
524
27
    return Results;
525
27
  }
526
  // Perform lookup into our base classes.
527
12
  CXXBasePaths Paths;
528
12
  Paths.setOrigin(this);
529
12
  if (!lookupInBases(
530
21
          [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
531
21
            return CXXRecordDecl::FindOrdinaryMemberInDependentClasses(
532
21
                Specifier, Path, Name);
533
21
          },
534
12
          Paths, /*LookupInDependent=*/true))
535
6
    return Results;
536
6
  for (const NamedDecl *ND : Paths.front().Decls) {
537
6
    if (Filter(ND))
538
6
      Results.push_back(ND);
539
6
  }
540
6
  return Results;
541
6
}
542
543
void OverridingMethods::add(unsigned OverriddenSubobject,
544
76.8k
                            UniqueVirtualMethod Overriding) {
545
76.8k
  SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides
546
76.8k
    = Overrides[OverriddenSubobject];
547
76.8k
  if (llvm::find(SubobjectOverrides, Overriding) == SubobjectOverrides.end())
548
76.6k
    SubobjectOverrides.push_back(Overriding);
549
76.8k
}
550
551
31.2k
void OverridingMethods::add(const OverridingMethods &Other) {
552
62.5k
  for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; 
++I31.3k
) {
553
31.3k
    for (overriding_const_iterator M = I->second.begin(),
554
31.3k
                                MEnd = I->second.end();
555
62.6k
         M != MEnd;
556
31.3k
         ++M)
557
31.3k
      add(I->first, *M);
558
31.3k
  }
559
31.2k
}
560
561
42.2k
void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
562
84.6k
  for (iterator I = begin(), IEnd = end(); I != IEnd; 
++I42.4k
) {
563
42.4k
    I->second.clear();
564
42.4k
    I->second.push_back(Overriding);
565
42.4k
  }
566
42.2k
}
567
568
namespace {
569
570
class FinalOverriderCollector {
571
  /// The number of subobjects of a given class type that
572
  /// occur within the class hierarchy.
573
  llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCount;
574
575
  /// Overriders for each virtual base subobject.
576
  llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *> VirtualOverriders;
577
578
  CXXFinalOverriderMap FinalOverriders;
579
580
public:
581
  ~FinalOverriderCollector();
582
583
  void Collect(const CXXRecordDecl *RD, bool VirtualBase,
584
               const CXXRecordDecl *InVirtualSubobject,
585
               CXXFinalOverriderMap &Overriders);
586
};
587
588
} // namespace
589
590
void FinalOverriderCollector::Collect(const CXXRecordDecl *RD,
591
                                      bool VirtualBase,
592
                                      const CXXRecordDecl *InVirtualSubobject,
593
36.6k
                                      CXXFinalOverriderMap &Overriders) {
594
36.6k
  unsigned SubobjectNumber = 0;
595
36.6k
  if (!VirtualBase)
596
31.7k
    SubobjectNumber
597
31.7k
      = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())];
598
599
28.6k
  for (const auto &Base : RD->bases()) {
600
28.6k
    if (const RecordType *RT = Base.getType()->getAs<RecordType>()) {
601
28.6k
      const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl());
602
28.6k
      if (!BaseDecl->isPolymorphic())
603
13.1k
        continue;
604
605
15.4k
      if (Overriders.empty() && 
!Base.isVirtual()13.6k
) {
606
        // There are no other overriders of virtual member functions,
607
        // so let the base class fill in our overriders for us.
608
8.75k
        Collect(BaseDecl, false, InVirtualSubobject, Overriders);
609
8.75k
        continue;
610
8.75k
      }
611
612
      // Collect all of the overridders from the base class subobject
613
      // and merge them into the set of overridders for this class.
614
      // For virtual base classes, populate or use the cached virtual
615
      // overrides so that we do not walk the virtual base class (and
616
      // its base classes) more than once.
617
6.69k
      CXXFinalOverriderMap ComputedBaseOverriders;
618
6.69k
      CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
619
6.69k
      if (Base.isVirtual()) {
620
5.29k
        CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
621
5.29k
        BaseOverriders = MyVirtualOverriders;
622
5.29k
        if (!MyVirtualOverriders) {
623
4.89k
          MyVirtualOverriders = new CXXFinalOverriderMap;
624
625
          // Collect may cause VirtualOverriders to reallocate, invalidating the
626
          // MyVirtualOverriders reference. Set BaseOverriders to the right
627
          // value now.
628
4.89k
          BaseOverriders = MyVirtualOverriders;
629
630
4.89k
          Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
631
4.89k
        }
632
5.29k
      } else
633
1.39k
        Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
634
635
      // Merge the overriders from this base class into our own set of
636
      // overriders.
637
6.69k
      for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(),
638
6.69k
                               OMEnd = BaseOverriders->end();
639
37.9k
           OM != OMEnd;
640
31.2k
           ++OM) {
641
31.2k
        const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl();
642
31.2k
        Overriders[CanonOM].add(OM->second);
643
31.2k
      }
644
6.69k
    }
645
28.6k
  }
646
647
275k
  for (auto *M : RD->methods()) {
648
    // We only care about virtual methods.
649
275k
    if (!M->isVirtual())
650
230k
      continue;
651
652
45.5k
    CXXMethodDecl *CanonM = M->getCanonicalDecl();
653
45.5k
    using OverriddenMethodsRange =
654
45.5k
        llvm::iterator_range<CXXMethodDecl::method_iterator>;
655
45.5k
    OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods();
656
657
45.5k
    if (OverriddenMethods.begin() == OverriddenMethods.end()) {
658
      // This is a new virtual function that does not override any
659
      // other virtual function. Add it to the map of virtual
660
      // functions for which we are tracking overridders.
661
662
      // C++ [class.virtual]p2:
663
      //   For convenience we say that any virtual function overrides itself.
664
28.8k
      Overriders[CanonM].add(SubobjectNumber,
665
28.8k
                             UniqueVirtualMethod(CanonM, SubobjectNumber,
666
28.8k
                                                 InVirtualSubobject));
667
28.8k
      continue;
668
28.8k
    }
669
670
    // This virtual method overrides other virtual methods, so it does
671
    // not add any new slots into the set of overriders. Instead, we
672
    // replace entries in the set of overriders with the new
673
    // overrider. To do so, we dig down to the original virtual
674
    // functions using data recursion and update all of the methods it
675
    // overrides.
676
16.6k
    SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods);
677
58.0k
    while (!Stack.empty()) {
678
42.2k
      for (const CXXMethodDecl *OM : Stack.pop_back_val()) {
679
42.2k
        const CXXMethodDecl *CanonOM = OM->getCanonicalDecl();
680
681
        // C++ [class.virtual]p2:
682
        //   A virtual member function C::vf of a class object S is
683
        //   a final overrider unless the most derived class (1.8)
684
        //   of which S is a base class subobject (if any) declares
685
        //   or inherits another member function that overrides vf.
686
        //
687
        // Treating this object like the most derived class, we
688
        // replace any overrides from base classes with this
689
        // overriding virtual function.
690
42.2k
        Overriders[CanonOM].replaceAll(
691
42.2k
                               UniqueVirtualMethod(CanonM, SubobjectNumber,
692
42.2k
                                                   InVirtualSubobject));
693
694
42.2k
        auto OverriddenMethods = CanonOM->overridden_methods();
695
42.2k
        if (OverriddenMethods.begin() == OverriddenMethods.end())
696
17.5k
          continue;
697
698
        // Continue recursion to the methods that this virtual method
699
        // overrides.
700
24.6k
        Stack.push_back(OverriddenMethods);
701
24.6k
      }
702
41.3k
    }
703
704
    // C++ [class.virtual]p2:
705
    //   For convenience we say that any virtual function overrides itself.
706
16.6k
    Overriders[CanonM].add(SubobjectNumber,
707
16.6k
                           UniqueVirtualMethod(CanonM, SubobjectNumber,
708
16.6k
                                               InVirtualSubobject));
709
16.6k
  }
710
36.6k
}
711
712
21.6k
FinalOverriderCollector::~FinalOverriderCollector() {
713
21.6k
  for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
714
21.6k
         VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
715
26.5k
       VO != VOEnd;
716
4.89k
       ++VO)
717
4.89k
    delete VO->second;
718
21.6k
}
719
720
void
721
21.6k
CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
722
21.6k
  FinalOverriderCollector Collector;
723
21.6k
  Collector.Collect(this, false, nullptr, FinalOverriders);
724
725
  // Weed out any final overriders that come from virtual base class
726
  // subobjects that were hidden by other subobjects along any path.
727
  // This is the final-overrider variant of C++ [class.member.lookup]p10.
728
45.1k
  for (auto &OM : FinalOverriders) {
729
45.5k
    for (auto &SO : OM.second) {
730
45.5k
      SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second;
731
45.5k
      if (Overriding.size() < 2)
732
45.4k
        continue;
733
734
196
      
auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) 98
{
735
196
        if (!M.InVirtualSubobject)
736
94
          return false;
737
738
        // We have an overriding method in a virtual base class
739
        // subobject (or non-virtual base class subobject thereof);
740
        // determine whether there exists an other overriding method
741
        // in a base class subobject that hides the virtual base class
742
        // subobject.
743
102
        for (const UniqueVirtualMethod &OP : Overriding)
744
158
          if (&M != &OP &&
745
102
              OP.Method->getParent()->isVirtuallyDerivedFrom(
746
102
                  M.InVirtualSubobject))
747
96
            return true;
748
6
        return false;
749
102
      };
750
751
      // FIXME: IsHidden reads from Overriding from the middle of a remove_if
752
      // over the same sequence! Is this guaranteed to work?
753
98
      Overriding.erase(
754
98
          std::remove_if(Overriding.begin(), Overriding.end(), IsHidden),
755
98
          Overriding.end());
756
98
    }
757
45.1k
  }
758
21.6k
}
759
760
static void
761
AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
762
875
                        CXXIndirectPrimaryBaseSet& Bases) {
763
  // If the record has a virtual primary base class, add it to our set.
764
875
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
765
875
  if (Layout.isPrimaryBaseVirtual())
766
181
    Bases.insert(Layout.getPrimaryBase());
767
768
1.27k
  for (const auto &I : RD->bases()) {
769
1.27k
    assert(!I.getType()->isDependentType() &&
770
1.27k
           "Cannot get indirect primary bases for class with dependent bases.");
771
772
1.27k
    const CXXRecordDecl *BaseDecl =
773
1.27k
      cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
774
775
    // Only bases with virtual bases participate in computing the
776
    // indirect primary virtual base classes.
777
1.27k
    if (BaseDecl->getNumVBases())
778
418
      AddIndirectPrimaryBases(BaseDecl, Context, Bases);
779
1.27k
  }
780
781
875
}
782
783
void
784
11.8k
CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
785
11.8k
  ASTContext &Context = getASTContext();
786
787
11.8k
  if (!getNumVBases())
788
10.9k
    return;
789
790
1.24k
  
for (const auto &I : bases())930
{
791
1.24k
    assert(!I.getType()->isDependentType() &&
792
1.24k
           "Cannot get indirect primary bases for class with dependent bases.");
793
794
1.24k
    const CXXRecordDecl *BaseDecl =
795
1.24k
      cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
796
797
    // Only bases with virtual bases participate in computing the
798
    // indirect primary virtual base classes.
799
1.24k
    if (BaseDecl->getNumVBases())
800
457
      AddIndirectPrimaryBases(BaseDecl, Context, Bases);
801
1.24k
  }
802
930
}