Coverage Report

Created: 2020-02-18 08:44

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