Coverage Report

Created: 2020-09-15 12:33

/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
31.1k
void CXXBasePaths::ComputeDeclsFound() {
39
31.1k
  assert(NumDeclsFound == 0 && !DeclsFound &&
40
31.1k
         "Already computed the set of declarations");
41
31.1k
42
31.1k
  llvm::SmallSetVector<NamedDecl *, 8> Decls;
43
62.7k
  for (paths_iterator Path = begin(), PathEnd = end(); Path != PathEnd; 
++Path31.5k
)
44
31.5k
    Decls.insert(Path->Decls.front());
45
31.1k
46
31.1k
  NumDeclsFound = Decls.size();
47
31.1k
  DeclsFound = std::make_unique<NamedDecl *[]>(NumDeclsFound);
48
31.1k
  std::copy(Decls.begin(), Decls.end(), DeclsFound.get());
49
31.1k
}
50
51
31.1k
CXXBasePaths::decl_range CXXBasePaths::found_decls() {
52
31.1k
  if (NumDeclsFound == 0)
53
31.1k
    ComputeDeclsFound();
54
31.1k
55
31.1k
  return decl_range(decl_iterator(DeclsFound.get()),
56
31.1k
                    decl_iterator(DeclsFound.get() + NumDeclsFound));
57
31.1k
}
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
38.2k
bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
64
38.2k
  BaseType = BaseType.getUnqualifiedType();
65
38.2k
  IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType];
66
37.0k
  return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 
11.14k
: 0) > 1;
67
38.2k
}
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
117
void CXXBasePaths::swap(CXXBasePaths &Other) {
81
117
  std::swap(Origin, Other.Origin);
82
117
  Paths.swap(Other.Paths);
83
117
  ClassSubobjects.swap(Other.ClassSubobjects);
84
117
  VisitedDependentRecords.swap(Other.VisitedDependentRecords);
85
117
  std::swap(FindAmbiguities, Other.FindAmbiguities);
86
117
  std::swap(RecordPaths, Other.RecordPaths);
87
117
  std::swap(DetectVirtual, Other.DetectVirtual);
88
117
  std::swap(DetectedVirtual, Other.DetectedVirtual);
89
117
}
90
91
438k
bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base) const {
92
438k
  CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
93
438k
                     /*DetectVirtual=*/false);
94
438k
  return isDerivedFrom(Base, Paths);
95
438k
}
96
97
bool CXXRecordDecl::isDerivedFrom(const CXXRecordDecl *Base,
98
539k
                                  CXXBasePaths &Paths) const {
99
539k
  if (getCanonicalDecl() == Base->getCanonicalDecl())
100
27.2k
    return false;
101
511k
102
511k
  Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
103
511k
104
511k
  const CXXRecordDecl *BaseDecl = Base->getCanonicalDecl();
105
511k
  return lookupInBases(
106
264k
      [BaseDecl](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
107
264k
        return FindBaseClass(Specifier, Path, BaseDecl);
108
264k
      },
109
511k
      Paths);
110
511k
}
111
112
9.59k
bool CXXRecordDecl::isVirtuallyDerivedFrom(const CXXRecordDecl *Base) const {
113
9.59k
  if (!getNumVBases())
114
7.57k
    return false;
115
2.02k
116
2.02k
  CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
117
2.02k
                     /*DetectVirtual=*/false);
118
2.02k
119
2.02k
  if (getCanonicalDecl() == Base->getCanonicalDecl())
120
830
    return false;
121
1.19k
122
1.19k
  Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
123
1.19k
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.6k
bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
133
11.6k
  const CXXRecordDecl *TargetDecl = Base->getCanonicalDecl();
134
12.2k
  return forallBases([TargetDecl](const CXXRecordDecl *Base) {
135
12.2k
    return Base->getCanonicalDecl() != TargetDecl;
136
12.2k
  });
