1//===------ CXXInheritance.cpp - C++ Inheritance ----------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file provides routines that help analyzing C++ inheritance hierarchies.
11//
12//===----------------------------------------------------------------------===//
13#include "clang/AST/CXXInheritance.h"
14#include "clang/AST/DeclCXX.h"
15#include <algorithm>
16#include <set>
17
18using namespace clang;
19
20/// \brief Computes the set of declarations referenced by these base
21/// paths.
22void CXXBasePaths::ComputeDeclsFound() {
23 assert(NumDeclsFound == 0 && !DeclsFound &&
24 "Already computed the set of declarations");
25
26 std::set<NamedDecl *> Decls;
27 for (CXXBasePaths::paths_iterator Path = begin(), PathEnd = end();
28 Path != PathEnd; ++Path)
29 Decls.insert(*Path->Decls.first);
30
31 NumDeclsFound = Decls.size();
32 DeclsFound = new NamedDecl * [NumDeclsFound];
33 std::copy(Decls.begin(), Decls.end(), DeclsFound);
34}
35
36CXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() {
37 if (NumDeclsFound == 0)
38 ComputeDeclsFound();
39 return DeclsFound;
40}
41
42CXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() {
43 if (NumDeclsFound == 0)
44 ComputeDeclsFound();
45 return DeclsFound + NumDeclsFound;
46}
47
48/// isAmbiguous - Determines whether the set of paths provided is
49/// ambiguous, i.e., there are two or more paths that refer to
50/// different base class subobjects of the same type. BaseType must be
51/// an unqualified, canonical class type.
52bool CXXBasePaths::isAmbiguous(QualType BaseType) {
53 assert(BaseType.isCanonical() && "Base type must be the canonical type");
54 assert(BaseType.hasQualifiers() == 0 && "Base type must be unqualified");
55 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
56 return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
57}
58
59/// clear - Clear out all prior path information.
60void CXXBasePaths::clear() {
61 Paths.clear();
62 ClassSubobjects.clear();
63 ScratchPath.clear();
64 DetectedVirtual = 0;
65}
66
67/// @brief Swaps the contents of this CXXBasePaths structure with the
68/// contents of Other.
69void CXXBasePaths::swap(CXXBasePaths &Other) {
70 std::swap(Origin, Other.Origin);
71 Paths.swap(Other.Paths);
72 ClassSubobjects.swap(Other.ClassSubobjects);
73 std::swap(FindAmbiguities, Other.FindAmbiguities);
74 std::swap(RecordPaths, Other.RecordPaths);
75 std::swap(DetectVirtual, Other.DetectVirtual);
76 std::swap(DetectedVirtual, Other.DetectedVirtual);
77}
78
79bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base) const {
80 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
81 /*DetectVirtual=*/false);
82 return isDerivedFrom(Base, Paths);
83}
84
85bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base, CXXBasePaths &Paths) const {
86 if (getCanonicalDecl() == Base->getCanonicalDecl())
87 return false;
88
89 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
90 return lookupInBases(&FindBaseClass, Base->getCanonicalDecl(), Paths);
91}
92
| 1//===------ CXXInheritance.cpp - C++ Inheritance ----------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file provides routines that help analyzing C++ inheritance hierarchies.
11//
12//===----------------------------------------------------------------------===//
13#include "clang/AST/CXXInheritance.h"
14#include "clang/AST/DeclCXX.h"
15#include <algorithm>
16#include <set>
17
18using namespace clang;
19
20/// \brief Computes the set of declarations referenced by these base
21/// paths.
22void CXXBasePaths::ComputeDeclsFound() {
23 assert(NumDeclsFound == 0 && !DeclsFound &&
24 "Already computed the set of declarations");
25
26 std::set<NamedDecl *> Decls;
27 for (CXXBasePaths::paths_iterator Path = begin(), PathEnd = end();
28 Path != PathEnd; ++Path)
29 Decls.insert(*Path->Decls.first);
30
31 NumDeclsFound = Decls.size();
32 DeclsFound = new NamedDecl * [NumDeclsFound];
33 std::copy(Decls.begin(), Decls.end(), DeclsFound);
34}
35
36CXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() {
37 if (NumDeclsFound == 0)
38 ComputeDeclsFound();
39 return DeclsFound;
40}
41
42CXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() {
43 if (NumDeclsFound == 0)
44 ComputeDeclsFound();
45 return DeclsFound + NumDeclsFound;
46}
47
48/// isAmbiguous - Determines whether the set of paths provided is
49/// ambiguous, i.e., there are two or more paths that refer to
50/// different base class subobjects of the same type. BaseType must be
51/// an unqualified, canonical class type.
52bool CXXBasePaths::isAmbiguous(QualType BaseType) {
53 assert(BaseType.isCanonical() && "Base type must be the canonical type");
54 assert(BaseType.hasQualifiers() == 0 && "Base type must be unqualified");
55 std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
56 return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
57}
58
59/// clear - Clear out all prior path information.
60void CXXBasePaths::clear() {
61 Paths.clear();
62 ClassSubobjects.clear();
63 ScratchPath.clear();
64 DetectedVirtual = 0;
65}
66
67/// @brief Swaps the contents of this CXXBasePaths structure with the
68/// contents of Other.
69void CXXBasePaths::swap(CXXBasePaths &Other) {
70 std::swap(Origin, Other.Origin);
71 Paths.swap(Other.Paths);
72 ClassSubobjects.swap(Other.ClassSubobjects);
73 std::swap(FindAmbiguities, Other.FindAmbiguities);
74 std::swap(RecordPaths, Other.RecordPaths);
75 std::swap(DetectVirtual, Other.DetectVirtual);
76 std::swap(DetectedVirtual, Other.DetectedVirtual);
77}
78
79bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base) const {
80 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
81 /*DetectVirtual=*/false);
82 return isDerivedFrom(Base, Paths);
83}
84
85bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base, CXXBasePaths &Paths) const {
86 if (getCanonicalDecl() == Base->getCanonicalDecl())
87 return false;
88
89 Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
90 return lookupInBases(&FindBaseClass, Base->getCanonicalDecl(), Paths);
91}
92
|
| 93static bool BaseIsNot(const CXXRecordDecl *Base, void *OpaqueTarget) {
94 // OpaqueTarget is a CXXRecordDecl*.
95 return Base->getCanonicalDecl() != (const CXXRecordDecl*) OpaqueTarget;
96}
97
98bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
99 return forallBases(BaseIsNot, (void*) Base->getCanonicalDecl());
100}
101
102bool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches,
103 void *OpaqueData,
104 bool AllowShortCircuit) const {
105 ASTContext &Context = getASTContext();
106 llvm::SmallVector<const CXXRecordDecl*, 8> Queue;
107
108 const CXXRecordDecl *Record = this;
109 bool AllMatches = true;
110 while (true) {
111 for (CXXRecordDecl::base_class_const_iterator
112 I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) {
113 const RecordType *Ty = I->getType()->getAs<RecordType>();
114 if (!Ty) {
115 if (AllowShortCircuit) return false;
116 AllMatches = false;
117 continue;
118 }
119
120 CXXRecordDecl *Base =
121 cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition(Context));
122 if (!Base) {
123 if (AllowShortCircuit) return false;
124 AllMatches = false;
125 continue;
126 }
127
128 Queue.push_back(Base);
129 if (!BaseMatches(Base, OpaqueData)) {
130 if (AllowShortCircuit) return false;
131 AllMatches = false;
132 continue;
133 }
134 }
135
136 if (Queue.empty()) break;
137 Record = Queue.back(); // not actually a queue.
138 Queue.pop_back();
139 }
140
141 return AllMatches;
142}
143
|
93bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches,
94 void *UserData,
95 CXXBasePaths &Paths) const {
96 bool FoundPath = false;
97
98 ASTContext &Context = getASTContext();
99 for (base_class_const_iterator BaseSpec = bases_begin(),
100 BaseSpecEnd = bases_end(); BaseSpec != BaseSpecEnd; ++BaseSpec) {
101 // Find the record of the base class subobjects for this type.
102 QualType BaseType = Context.getCanonicalType(BaseSpec->getType())
103 .getUnqualifiedType();
104
105 // C++ [temp.dep]p3:
106 // In the definition of a class template or a member of a class template,
107 // if a base class of the class template depends on a template-parameter,
108 // the base class scope is not examined during unqualified name lookup
109 // either at the point of definition of the class template or member or
110 // during an instantiation of the class tem- plate or member.
111 if (BaseType->isDependentType())
112 continue;
113
114 // Determine whether we need to visit this base class at all,
115 // updating the count of subobjects appropriately.
116 std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType];
117 bool VisitBase = true;
118 bool SetVirtual = false;
119 if (BaseSpec->isVirtual()) {
120 VisitBase = !Subobjects.first;
121 Subobjects.first = true;
122 if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) {
123 // If this is the first virtual we find, remember it. If it turns out
124 // there is no base path here, we'll reset it later.
125 Paths.DetectedVirtual = BaseType->getAs<RecordType>();
126 SetVirtual = true;
127 }
128 } else
129 ++Subobjects.second;
130
131 if (Paths.isRecordingPaths()) {
132 // Add this base specifier to the current path.
133 CXXBasePathElement Element;
134 Element.Base = &*BaseSpec;
135 Element.Class = this;
136 if (BaseSpec->isVirtual())
137 Element.SubobjectNumber = 0;
138 else
139 Element.SubobjectNumber = Subobjects.second;
140 Paths.ScratchPath.push_back(Element);
141 }
142
143 if (BaseMatches(BaseSpec, Paths.ScratchPath, UserData)) {
144 // We've found a path that terminates that this base.
145 FoundPath = true;
146 if (Paths.isRecordingPaths()) {
147 // We have a path. Make a copy of it before moving on.
148 Paths.Paths.push_back(Paths.ScratchPath);
149 } else if (!Paths.isFindingAmbiguities()) {
150 // We found a path and we don't care about ambiguities;
151 // return immediately.
152 return FoundPath;
153 }
154 } else if (VisitBase) {
155 CXXRecordDecl *BaseRecord
156 = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>()
157 ->getDecl());
158 if (BaseRecord->lookupInBases(BaseMatches, UserData, Paths)) {
159 // C++ [class.member.lookup]p2:
160 // A member name f in one sub-object B hides a member name f in
161 // a sub-object A if A is a base class sub-object of B. Any
162 // declarations that are so hidden are eliminated from
163 // consideration.
164
165 // There is a path to a base class that meets the criteria. If we're
166 // not collecting paths or finding ambiguities, we're done.
167 FoundPath = true;
168 if (!Paths.isFindingAmbiguities())
169 return FoundPath;
170 }
171 }
172
173 // Pop this base specifier off the current path (if we're
174 // collecting paths).
175 if (Paths.isRecordingPaths())
176 Paths.ScratchPath.pop_back();
177 // If we set a virtual earlier, and this isn't a path, forget it again.
178 if (SetVirtual && !FoundPath) {
179 Paths.DetectedVirtual = 0;
180 }
181 }
182
183 return FoundPath;
184}
185
186bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
187 CXXBasePath &Path,
188 void *BaseRecord) {
189 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
190 "User data for FindBaseClass is not canonical!");
191 return Specifier->getType()->getAs<RecordType>()->getDecl()
192 ->getCanonicalDecl() == BaseRecord;
193}
194
195bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier,
196 CXXBasePath &Path,
197 void *Name) {
198 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
199
200 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
201 for (Path.Decls = BaseRecord->lookup(N);
202 Path.Decls.first != Path.Decls.second;
203 ++Path.Decls.first) {
204 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
205 return true;
206 }
207
208 return false;
209}
210
211bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier,
212 CXXBasePath &Path,
213 void *Name) {
214 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
215
216 const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member;
217 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
218 for (Path.Decls = BaseRecord->lookup(N);
219 Path.Decls.first != Path.Decls.second;
220 ++Path.Decls.first) {
221 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS))
222 return true;
223 }
224
225 return false;
226}
227
228bool CXXRecordDecl::
229FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier,
230 CXXBasePath &Path,
231 void *Name) {
232 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
233
234 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
235 for (Path.Decls = BaseRecord->lookup(N);
236 Path.Decls.first != Path.Decls.second;
237 ++Path.Decls.first) {
238 // FIXME: Refactor the "is it a nested-name-specifier?" check
239 if (isa<TypedefDecl>(*Path.Decls.first) ||
240 (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
241 return true;
242 }
243
244 return false;
245}
| 144bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches,
145 void *UserData,
146 CXXBasePaths &Paths) const {
147 bool FoundPath = false;
148
149 ASTContext &Context = getASTContext();
150 for (base_class_const_iterator BaseSpec = bases_begin(),
151 BaseSpecEnd = bases_end(); BaseSpec != BaseSpecEnd; ++BaseSpec) {
152 // Find the record of the base class subobjects for this type.
153 QualType BaseType = Context.getCanonicalType(BaseSpec->getType())
154 .getUnqualifiedType();
155
156 // C++ [temp.dep]p3:
157 // In the definition of a class template or a member of a class template,
158 // if a base class of the class template depends on a template-parameter,
159 // the base class scope is not examined during unqualified name lookup
160 // either at the point of definition of the class template or member or
161 // during an instantiation of the class tem- plate or member.
162 if (BaseType->isDependentType())
163 continue;
164
165 // Determine whether we need to visit this base class at all,
166 // updating the count of subobjects appropriately.
167 std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType];
168 bool VisitBase = true;
169 bool SetVirtual = false;
170 if (BaseSpec->isVirtual()) {
171 VisitBase = !Subobjects.first;
172 Subobjects.first = true;
173 if (Paths.isDetectingVirtual() && Paths.DetectedVirtual == 0) {
174 // If this is the first virtual we find, remember it. If it turns out
175 // there is no base path here, we'll reset it later.
176 Paths.DetectedVirtual = BaseType->getAs<RecordType>();
177 SetVirtual = true;
178 }
179 } else
180 ++Subobjects.second;
181
182 if (Paths.isRecordingPaths()) {
183 // Add this base specifier to the current path.
184 CXXBasePathElement Element;
185 Element.Base = &*BaseSpec;
186 Element.Class = this;
187 if (BaseSpec->isVirtual())
188 Element.SubobjectNumber = 0;
189 else
190 Element.SubobjectNumber = Subobjects.second;
191 Paths.ScratchPath.push_back(Element);
192 }
193
194 if (BaseMatches(BaseSpec, Paths.ScratchPath, UserData)) {
195 // We've found a path that terminates that this base.
196 FoundPath = true;
197 if (Paths.isRecordingPaths()) {
198 // We have a path. Make a copy of it before moving on.
199 Paths.Paths.push_back(Paths.ScratchPath);
200 } else if (!Paths.isFindingAmbiguities()) {
201 // We found a path and we don't care about ambiguities;
202 // return immediately.
203 return FoundPath;
204 }
205 } else if (VisitBase) {
206 CXXRecordDecl *BaseRecord
207 = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>()
208 ->getDecl());
209 if (BaseRecord->lookupInBases(BaseMatches, UserData, Paths)) {
210 // C++ [class.member.lookup]p2:
211 // A member name f in one sub-object B hides a member name f in
212 // a sub-object A if A is a base class sub-object of B. Any
213 // declarations that are so hidden are eliminated from
214 // consideration.
215
216 // There is a path to a base class that meets the criteria. If we're
217 // not collecting paths or finding ambiguities, we're done.
218 FoundPath = true;
219 if (!Paths.isFindingAmbiguities())
220 return FoundPath;
221 }
222 }
223
224 // Pop this base specifier off the current path (if we're
225 // collecting paths).
226 if (Paths.isRecordingPaths())
227 Paths.ScratchPath.pop_back();
228 // If we set a virtual earlier, and this isn't a path, forget it again.
229 if (SetVirtual && !FoundPath) {
230 Paths.DetectedVirtual = 0;
231 }
232 }
233
234 return FoundPath;
235}
236
237bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
238 CXXBasePath &Path,
239 void *BaseRecord) {
240 assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
241 "User data for FindBaseClass is not canonical!");
242 return Specifier->getType()->getAs<RecordType>()->getDecl()
243 ->getCanonicalDecl() == BaseRecord;
244}
245
246bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier,
247 CXXBasePath &Path,
248 void *Name) {
249 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
250
251 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
252 for (Path.Decls = BaseRecord->lookup(N);
253 Path.Decls.first != Path.Decls.second;
254 ++Path.Decls.first) {
255 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
256 return true;
257 }
258
259 return false;
260}
261
262bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier,
263 CXXBasePath &Path,
264 void *Name) {
265 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
266
267 const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member;
268 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
269 for (Path.Decls = BaseRecord->lookup(N);
270 Path.Decls.first != Path.Decls.second;
271 ++Path.Decls.first) {
272 if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS))
273 return true;
274 }
275
276 return false;
277}
278
279bool CXXRecordDecl::
280FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier,
281 CXXBasePath &Path,
282 void *Name) {
283 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
284
285 DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
286 for (Path.Decls = BaseRecord->lookup(N);
287 Path.Decls.first != Path.Decls.second;
288 ++Path.Decls.first) {
289 // FIXME: Refactor the "is it a nested-name-specifier?" check
290 if (isa<TypedefDecl>(*Path.Decls.first) ||
291 (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
292 return true;
293 }
294
295 return false;
296}
|