137
11.6k
}
138
139
bool
140
368k
CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const {
141
368k
  assert(isDependentContext());
142
368k
143
387k
  for (; !CurContext->isFileContext(); 
CurContext = CurContext->getParent()19.5k
)
144
374k
    if (CurContext->Equals(this))
145
354k
      return true;
146
368k
147
13.5k
  return false;
148
368k
}
149
150
21.0k
bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches) const {
151
21.0k
  SmallVector<const CXXRecordDecl*, 8> Queue;
152
21.0k
153
21.0k
  const CXXRecordDecl *Record = this;
154
22.5k
  while (true) {
155
22.4k
    for (const auto &I : Record->bases()) {
156
22.4k
      const RecordType *Ty = I.getType()->getAs<RecordType>();
157
22.4k
      if (!Ty)
158
2.43k
        return false;
159
20.0k
160
20.0k
      CXXRecordDecl *Base =
161
20.0k
            cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
162
20.0k
      if (!Base ||
163
20.0k
          (Base->isDependentContext() &&
164
8
           
!Base->isCurrentInstantiation(Record)6
)) {
165
8
        return false;
166
8
      }
167
20.0k
168
20.0k
      Queue.push_back(Base);
169
20.0k
      if (!BaseMatches(Base))
170
17.7k
        return false;
171
20.0k
    }
172
22.5k
173
2.35k
    if (Queue.empty())
174
885
      break;
175
1.47k
    Record = Queue.pop_back_val(); // not actually a queue.
176
1.47k
  }
177
21.0k
178
885
  return true;
179
21.0k
}
180
181
bool CXXBasePaths::lookupInBases(ASTContext &Context,
182
                                 const CXXRecordDecl *Record,
183
                                 CXXRecordDecl::BaseMatchesCallback BaseMatches,
184
10.2M
                                 bool LookupInDependent) {
185
10.2M
  bool FoundPath = false;
186
10.2M
187
  // The access of the path down to this record.
188
10.2M
  AccessSpecifier AccessToHere = ScratchPath.Access;
189
10.2M
  bool IsFirstStep = ScratchPath.empty();
190
10.2M
191
4.99M
  for (const auto &BaseSpec : Record->bases()) {
192
    // Find the record of the base class subobjects for this type.
193
4.99M
    QualType BaseType =
194
4.99M
        Context.getCanonicalType(BaseSpec.getType()).getUnqualifiedType();
195
4.99M
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
4.99M
    if (!LookupInDependent && 
BaseType->isDependentType()4.99M
)
203
681k
      continue;
204
4.31M
205
    // Determine whether we need to visit this base class at all,
206
    // updating the count of subobjects appropriately.
207
4.31M
    IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType];
208
4.31M
    bool VisitBase = true;
209
4.31M
    bool SetVirtual = false;
210
4.31M
    if (BaseSpec.isVirtual()) {
211
49.2k
      VisitBase = !Subobjects.IsVirtBase;
212
49.2k
      Subobjects.IsVirtBase = true;
213
49.2k
      if (isDetectingVirtual() && 
DetectedVirtual == nullptr43.3k
) {
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
36.2k
        DetectedVirtual = BaseType->getAs<RecordType>();
217
36.2k
        SetVirtual = true;
218
36.2k
      }
219
4.26M
    } else {
220
4.26M
      ++Subobjects.NumberOfNonVirtBases;
221
4.26M
    }
222
4.31M
    if (isRecordingPaths()) {
223
      // Add this base specifier to the current path.
224
4.15M
      CXXBasePathElement Element;
225
4.15M
      Element.Base = &BaseSpec;
226
4.15M
      Element.Class = Record;
227
4.15M
      if (BaseSpec.isVirtual())
228
45.0k
        Element.SubobjectNumber = 0;
229
4.10M
      else
230
4.10M
        Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases;
231
4.15M
      ScratchPath.push_back(Element);
232
4.15M
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.15M
      if (IsFirstStep)
249
1.69M
        ScratchPath.Access = BaseSpec.getAccessSpecifier();
250
2.46M
      else
251
2.46M
        ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere,
252
2.46M
                                                 BaseSpec.getAccessSpecifier());
253
4.15M
    }
254
4.31M
255
    // Track whether there's a path involving this specific base.
256
4.31M
    bool FoundPathThroughBase = false;
257
4.31M
258
4.31M
    if (BaseMatches(&BaseSpec, ScratchPath)) {
259
      // We've found a path that terminates at this base.
260
698k
      FoundPath = FoundPathThroughBase = true;
261
698k
      if (isRecordingPaths()) {
262
        // We have a path. Make a copy of it before moving on.
263
629k
        Paths.push_back(ScratchPath);
264
69.3k
      } else if (!isFindingAmbiguities()) {
265
        // We found a path and we don't care about ambiguities;
266
        // return immediately.
267
69.3k
        return FoundPath;
268
69.3k
      }
269
3.61M
    } else if (VisitBase) {
270
3.61M
      CXXRecordDecl *BaseRecord;
271
3.61M
      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.61M
      } else {
293
3.61M
        BaseRecord = cast<CXXRecordDecl>(
294
3.61M
            BaseSpec.getType()->castAs<RecordType>()->getDecl());
295
3.61M
      }
296
3.61M
      if (BaseRecord &&
297
3.61M
          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
119k
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
119k
        FoundPath = FoundPathThroughBase = true;
307
119k
        if (!isFindingAmbiguities())
308
18.6k
          return FoundPath;
309
4.23M
      }
310
3.61M
    }
311
4.23M
312
    // Pop this base specifier off the current path (if we're
313
    // collecting paths).
314
4.23M
    if (isRecordingPaths()) {
315
4.15M
      ScratchPath.pop_back();
316
4.15M
    }
317
4.23M
318
    // If we set a virtual earlier, and this isn't a path, forget it again.
319
4.23M
    if (SetVirtual && 
!FoundPathThroughBase36.2k
) {
320
33.0k
      DetectedVirtual = nullptr;
321
33.0k
    }
322
4.23M
  }
323
10.2M
324
  // Reset the scratch path access.
325
10.1M
  ScratchPath.Access = AccessToHere;
326
10.1M
327
10.1M
  return FoundPath;
328
10.2M
}
329
330
bool CXXRecordDecl::lookupInBases(BaseMatchesCallback BaseMatches,
331
                                  CXXBasePaths &Paths,
332
6.66M
                                  bool LookupInDependent) const {
333
  // If we didn't find anything, report that.
334
6.66M
  if (!Paths.lookupInBases(getASTContext(), this, BaseMatches,
335
6.66M
                           LookupInDependent))
336
5.96M
    return false;
337
696k
338
  // If we're not recording paths or we won't ever find ambiguities,
339
  // we're done.
340
696k
  if (!Paths.isRecordingPaths() || 
!Paths.isFindingAmbiguities()627k
)
341
69.7k
    return true;
342
626k
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
629k
  
Paths.Paths.remove_if([&Paths](const CXXBasePath &Path) 626k
{
354
730k
    for (const CXXBasePathElement &PE : Path) {
355
730k
      if (!PE.Base->isVirtual())
356
725k
        continue;
357
5.55k
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
5.55k
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
9.30k
376
9.30k
        if (HidingClass->isVirtuallyDerivedFrom(VBase))
377
40
          return true;
378
9.30k
      }
379
5.55k
    }
380
629k
    return false;
381
629k
  });
382
626k
383
626k
  return true;
384
626k
}
385
386
bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
387
                                  CXXBasePath &Path,
388
264k
                                  const CXXRecordDecl *BaseRecord) {
389
264k
  assert(BaseRecord->getCanonicalDecl() == BaseRecord &&
390
264k
         "User data for FindBaseClass is not canonical!");
391
264k
  return Specifier->getType()->castAs<RecordType>()->getDecl()
392
264k
            ->getCanonicalDecl() == BaseRecord;
393
264k
}
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
50
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
50
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
525k
       
Path.Decls = Path.Decls.slice(1)42
) {
428
525k
    if (Path.Decls.front()->isInIdentifierNamespace(IDNS))
429
525k
      return true;
430
525k
  }
431
1.00M
432
481k
  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
368
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
368
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
362
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
362
491
362
  return false;
492
362
}
493
494
bool CXXRecordDecl::
495
FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier,
496
                              CXXBasePath &Path,
497
115k
                              DeclarationName Name) {
498
115k
  RecordDecl *BaseRecord =
499
115k
    Specifier->getType()->castAs<RecordType>()->getDecl();
500
115k
501
115k
  for (Path.Decls = BaseRecord->lookup(Name);
502
115k
       !Path.Decls.empty();
503
4.73k
       
Path.Decls = Path.Decls.slice(1)0
) {
504
    // FIXME: Refactor the "is it a nested-name-specifier?" check
505
4.73k
    if (isa<TypedefNameDecl>(Path.Decls.front()) ||
506
4.73k
        Path.Decls.front()->isInIdentifierNamespace(IDNS_Tag))
507
4.73k
      return true;
508
4.73k
  }
509
115k
510
110k
  return false;
511
115k
}
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.1k
                            UniqueVirtualMethod Overriding) {
545
76.1k
  SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides
546
76.1k
    = Overrides[OverriddenSubobject];
547
76.1k
  if (llvm::find(SubobjectOverrides, Overriding) == SubobjectOverrides.end())
548
75.9k
    SubobjectOverrides.push_back(Overriding);
549
76.1k
}
550
551
31.3k
void OverridingMethods::add(const OverridingMethods &Other) {
552
62.7k
  for (const_iterator I = Other.begin(), IE = Other.end(); I != IE; 
++I31.4k
) {
553
31.4k
    for (overriding_const_iterator M = I->second.begin(),
554
31.4k
                                MEnd = I->second.end();
555
62.8k
         M != MEnd;
556
31.4k
         ++M)
557
31.4k
      add(I->first, *M);
558
31.4k
  }
559
31.3k
}
560
561
42.1k
void OverridingMethods::replaceAll(UniqueVirtualMethod Overriding) {
562
84.5k
  for (iterator I = begin(), IEnd = end(); I != IEnd; 
++I42.3k
) {
563
42.3k
    I->second.clear();
564
42.3k
    I->second.push_back(Overriding);
565
42.3k
  }
566
42.1k
}
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
35.7k
                                      CXXFinalOverriderMap &Overriders) {
594
35.7k
  unsigned SubobjectNumber = 0;
595
35.7k
  if (!VirtualBase)
596
30.8k
    SubobjectNumber
597
30.8k
      = ++SubobjectCount[cast<CXXRecordDecl>(RD->getCanonicalDecl())];
598
35.7k
599
27.8k
  for (const auto &Base : RD->bases()) {
600
27.8k
    if (const RecordType *RT = Base.getType()->getAs<RecordType>()) {
601
27.8k
      const CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(RT->getDecl());
602
27.8k
      if (!BaseDecl->isPolymorphic())
603
12.7k
        continue;
604
15.1k
605
15.1k
      if (Overriders.empty() && 
!Base.isVirtual()13.3k
) {
606
        // There are no other overriders of virtual member functions,
607
        // so let the base class fill in our overriders for us.
608
8.38k
        Collect(BaseDecl, false, InVirtualSubobject, Overriders);
609
8.38k
        continue;
610
8.38k
      }
611
6.72k
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.72k
      CXXFinalOverriderMap ComputedBaseOverriders;
618
6.72k
      CXXFinalOverriderMap *BaseOverriders = &ComputedBaseOverriders;
619
6.72k
      if (Base.isVirtual()) {
620
5.33k
        CXXFinalOverriderMap *&MyVirtualOverriders = VirtualOverriders[BaseDecl];
621
5.33k
        BaseOverriders = MyVirtualOverriders;
622
5.33k
        if (!MyVirtualOverriders) {
623
4.92k
          MyVirtualOverriders = new CXXFinalOverriderMap;
624
4.92k
625
          // Collect may cause VirtualOverriders to reallocate, invalidating the
626
          // MyVirtualOverriders reference. Set BaseOverriders to the right
627
          // value now.
628
4.92k
          BaseOverriders = MyVirtualOverriders;
629
4.92k
630
4.92k
          Collect(BaseDecl, true, BaseDecl, *MyVirtualOverriders);
631
4.92k
        }
632
5.33k
      } else
633
1.39k
        Collect(BaseDecl, false, InVirtualSubobject, ComputedBaseOverriders);
634
6.72k
635
      // Merge the overriders from this base class into our own set of
636
      // overriders.
637
6.72k
      for (CXXFinalOverriderMap::iterator OM = BaseOverriders->begin(),
638
6.72k
                               OMEnd = BaseOverriders->end();
639
38.0k
           OM != OMEnd;
640
31.3k
           ++OM) {
641
31.3k
        const CXXMethodDecl *CanonOM = OM->first->getCanonicalDecl();
642
31.3k
        Overriders[CanonOM].add(OM->second);
643
31.3k
      }
644
6.72k
    }
645
27.8k
  }
646
35.7k
647
275k
  for (auto *M : RD->methods()) {
648
    // We only care about virtual methods.
649
275k
    if (!M->isVirtual())
650
230k
      continue;
651
44.7k
652
44.7k
    CXXMethodDecl *CanonM = M->getCanonicalDecl();
653
44.7k
    using OverriddenMethodsRange =
654
44.7k
        llvm::iterator_range<CXXMethodDecl::method_iterator>;
655
44.7k
    OverriddenMethodsRange OverriddenMethods = CanonM->overridden_methods();
656
44.7k
657
44.7k
    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
28.2k
662
      // C++ [class.virtual]p2:
663
      //   For convenience we say that any virtual function overrides itself.
664
28.2k
      Overriders[CanonM].add(SubobjectNumber,
665
28.2k
                             UniqueVirtualMethod(CanonM, SubobjectNumber,
666
28.2k
                                                 InVirtualSubobject));
667
28.2k
      continue;
668
28.2k
    }
669
16.5k
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.5k
    SmallVector<OverriddenMethodsRange, 4> Stack(1, OverriddenMethods);
677
57.7k
    while (!Stack.empty()) {
678
42.1k
      for (const CXXMethodDecl *OM : Stack.pop_back_val()) {
679
42.1k
        const CXXMethodDecl *CanonOM = OM->getCanonicalDecl();
680
42.1k
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.1k
        Overriders[CanonOM].replaceAll(
691
42.1k
                               UniqueVirtualMethod(CanonM, SubobjectNumber,
692
42.1k
                                                   InVirtualSubobject));
693
42.1k
694
42.1k
        auto OverriddenMethods = CanonOM->overridden_methods();
695
42.1k
        if (OverriddenMethods.begin() == OverriddenMethods.end())
696
17.3k
          continue;
697
24.7k
698
        // Continue recursion to the methods that this virtual method
699
        // overrides.
700
24.7k
        Stack.push_back(OverriddenMethods);
701
24.7k
      }
702
41.2k
    }
703
16.5k
704
    // C++ [class.virtual]p2:
705
    //   For convenience we say that any virtual function overrides itself.
706
16.5k
    Overriders[CanonM].add(SubobjectNumber,
707
16.5k
                           UniqueVirtualMethod(CanonM, SubobjectNumber,
708
16.5k
                                               InVirtualSubobject));
709
16.5k
  }
710
35.7k
}
711
712
21.0k
FinalOverriderCollector::~FinalOverriderCollector() {
713
21.0k
  for (llvm::DenseMap<const CXXRecordDecl *, CXXFinalOverriderMap *>::iterator
714
21.0k
         VO = VirtualOverriders.begin(), VOEnd = VirtualOverriders.end();
715
25.9k
       VO != VOEnd;
716
4.92k
       ++VO)
717
4.92k
    delete VO->second;
718
21.0k
}
719
720
void
721
21.0k
CXXRecordDecl::getFinalOverriders(CXXFinalOverriderMap &FinalOverriders) const {
722
21.0k
  FinalOverriderCollector Collector;
723
21.0k
  Collector.Collect(this, false, nullptr, FinalOverriders);
724
21.0k
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
44.3k
  for (auto &OM : FinalOverriders) {
729
44.7k
    for (auto &SO : OM.second) {
730
44.7k
      SmallVectorImpl<UniqueVirtualMethod> &Overriding = SO.second;
731
44.7k
      if (Overriding.size() < 2)
732
44.6k
        continue;
733
98
734
196
      
auto IsHidden = [&Overriding](const UniqueVirtualMethod &M) 98
{
735
196
        if (!M.InVirtualSubobject)
736
94
          return false;
737
102
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
98
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
44.3k
  }
758
21.0k
}
759
760
static void
761
AddIndirectPrimaryBases(const CXXRecordDecl *RD, ASTContext &Context,
762
868
                        CXXIndirectPrimaryBaseSet& Bases) {
763
  // If the record has a virtual primary base class, add it to our set.
764
868
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
765
868
  if (Layout.isPrimaryBaseVirtual())
766
178
    Bases.insert(Layout.getPrimaryBase());
767
868
768
1.26k
  for (const auto &I : RD->bases()) {
769
1.26k
    assert(!I.getType()->isDependentType() &&
770
1.26k
           "Cannot get indirect primary bases for class with dependent bases.");
771
1.26k
772
1.26k
    const CXXRecordDecl *BaseDecl =
773
1.26k
      cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
774
1.26k
775
    // Only bases with virtual bases participate in computing the
776
    // indirect primary virtual base classes.
777
1.26k
    if (BaseDecl->getNumVBases())
778
417
      AddIndirectPrimaryBases(BaseDecl, Context, Bases);
779
1.26k
  }
780
868
781
868
}
782
783
void
784
11.6k
CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
785
11.6k
  ASTContext &Context = getASTContext();
786
11.6k
787
11.6k
  if (!getNumVBases())
788
10.7k
    return;
789
915
790
1.22k
  
for (const auto &I : bases())915
{
791
1.22k
    assert(!I.getType()->isDependentType() &&
792
1.22k
           "Cannot get indirect primary bases for class with dependent bases.");
793
1.22k
794
1.22k
    const CXXRecordDecl *BaseDecl =
795
1.22k
      cast<CXXRecordDecl>(I.getType()->castAs<RecordType>()->getDecl());
796
1.22k
797
    // Only bases with virtual bases participate in computing the
798
    // indirect primary virtual base classes.
799
1.22k
    if (BaseDecl->getNumVBases())
800
451
      AddIndirectPrimaryBases(BaseDecl, Context, Bases);
801
1.22k
  }
802
915
}