1 //===- ASTStructuralEquivalence.cpp ---------------------------------------===//
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 implement StructuralEquivalenceContext class and helper functions
10 // for layout matching.
11 //
12 // The structural equivalence check could have been implemented as a parallel
13 // BFS on a pair of graphs. That must have been the original approach at the
14 // beginning.
15 // Let's consider this simple BFS algorithm from the `s` source:
16 // ```
17 // void bfs(Graph G, int s)
18 // {
19 // Queue<Integer> queue = new Queue<Integer>();
20 // marked[s] = true; // Mark the source
21 // queue.enqueue(s); // and put it on the queue.
22 // while (!q.isEmpty()) {
23 // int v = queue.dequeue(); // Remove next vertex from the queue.
24 // for (int w : G.adj(v))
25 // if (!marked[w]) // For every unmarked adjacent vertex,
26 // {
27 // marked[w] = true;
28 // queue.enqueue(w);
29 // }
30 // }
31 // }
32 // ```
33 // Indeed, it has it's queue, which holds pairs of nodes, one from each graph,
34 // this is the `DeclsToCheck` member. `VisitedDecls` plays the role of the
35 // marking (`marked`) functionality above, we use it to check whether we've
36 // already seen a pair of nodes.
37 //
38 // We put in the elements into the queue only in the toplevel decl check
39 // function:
40 // ```
41 // static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
42 // Decl *D1, Decl *D2);
43 // ```
44 // The `while` loop where we iterate over the children is implemented in
45 // `Finish()`. And `Finish` is called only from the two **member** functions
46 // which check the equivalency of two Decls or two Types. ASTImporter (and
47 // other clients) call only these functions.
48 //
49 // The `static` implementation functions are called from `Finish`, these push
50 // the children nodes to the queue via `static bool
51 // IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1,
52 // Decl *D2)`. So far so good, this is almost like the BFS. However, if we
53 // let a static implementation function to call `Finish` via another **member**
54 // function that means we end up with two nested while loops each of them
55 // working on the same queue. This is wrong and nobody can reason about it's
56 // doing. Thus, static implementation functions must not call the **member**
57 // functions.
58 //
59 //===----------------------------------------------------------------------===//
60
61 #include "clang/AST/ASTStructuralEquivalence.h"
62 #include "clang/AST/ASTContext.h"
63 #include "clang/AST/ASTDiagnostic.h"
64 #include "clang/AST/Decl.h"
65 #include "clang/AST/DeclBase.h"
66 #include "clang/AST/DeclCXX.h"
67 #include "clang/AST/DeclFriend.h"
68 #include "clang/AST/DeclObjC.h"
69 #include "clang/AST/DeclOpenMP.h"
70 #include "clang/AST/DeclTemplate.h"
71 #include "clang/AST/ExprCXX.h"
72 #include "clang/AST/ExprConcepts.h"
73 #include "clang/AST/ExprObjC.h"
74 #include "clang/AST/ExprOpenMP.h"
75 #include "clang/AST/NestedNameSpecifier.h"
76 #include "clang/AST/StmtObjC.h"
77 #include "clang/AST/StmtOpenMP.h"
78 #include "clang/AST/TemplateBase.h"
79 #include "clang/AST/TemplateName.h"
80 #include "clang/AST/Type.h"
81 #include "clang/Basic/ExceptionSpecificationType.h"
82 #include "clang/Basic/IdentifierTable.h"
83 #include "clang/Basic/LLVM.h"
84 #include "clang/Basic/SourceLocation.h"
85 #include "llvm/ADT/APInt.h"
86 #include "llvm/ADT/APSInt.h"
87 #include "llvm/ADT/None.h"
88 #include "llvm/ADT/Optional.h"
89 #include "llvm/ADT/StringExtras.h"
90 #include "llvm/Support/Casting.h"
91 #include "llvm/Support/Compiler.h"
92 #include "llvm/Support/ErrorHandling.h"
93 #include <cassert>
94 #include <utility>
95
96 using namespace clang;
97
98 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
99 QualType T1, QualType T2);
100 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
101 Decl *D1, Decl *D2);
102 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
103 const TemplateArgument &Arg1,
104 const TemplateArgument &Arg2);
105 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
106 NestedNameSpecifier *NNS1,
107 NestedNameSpecifier *NNS2);
108 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
109 const IdentifierInfo *Name2);
110
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,const DeclarationName Name1,const DeclarationName Name2)111 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
112 const DeclarationName Name1,
113 const DeclarationName Name2) {
114 if (Name1.getNameKind() != Name2.getNameKind())
115 return false;
116
117 switch (Name1.getNameKind()) {
118
119 case DeclarationName::Identifier:
120 return IsStructurallyEquivalent(Name1.getAsIdentifierInfo(),
121 Name2.getAsIdentifierInfo());
122
123 case DeclarationName::CXXConstructorName:
124 case DeclarationName::CXXDestructorName:
125 case DeclarationName::CXXConversionFunctionName:
126 return IsStructurallyEquivalent(Context, Name1.getCXXNameType(),
127 Name2.getCXXNameType());
128
129 case DeclarationName::CXXDeductionGuideName: {
130 if (!IsStructurallyEquivalent(
131 Context, Name1.getCXXDeductionGuideTemplate()->getDeclName(),
132 Name2.getCXXDeductionGuideTemplate()->getDeclName()))
133 return false;
134 return IsStructurallyEquivalent(Context,
135 Name1.getCXXDeductionGuideTemplate(),
136 Name2.getCXXDeductionGuideTemplate());
137 }
138
139 case DeclarationName::CXXOperatorName:
140 return Name1.getCXXOverloadedOperator() == Name2.getCXXOverloadedOperator();
141
142 case DeclarationName::CXXLiteralOperatorName:
143 return IsStructurallyEquivalent(Name1.getCXXLiteralIdentifier(),
144 Name2.getCXXLiteralIdentifier());
145
146 case DeclarationName::CXXUsingDirective:
147 return true; // FIXME When do we consider two using directives equal?
148
149 case DeclarationName::ObjCZeroArgSelector:
150 case DeclarationName::ObjCOneArgSelector:
151 case DeclarationName::ObjCMultiArgSelector:
152 return true; // FIXME
153 }
154
155 llvm_unreachable("Unhandled kind of DeclarationName");
156 return true;
157 }
158
159 namespace {
160 /// Encapsulates Stmt comparison logic.
161 class StmtComparer {
162 StructuralEquivalenceContext &Context;
163
164 // IsStmtEquivalent overloads. Each overload compares a specific statement
165 // and only has to compare the data that is specific to the specific statement
166 // class. Should only be called from TraverseStmt.
167
IsStmtEquivalent(const AddrLabelExpr * E1,const AddrLabelExpr * E2)168 bool IsStmtEquivalent(const AddrLabelExpr *E1, const AddrLabelExpr *E2) {
169 return IsStructurallyEquivalent(Context, E1->getLabel(), E2->getLabel());
170 }
171
IsStmtEquivalent(const AtomicExpr * E1,const AtomicExpr * E2)172 bool IsStmtEquivalent(const AtomicExpr *E1, const AtomicExpr *E2) {
173 return E1->getOp() == E2->getOp();
174 }
175
IsStmtEquivalent(const BinaryOperator * E1,const BinaryOperator * E2)176 bool IsStmtEquivalent(const BinaryOperator *E1, const BinaryOperator *E2) {
177 return E1->getOpcode() == E2->getOpcode();
178 }
179
IsStmtEquivalent(const CallExpr * E1,const CallExpr * E2)180 bool IsStmtEquivalent(const CallExpr *E1, const CallExpr *E2) {
181 // FIXME: IsStructurallyEquivalent requires non-const Decls.
182 Decl *Callee1 = const_cast<Decl *>(E1->getCalleeDecl());
183 Decl *Callee2 = const_cast<Decl *>(E2->getCalleeDecl());
184
185 // Compare whether both calls know their callee.
186 if (static_cast<bool>(Callee1) != static_cast<bool>(Callee2))
187 return false;
188
189 // Both calls have no callee, so nothing to do.
190 if (!static_cast<bool>(Callee1))
191 return true;
192
193 assert(Callee2);
194 return IsStructurallyEquivalent(Context, Callee1, Callee2);
195 }
196
IsStmtEquivalent(const CharacterLiteral * E1,const CharacterLiteral * E2)197 bool IsStmtEquivalent(const CharacterLiteral *E1,
198 const CharacterLiteral *E2) {
199 return E1->getValue() == E2->getValue() && E1->getKind() == E2->getKind();
200 }
201
IsStmtEquivalent(const ChooseExpr * E1,const ChooseExpr * E2)202 bool IsStmtEquivalent(const ChooseExpr *E1, const ChooseExpr *E2) {
203 return true; // Semantics only depend on children.
204 }
205
IsStmtEquivalent(const CompoundStmt * E1,const CompoundStmt * E2)206 bool IsStmtEquivalent(const CompoundStmt *E1, const CompoundStmt *E2) {
207 // Number of children is actually checked by the generic children comparison
208 // code, but a CompoundStmt is one of the few statements where the number of
209 // children frequently differs and the number of statements is also always
210 // precomputed. Directly comparing the number of children here is thus
211 // just an optimization.
212 return E1->size() == E2->size();
213 }
214
IsStmtEquivalent(const DependentScopeDeclRefExpr * DE1,const DependentScopeDeclRefExpr * DE2)215 bool IsStmtEquivalent(const DependentScopeDeclRefExpr *DE1,
216 const DependentScopeDeclRefExpr *DE2) {
217 if (!IsStructurallyEquivalent(Context, DE1->getDeclName(),
218 DE2->getDeclName()))
219 return false;
220 return IsStructurallyEquivalent(Context, DE1->getQualifier(),
221 DE2->getQualifier());
222 }
223
IsStmtEquivalent(const Expr * E1,const Expr * E2)224 bool IsStmtEquivalent(const Expr *E1, const Expr *E2) {
225 return IsStructurallyEquivalent(Context, E1->getType(), E2->getType());
226 }
227
IsStmtEquivalent(const ExpressionTraitExpr * E1,const ExpressionTraitExpr * E2)228 bool IsStmtEquivalent(const ExpressionTraitExpr *E1,
229 const ExpressionTraitExpr *E2) {
230 return E1->getTrait() == E2->getTrait() && E1->getValue() == E2->getValue();
231 }
232
IsStmtEquivalent(const FloatingLiteral * E1,const FloatingLiteral * E2)233 bool IsStmtEquivalent(const FloatingLiteral *E1, const FloatingLiteral *E2) {
234 return E1->isExact() == E2->isExact() && E1->getValue() == E2->getValue();
235 }
236
IsStmtEquivalent(const GenericSelectionExpr * E1,const GenericSelectionExpr * E2)237 bool IsStmtEquivalent(const GenericSelectionExpr *E1,
238 const GenericSelectionExpr *E2) {
239 for (auto Pair : zip_longest(E1->getAssocTypeSourceInfos(),
240 E2->getAssocTypeSourceInfos())) {
241 Optional<TypeSourceInfo *> Child1 = std::get<0>(Pair);
242 Optional<TypeSourceInfo *> Child2 = std::get<1>(Pair);
243 // Skip this case if there are a different number of associated types.
244 if (!Child1 || !Child2)
245 return false;
246
247 if (!IsStructurallyEquivalent(Context, (*Child1)->getType(),
248 (*Child2)->getType()))
249 return false;
250 }
251
252 return true;
253 }
254
IsStmtEquivalent(const ImplicitCastExpr * CastE1,const ImplicitCastExpr * CastE2)255 bool IsStmtEquivalent(const ImplicitCastExpr *CastE1,
256 const ImplicitCastExpr *CastE2) {
257 return IsStructurallyEquivalent(Context, CastE1->getType(),
258 CastE2->getType());
259 }
260
IsStmtEquivalent(const IntegerLiteral * E1,const IntegerLiteral * E2)261 bool IsStmtEquivalent(const IntegerLiteral *E1, const IntegerLiteral *E2) {
262 return E1->getValue() == E2->getValue();
263 }
264
IsStmtEquivalent(const MemberExpr * E1,const MemberExpr * E2)265 bool IsStmtEquivalent(const MemberExpr *E1, const MemberExpr *E2) {
266 return IsStructurallyEquivalent(Context, E1->getFoundDecl(),
267 E2->getFoundDecl());
268 }
269
IsStmtEquivalent(const ObjCStringLiteral * E1,const ObjCStringLiteral * E2)270 bool IsStmtEquivalent(const ObjCStringLiteral *E1,
271 const ObjCStringLiteral *E2) {
272 // Just wraps a StringLiteral child.
273 return true;
274 }
275
IsStmtEquivalent(const Stmt * S1,const Stmt * S2)276 bool IsStmtEquivalent(const Stmt *S1, const Stmt *S2) { return true; }
277
IsStmtEquivalent(const SourceLocExpr * E1,const SourceLocExpr * E2)278 bool IsStmtEquivalent(const SourceLocExpr *E1, const SourceLocExpr *E2) {
279 return E1->getIdentKind() == E2->getIdentKind();
280 }
281
IsStmtEquivalent(const StmtExpr * E1,const StmtExpr * E2)282 bool IsStmtEquivalent(const StmtExpr *E1, const StmtExpr *E2) {
283 return E1->getTemplateDepth() == E2->getTemplateDepth();
284 }
285
IsStmtEquivalent(const StringLiteral * E1,const StringLiteral * E2)286 bool IsStmtEquivalent(const StringLiteral *E1, const StringLiteral *E2) {
287 return E1->getBytes() == E2->getBytes();
288 }
289
IsStmtEquivalent(const SubstNonTypeTemplateParmExpr * E1,const SubstNonTypeTemplateParmExpr * E2)290 bool IsStmtEquivalent(const SubstNonTypeTemplateParmExpr *E1,
291 const SubstNonTypeTemplateParmExpr *E2) {
292 return IsStructurallyEquivalent(Context, E1->getParameter(),
293 E2->getParameter());
294 }
295
IsStmtEquivalent(const SubstNonTypeTemplateParmPackExpr * E1,const SubstNonTypeTemplateParmPackExpr * E2)296 bool IsStmtEquivalent(const SubstNonTypeTemplateParmPackExpr *E1,
297 const SubstNonTypeTemplateParmPackExpr *E2) {
298 return IsStructurallyEquivalent(Context, E1->getArgumentPack(),
299 E2->getArgumentPack());
300 }
301
IsStmtEquivalent(const TypeTraitExpr * E1,const TypeTraitExpr * E2)302 bool IsStmtEquivalent(const TypeTraitExpr *E1, const TypeTraitExpr *E2) {
303 if (E1->getTrait() != E2->getTrait())
304 return false;
305
306 for (auto Pair : zip_longest(E1->getArgs(), E2->getArgs())) {
307 Optional<TypeSourceInfo *> Child1 = std::get<0>(Pair);
308 Optional<TypeSourceInfo *> Child2 = std::get<1>(Pair);
309 // Different number of args.
310 if (!Child1 || !Child2)
311 return false;
312
313 if (!IsStructurallyEquivalent(Context, (*Child1)->getType(),
314 (*Child2)->getType()))
315 return false;
316 }
317 return true;
318 }
319
IsStmtEquivalent(const UnaryExprOrTypeTraitExpr * E1,const UnaryExprOrTypeTraitExpr * E2)320 bool IsStmtEquivalent(const UnaryExprOrTypeTraitExpr *E1,
321 const UnaryExprOrTypeTraitExpr *E2) {
322 if (E1->getKind() != E2->getKind())
323 return false;
324 return IsStructurallyEquivalent(Context, E1->getTypeOfArgument(),
325 E2->getTypeOfArgument());
326 }
327
IsStmtEquivalent(const UnaryOperator * E1,const UnaryOperator * E2)328 bool IsStmtEquivalent(const UnaryOperator *E1, const UnaryOperator *E2) {
329 return E1->getOpcode() == E2->getOpcode();
330 }
331
IsStmtEquivalent(const VAArgExpr * E1,const VAArgExpr * E2)332 bool IsStmtEquivalent(const VAArgExpr *E1, const VAArgExpr *E2) {
333 // Semantics only depend on children.
334 return true;
335 }
336
337 /// End point of the traversal chain.
TraverseStmt(const Stmt * S1,const Stmt * S2)338 bool TraverseStmt(const Stmt *S1, const Stmt *S2) { return true; }
339
340 // Create traversal methods that traverse the class hierarchy and return
341 // the accumulated result of the comparison. Each TraverseStmt overload
342 // calls the TraverseStmt overload of the parent class. For example,
343 // the TraverseStmt overload for 'BinaryOperator' calls the TraverseStmt
344 // overload of 'Expr' which then calls the overload for 'Stmt'.
345 #define STMT(CLASS, PARENT) \
346 bool TraverseStmt(const CLASS *S1, const CLASS *S2) { \
347 if (!TraverseStmt(static_cast<const PARENT *>(S1), \
348 static_cast<const PARENT *>(S2))) \
349 return false; \
350 return IsStmtEquivalent(S1, S2); \
351 }
352 #include "clang/AST/StmtNodes.inc"
353
354 public:
StmtComparer(StructuralEquivalenceContext & C)355 StmtComparer(StructuralEquivalenceContext &C) : Context(C) {}
356
357 /// Determine whether two statements are equivalent. The statements have to
358 /// be of the same kind. The children of the statements and their properties
359 /// are not compared by this function.
IsEquivalent(const Stmt * S1,const Stmt * S2)360 bool IsEquivalent(const Stmt *S1, const Stmt *S2) {
361 if (S1->getStmtClass() != S2->getStmtClass())
362 return false;
363
364 // Each TraverseStmt walks the class hierarchy from the leaf class to
365 // the root class 'Stmt' (e.g. 'BinaryOperator' -> 'Expr' -> 'Stmt'). Cast
366 // the Stmt we have here to its specific subclass so that we call the
367 // overload that walks the whole class hierarchy from leaf to root (e.g.,
368 // cast to 'BinaryOperator' so that 'Expr' and 'Stmt' is traversed).
369 switch (S1->getStmtClass()) {
370 case Stmt::NoStmtClass:
371 llvm_unreachable("Can't traverse NoStmtClass");
372 #define STMT(CLASS, PARENT) \
373 case Stmt::StmtClass::CLASS##Class: \
374 return TraverseStmt(static_cast<const CLASS *>(S1), \
375 static_cast<const CLASS *>(S2));
376 #define ABSTRACT_STMT(S)
377 #include "clang/AST/StmtNodes.inc"
378 }
379 llvm_unreachable("Invalid statement kind");
380 }
381 };
382 } // namespace
383
384 /// Determine structural equivalence of two statements.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,const Stmt * S1,const Stmt * S2)385 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
386 const Stmt *S1, const Stmt *S2) {
387 if (!S1 || !S2)
388 return S1 == S2;
389
390 // Compare the statements itself.
391 StmtComparer Comparer(Context);
392 if (!Comparer.IsEquivalent(S1, S2))
393 return false;
394
395 // Iterate over the children of both statements and also compare them.
396 for (auto Pair : zip_longest(S1->children(), S2->children())) {
397 Optional<const Stmt *> Child1 = std::get<0>(Pair);
398 Optional<const Stmt *> Child2 = std::get<1>(Pair);
399 // One of the statements has a different amount of children than the other,
400 // so the statements can't be equivalent.
401 if (!Child1 || !Child2)
402 return false;
403 if (!IsStructurallyEquivalent(Context, *Child1, *Child2))
404 return false;
405 }
406 return true;
407 }
408
409 /// Determine whether two identifiers are equivalent.
IsStructurallyEquivalent(const IdentifierInfo * Name1,const IdentifierInfo * Name2)410 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
411 const IdentifierInfo *Name2) {
412 if (!Name1 || !Name2)
413 return Name1 == Name2;
414
415 return Name1->getName() == Name2->getName();
416 }
417
418 /// Determine whether two nested-name-specifiers are equivalent.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,NestedNameSpecifier * NNS1,NestedNameSpecifier * NNS2)419 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
420 NestedNameSpecifier *NNS1,
421 NestedNameSpecifier *NNS2) {
422 if (NNS1->getKind() != NNS2->getKind())
423 return false;
424
425 NestedNameSpecifier *Prefix1 = NNS1->getPrefix(),
426 *Prefix2 = NNS2->getPrefix();
427 if ((bool)Prefix1 != (bool)Prefix2)
428 return false;
429
430 if (Prefix1)
431 if (!IsStructurallyEquivalent(Context, Prefix1, Prefix2))
432 return false;
433
434 switch (NNS1->getKind()) {
435 case NestedNameSpecifier::Identifier:
436 return IsStructurallyEquivalent(NNS1->getAsIdentifier(),
437 NNS2->getAsIdentifier());
438 case NestedNameSpecifier::Namespace:
439 return IsStructurallyEquivalent(Context, NNS1->getAsNamespace(),
440 NNS2->getAsNamespace());
441 case NestedNameSpecifier::NamespaceAlias:
442 return IsStructurallyEquivalent(Context, NNS1->getAsNamespaceAlias(),
443 NNS2->getAsNamespaceAlias());
444 case NestedNameSpecifier::TypeSpec:
445 case NestedNameSpecifier::TypeSpecWithTemplate:
446 return IsStructurallyEquivalent(Context, QualType(NNS1->getAsType(), 0),
447 QualType(NNS2->getAsType(), 0));
448 case NestedNameSpecifier::Global:
449 return true;
450 case NestedNameSpecifier::Super:
451 return IsStructurallyEquivalent(Context, NNS1->getAsRecordDecl(),
452 NNS2->getAsRecordDecl());
453 }
454 return false;
455 }
456
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,const TemplateName & N1,const TemplateName & N2)457 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
458 const TemplateName &N1,
459 const TemplateName &N2) {
460 TemplateDecl *TemplateDeclN1 = N1.getAsTemplateDecl();
461 TemplateDecl *TemplateDeclN2 = N2.getAsTemplateDecl();
462 if (TemplateDeclN1 && TemplateDeclN2) {
463 if (!IsStructurallyEquivalent(Context, TemplateDeclN1, TemplateDeclN2))
464 return false;
465 // If the kind is different we compare only the template decl.
466 if (N1.getKind() != N2.getKind())
467 return true;
468 } else if (TemplateDeclN1 || TemplateDeclN2)
469 return false;
470 else if (N1.getKind() != N2.getKind())
471 return false;
472
473 // Check for special case incompatibilities.
474 switch (N1.getKind()) {
475
476 case TemplateName::OverloadedTemplate: {
477 OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),
478 *OS2 = N2.getAsOverloadedTemplate();
479 OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),
480 E1 = OS1->end(), E2 = OS2->end();
481 for (; I1 != E1 && I2 != E2; ++I1, ++I2)
482 if (!IsStructurallyEquivalent(Context, *I1, *I2))
483 return false;
484 return I1 == E1 && I2 == E2;
485 }
486
487 case TemplateName::AssumedTemplate: {
488 AssumedTemplateStorage *TN1 = N1.getAsAssumedTemplateName(),
489 *TN2 = N1.getAsAssumedTemplateName();
490 return TN1->getDeclName() == TN2->getDeclName();
491 }
492
493 case TemplateName::DependentTemplate: {
494 DependentTemplateName *DN1 = N1.getAsDependentTemplateName(),
495 *DN2 = N2.getAsDependentTemplateName();
496 if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
497 DN2->getQualifier()))
498 return false;
499 if (DN1->isIdentifier() && DN2->isIdentifier())
500 return IsStructurallyEquivalent(DN1->getIdentifier(),
501 DN2->getIdentifier());
502 else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
503 return DN1->getOperator() == DN2->getOperator();
504 return false;
505 }
506
507 case TemplateName::SubstTemplateTemplateParmPack: {
508 SubstTemplateTemplateParmPackStorage
509 *P1 = N1.getAsSubstTemplateTemplateParmPack(),
510 *P2 = N2.getAsSubstTemplateTemplateParmPack();
511 return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
512 P2->getArgumentPack()) &&
513 IsStructurallyEquivalent(Context, P1->getParameterPack(),
514 P2->getParameterPack());
515 }
516
517 case TemplateName::Template:
518 case TemplateName::QualifiedTemplate:
519 case TemplateName::SubstTemplateTemplateParm:
520 // It is sufficient to check value of getAsTemplateDecl.
521 break;
522
523 }
524
525 return true;
526 }
527
528 /// Determine whether two template arguments are equivalent.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,const TemplateArgument & Arg1,const TemplateArgument & Arg2)529 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
530 const TemplateArgument &Arg1,
531 const TemplateArgument &Arg2) {
532 if (Arg1.getKind() != Arg2.getKind())
533 return false;
534
535 switch (Arg1.getKind()) {
536 case TemplateArgument::Null:
537 return true;
538
539 case TemplateArgument::Type:
540 return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());
541
542 case TemplateArgument::Integral:
543 if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),
544 Arg2.getIntegralType()))
545 return false;
546
547 return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
548 Arg2.getAsIntegral());
549
550 case TemplateArgument::Declaration:
551 return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());
552
553 case TemplateArgument::NullPtr:
554 return true; // FIXME: Is this correct?
555
556 case TemplateArgument::Template:
557 return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
558 Arg2.getAsTemplate());
559
560 case TemplateArgument::TemplateExpansion:
561 return IsStructurallyEquivalent(Context,
562 Arg1.getAsTemplateOrTemplatePattern(),
563 Arg2.getAsTemplateOrTemplatePattern());
564
565 case TemplateArgument::Expression:
566 return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
567 Arg2.getAsExpr());
568
569 case TemplateArgument::Pack:
570 if (Arg1.pack_size() != Arg2.pack_size())
571 return false;
572
573 for (unsigned I = 0, N = Arg1.pack_size(); I != N; ++I)
574 if (!IsStructurallyEquivalent(Context, Arg1.pack_begin()[I],
575 Arg2.pack_begin()[I]))
576 return false;
577
578 return true;
579 }
580
581 llvm_unreachable("Invalid template argument kind");
582 }
583
584 /// Determine structural equivalence for the common part of array
585 /// types.
IsArrayStructurallyEquivalent(StructuralEquivalenceContext & Context,const ArrayType * Array1,const ArrayType * Array2)586 static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
587 const ArrayType *Array1,
588 const ArrayType *Array2) {
589 if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
590 Array2->getElementType()))
591 return false;
592 if (Array1->getSizeModifier() != Array2->getSizeModifier())
593 return false;
594 if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
595 return false;
596
597 return true;
598 }
599
600 /// Determine structural equivalence based on the ExtInfo of functions. This
601 /// is inspired by ASTContext::mergeFunctionTypes(), we compare calling
602 /// conventions bits but must not compare some other bits.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FunctionType::ExtInfo EI1,FunctionType::ExtInfo EI2)603 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
604 FunctionType::ExtInfo EI1,
605 FunctionType::ExtInfo EI2) {
606 // Compatible functions must have compatible calling conventions.
607 if (EI1.getCC() != EI2.getCC())
608 return false;
609
610 // Regparm is part of the calling convention.
611 if (EI1.getHasRegParm() != EI2.getHasRegParm())
612 return false;
613 if (EI1.getRegParm() != EI2.getRegParm())
614 return false;
615
616 if (EI1.getProducesResult() != EI2.getProducesResult())
617 return false;
618 if (EI1.getNoCallerSavedRegs() != EI2.getNoCallerSavedRegs())
619 return false;
620 if (EI1.getNoCfCheck() != EI2.getNoCfCheck())
621 return false;
622
623 return true;
624 }
625
626 /// Check the equivalence of exception specifications.
IsEquivalentExceptionSpec(StructuralEquivalenceContext & Context,const FunctionProtoType * Proto1,const FunctionProtoType * Proto2)627 static bool IsEquivalentExceptionSpec(StructuralEquivalenceContext &Context,
628 const FunctionProtoType *Proto1,
629 const FunctionProtoType *Proto2) {
630
631 auto Spec1 = Proto1->getExceptionSpecType();
632 auto Spec2 = Proto2->getExceptionSpecType();
633
634 if (isUnresolvedExceptionSpec(Spec1) || isUnresolvedExceptionSpec(Spec2))
635 return true;
636
637 if (Spec1 != Spec2)
638 return false;
639 if (Spec1 == EST_Dynamic) {
640 if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
641 return false;
642 for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
643 if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
644 Proto2->getExceptionType(I)))
645 return false;
646 }
647 } else if (isComputedNoexcept(Spec1)) {
648 if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
649 Proto2->getNoexceptExpr()))
650 return false;
651 }
652
653 return true;
654 }
655
656 /// Determine structural equivalence of two types.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,QualType T1,QualType T2)657 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
658 QualType T1, QualType T2) {
659 if (T1.isNull() || T2.isNull())
660 return T1.isNull() && T2.isNull();
661
662 QualType OrigT1 = T1;
663 QualType OrigT2 = T2;
664
665 if (!Context.StrictTypeSpelling) {
666 // We aren't being strict about token-to-token equivalence of types,
667 // so map down to the canonical type.
668 T1 = Context.FromCtx.getCanonicalType(T1);
669 T2 = Context.ToCtx.getCanonicalType(T2);
670 }
671
672 if (T1.getQualifiers() != T2.getQualifiers())
673 return false;
674
675 Type::TypeClass TC = T1->getTypeClass();
676
677 if (T1->getTypeClass() != T2->getTypeClass()) {
678 // Compare function types with prototypes vs. without prototypes as if
679 // both did not have prototypes.
680 if (T1->getTypeClass() == Type::FunctionProto &&
681 T2->getTypeClass() == Type::FunctionNoProto)
682 TC = Type::FunctionNoProto;
683 else if (T1->getTypeClass() == Type::FunctionNoProto &&
684 T2->getTypeClass() == Type::FunctionProto)
685 TC = Type::FunctionNoProto;
686 else
687 return false;
688 }
689
690 switch (TC) {
691 case Type::Builtin:
692 // FIXME: Deal with Char_S/Char_U.
693 if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
694 return false;
695 break;
696
697 case Type::Complex:
698 if (!IsStructurallyEquivalent(Context,
699 cast<ComplexType>(T1)->getElementType(),
700 cast<ComplexType>(T2)->getElementType()))
701 return false;
702 break;
703
704 case Type::Adjusted:
705 case Type::Decayed:
706 if (!IsStructurallyEquivalent(Context,
707 cast<AdjustedType>(T1)->getOriginalType(),
708 cast<AdjustedType>(T2)->getOriginalType()))
709 return false;
710 break;
711
712 case Type::Pointer:
713 if (!IsStructurallyEquivalent(Context,
714 cast<PointerType>(T1)->getPointeeType(),
715 cast<PointerType>(T2)->getPointeeType()))
716 return false;
717 break;
718
719 case Type::BlockPointer:
720 if (!IsStructurallyEquivalent(Context,
721 cast<BlockPointerType>(T1)->getPointeeType(),
722 cast<BlockPointerType>(T2)->getPointeeType()))
723 return false;
724 break;
725
726 case Type::LValueReference:
727 case Type::RValueReference: {
728 const auto *Ref1 = cast<ReferenceType>(T1);
729 const auto *Ref2 = cast<ReferenceType>(T2);
730 if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
731 return false;
732 if (Ref1->isInnerRef() != Ref2->isInnerRef())
733 return false;
734 if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
735 Ref2->getPointeeTypeAsWritten()))
736 return false;
737 break;
738 }
739
740 case Type::MemberPointer: {
741 const auto *MemPtr1 = cast<MemberPointerType>(T1);
742 const auto *MemPtr2 = cast<MemberPointerType>(T2);
743 if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
744 MemPtr2->getPointeeType()))
745 return false;
746 if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
747 QualType(MemPtr2->getClass(), 0)))
748 return false;
749 break;
750 }
751
752 case Type::ConstantArray: {
753 const auto *Array1 = cast<ConstantArrayType>(T1);
754 const auto *Array2 = cast<ConstantArrayType>(T2);
755 if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
756 return false;
757
758 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
759 return false;
760 break;
761 }
762
763 case Type::IncompleteArray:
764 if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
765 cast<ArrayType>(T2)))
766 return false;
767 break;
768
769 case Type::VariableArray: {
770 const auto *Array1 = cast<VariableArrayType>(T1);
771 const auto *Array2 = cast<VariableArrayType>(T2);
772 if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
773 Array2->getSizeExpr()))
774 return false;
775
776 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
777 return false;
778
779 break;
780 }
781
782 case Type::DependentSizedArray: {
783 const auto *Array1 = cast<DependentSizedArrayType>(T1);
784 const auto *Array2 = cast<DependentSizedArrayType>(T2);
785 if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
786 Array2->getSizeExpr()))
787 return false;
788
789 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
790 return false;
791
792 break;
793 }
794
795 case Type::DependentAddressSpace: {
796 const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);
797 const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);
798 if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),
799 DepAddressSpace2->getAddrSpaceExpr()))
800 return false;
801 if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
802 DepAddressSpace2->getPointeeType()))
803 return false;
804
805 break;
806 }
807
808 case Type::DependentSizedExtVector: {
809 const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);
810 const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);
811 if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
812 Vec2->getSizeExpr()))
813 return false;
814 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
815 Vec2->getElementType()))
816 return false;
817 break;
818 }
819
820 case Type::DependentVector: {
821 const auto *Vec1 = cast<DependentVectorType>(T1);
822 const auto *Vec2 = cast<DependentVectorType>(T2);
823 if (Vec1->getVectorKind() != Vec2->getVectorKind())
824 return false;
825 if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
826 Vec2->getSizeExpr()))
827 return false;
828 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
829 Vec2->getElementType()))
830 return false;
831 break;
832 }
833
834 case Type::Vector:
835 case Type::ExtVector: {
836 const auto *Vec1 = cast<VectorType>(T1);
837 const auto *Vec2 = cast<VectorType>(T2);
838 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
839 Vec2->getElementType()))
840 return false;
841 if (Vec1->getNumElements() != Vec2->getNumElements())
842 return false;
843 if (Vec1->getVectorKind() != Vec2->getVectorKind())
844 return false;
845 break;
846 }
847
848 case Type::DependentSizedMatrix: {
849 const DependentSizedMatrixType *Mat1 = cast<DependentSizedMatrixType>(T1);
850 const DependentSizedMatrixType *Mat2 = cast<DependentSizedMatrixType>(T2);
851 // The element types, row and column expressions must be structurally
852 // equivalent.
853 if (!IsStructurallyEquivalent(Context, Mat1->getRowExpr(),
854 Mat2->getRowExpr()) ||
855 !IsStructurallyEquivalent(Context, Mat1->getColumnExpr(),
856 Mat2->getColumnExpr()) ||
857 !IsStructurallyEquivalent(Context, Mat1->getElementType(),
858 Mat2->getElementType()))
859 return false;
860 break;
861 }
862
863 case Type::ConstantMatrix: {
864 const ConstantMatrixType *Mat1 = cast<ConstantMatrixType>(T1);
865 const ConstantMatrixType *Mat2 = cast<ConstantMatrixType>(T2);
866 // The element types must be structurally equivalent and the number of rows
867 // and columns must match.
868 if (!IsStructurallyEquivalent(Context, Mat1->getElementType(),
869 Mat2->getElementType()) ||
870 Mat1->getNumRows() != Mat2->getNumRows() ||
871 Mat1->getNumColumns() != Mat2->getNumColumns())
872 return false;
873 break;
874 }
875
876 case Type::FunctionProto: {
877 const auto *Proto1 = cast<FunctionProtoType>(T1);
878 const auto *Proto2 = cast<FunctionProtoType>(T2);
879
880 if (Proto1->getNumParams() != Proto2->getNumParams())
881 return false;
882 for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
883 if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
884 Proto2->getParamType(I)))
885 return false;
886 }
887 if (Proto1->isVariadic() != Proto2->isVariadic())
888 return false;
889
890 if (Proto1->getMethodQuals() != Proto2->getMethodQuals())
891 return false;
892
893 // Check exceptions, this information is lost in canonical type.
894 const auto *OrigProto1 =
895 cast<FunctionProtoType>(OrigT1.getDesugaredType(Context.FromCtx));
896 const auto *OrigProto2 =
897 cast<FunctionProtoType>(OrigT2.getDesugaredType(Context.ToCtx));
898 if (!IsEquivalentExceptionSpec(Context, OrigProto1, OrigProto2))
899 return false;
900
901 // Fall through to check the bits common with FunctionNoProtoType.
902 LLVM_FALLTHROUGH;
903 }
904
905 case Type::FunctionNoProto: {
906 const auto *Function1 = cast<FunctionType>(T1);
907 const auto *Function2 = cast<FunctionType>(T2);
908 if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
909 Function2->getReturnType()))
910 return false;
911 if (!IsStructurallyEquivalent(Context, Function1->getExtInfo(),
912 Function2->getExtInfo()))
913 return false;
914 break;
915 }
916
917 case Type::UnresolvedUsing:
918 if (!IsStructurallyEquivalent(Context,
919 cast<UnresolvedUsingType>(T1)->getDecl(),
920 cast<UnresolvedUsingType>(T2)->getDecl()))
921 return false;
922 break;
923
924 case Type::Attributed:
925 if (!IsStructurallyEquivalent(Context,
926 cast<AttributedType>(T1)->getModifiedType(),
927 cast<AttributedType>(T2)->getModifiedType()))
928 return false;
929 if (!IsStructurallyEquivalent(
930 Context, cast<AttributedType>(T1)->getEquivalentType(),
931 cast<AttributedType>(T2)->getEquivalentType()))
932 return false;
933 break;
934
935 case Type::Paren:
936 if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
937 cast<ParenType>(T2)->getInnerType()))
938 return false;
939 break;
940
941 case Type::MacroQualified:
942 if (!IsStructurallyEquivalent(
943 Context, cast<MacroQualifiedType>(T1)->getUnderlyingType(),
944 cast<MacroQualifiedType>(T2)->getUnderlyingType()))
945 return false;
946 break;
947
948 case Type::Typedef:
949 if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
950 cast<TypedefType>(T2)->getDecl()))
951 return false;
952 break;
953
954 case Type::TypeOfExpr:
955 if (!IsStructurallyEquivalent(
956 Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
957 cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
958 return false;
959 break;
960
961 case Type::TypeOf:
962 if (!IsStructurallyEquivalent(Context,
963 cast<TypeOfType>(T1)->getUnderlyingType(),
964 cast<TypeOfType>(T2)->getUnderlyingType()))
965 return false;
966 break;
967
968 case Type::UnaryTransform:
969 if (!IsStructurallyEquivalent(
970 Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
971 cast<UnaryTransformType>(T2)->getUnderlyingType()))
972 return false;
973 break;
974
975 case Type::Decltype:
976 if (!IsStructurallyEquivalent(Context,
977 cast<DecltypeType>(T1)->getUnderlyingExpr(),
978 cast<DecltypeType>(T2)->getUnderlyingExpr()))
979 return false;
980 break;
981
982 case Type::Auto: {
983 auto *Auto1 = cast<AutoType>(T1);
984 auto *Auto2 = cast<AutoType>(T2);
985 if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),
986 Auto2->getDeducedType()))
987 return false;
988 if (Auto1->isConstrained() != Auto2->isConstrained())
989 return false;
990 if (Auto1->isConstrained()) {
991 if (Auto1->getTypeConstraintConcept() !=
992 Auto2->getTypeConstraintConcept())
993 return false;
994 ArrayRef<TemplateArgument> Auto1Args =
995 Auto1->getTypeConstraintArguments();
996 ArrayRef<TemplateArgument> Auto2Args =
997 Auto2->getTypeConstraintArguments();
998 if (Auto1Args.size() != Auto2Args.size())
999 return false;
1000 for (unsigned I = 0, N = Auto1Args.size(); I != N; ++I) {
1001 if (!IsStructurallyEquivalent(Context, Auto1Args[I], Auto2Args[I]))
1002 return false;
1003 }
1004 }
1005 break;
1006 }
1007
1008 case Type::DeducedTemplateSpecialization: {
1009 const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
1010 const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
1011 if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
1012 DT2->getTemplateName()))
1013 return false;
1014 if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
1015 DT2->getDeducedType()))
1016 return false;
1017 break;
1018 }
1019
1020 case Type::Record:
1021 case Type::Enum:
1022 if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
1023 cast<TagType>(T2)->getDecl()))
1024 return false;
1025 break;
1026
1027 case Type::TemplateTypeParm: {
1028 const auto *Parm1 = cast<TemplateTypeParmType>(T1);
1029 const auto *Parm2 = cast<TemplateTypeParmType>(T2);
1030 if (Parm1->getDepth() != Parm2->getDepth())
1031 return false;
1032 if (Parm1->getIndex() != Parm2->getIndex())
1033 return false;
1034 if (Parm1->isParameterPack() != Parm2->isParameterPack())
1035 return false;
1036
1037 // Names of template type parameters are never significant.
1038 break;
1039 }
1040
1041 case Type::SubstTemplateTypeParm: {
1042 const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
1043 const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
1044 if (!IsStructurallyEquivalent(Context,
1045 QualType(Subst1->getReplacedParameter(), 0),
1046 QualType(Subst2->getReplacedParameter(), 0)))
1047 return false;
1048 if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
1049 Subst2->getReplacementType()))
1050 return false;
1051 break;
1052 }
1053
1054 case Type::SubstTemplateTypeParmPack: {
1055 const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
1056 const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
1057 if (!IsStructurallyEquivalent(Context,
1058 QualType(Subst1->getReplacedParameter(), 0),
1059 QualType(Subst2->getReplacedParameter(), 0)))
1060 return false;
1061 if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
1062 Subst2->getArgumentPack()))
1063 return false;
1064 break;
1065 }
1066
1067 case Type::TemplateSpecialization: {
1068 const auto *Spec1 = cast<TemplateSpecializationType>(T1);
1069 const auto *Spec2 = cast<TemplateSpecializationType>(T2);
1070 if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
1071 Spec2->getTemplateName()))
1072 return false;
1073 if (Spec1->getNumArgs() != Spec2->getNumArgs())
1074 return false;
1075 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
1076 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
1077 Spec2->getArg(I)))
1078 return false;
1079 }
1080 break;
1081 }
1082
1083 case Type::Elaborated: {
1084 const auto *Elab1 = cast<ElaboratedType>(T1);
1085 const auto *Elab2 = cast<ElaboratedType>(T2);
1086 // CHECKME: what if a keyword is ETK_None or ETK_typename ?
1087 if (Elab1->getKeyword() != Elab2->getKeyword())
1088 return false;
1089 if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
1090 Elab2->getQualifier()))
1091 return false;
1092 if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
1093 Elab2->getNamedType()))
1094 return false;
1095 break;
1096 }
1097
1098 case Type::InjectedClassName: {
1099 const auto *Inj1 = cast<InjectedClassNameType>(T1);
1100 const auto *Inj2 = cast<InjectedClassNameType>(T2);
1101 if (!IsStructurallyEquivalent(Context,
1102 Inj1->getInjectedSpecializationType(),
1103 Inj2->getInjectedSpecializationType()))
1104 return false;
1105 break;
1106 }
1107
1108 case Type::DependentName: {
1109 const auto *Typename1 = cast<DependentNameType>(T1);
1110 const auto *Typename2 = cast<DependentNameType>(T2);
1111 if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
1112 Typename2->getQualifier()))
1113 return false;
1114 if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
1115 Typename2->getIdentifier()))
1116 return false;
1117
1118 break;
1119 }
1120
1121 case Type::DependentTemplateSpecialization: {
1122 const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
1123 const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
1124 if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
1125 Spec2->getQualifier()))
1126 return false;
1127 if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
1128 Spec2->getIdentifier()))
1129 return false;
1130 if (Spec1->getNumArgs() != Spec2->getNumArgs())
1131 return false;
1132 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
1133 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
1134 Spec2->getArg(I)))
1135 return false;
1136 }
1137 break;
1138 }
1139
1140 case Type::PackExpansion:
1141 if (!IsStructurallyEquivalent(Context,
1142 cast<PackExpansionType>(T1)->getPattern(),
1143 cast<PackExpansionType>(T2)->getPattern()))
1144 return false;
1145 break;
1146
1147 case Type::ObjCInterface: {
1148 const auto *Iface1 = cast<ObjCInterfaceType>(T1);
1149 const auto *Iface2 = cast<ObjCInterfaceType>(T2);
1150 if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
1151 Iface2->getDecl()))
1152 return false;
1153 break;
1154 }
1155
1156 case Type::ObjCTypeParam: {
1157 const auto *Obj1 = cast<ObjCTypeParamType>(T1);
1158 const auto *Obj2 = cast<ObjCTypeParamType>(T2);
1159 if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
1160 return false;
1161
1162 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
1163 return false;
1164 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
1165 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
1166 Obj2->getProtocol(I)))
1167 return false;
1168 }
1169 break;
1170 }
1171
1172 case Type::ObjCObject: {
1173 const auto *Obj1 = cast<ObjCObjectType>(T1);
1174 const auto *Obj2 = cast<ObjCObjectType>(T2);
1175 if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
1176 Obj2->getBaseType()))
1177 return false;
1178 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
1179 return false;
1180 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
1181 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
1182 Obj2->getProtocol(I)))
1183 return false;
1184 }
1185 break;
1186 }
1187
1188 case Type::ObjCObjectPointer: {
1189 const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
1190 const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
1191 if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
1192 Ptr2->getPointeeType()))
1193 return false;
1194 break;
1195 }
1196
1197 case Type::Atomic:
1198 if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
1199 cast<AtomicType>(T2)->getValueType()))
1200 return false;
1201 break;
1202
1203 case Type::Pipe:
1204 if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
1205 cast<PipeType>(T2)->getElementType()))
1206 return false;
1207 break;
1208 case Type::ExtInt: {
1209 const auto *Int1 = cast<ExtIntType>(T1);
1210 const auto *Int2 = cast<ExtIntType>(T2);
1211
1212 if (Int1->isUnsigned() != Int2->isUnsigned() ||
1213 Int1->getNumBits() != Int2->getNumBits())
1214 return false;
1215 break;
1216 }
1217 case Type::DependentExtInt: {
1218 const auto *Int1 = cast<DependentExtIntType>(T1);
1219 const auto *Int2 = cast<DependentExtIntType>(T2);
1220
1221 if (Int1->isUnsigned() != Int2->isUnsigned() ||
1222 !IsStructurallyEquivalent(Context, Int1->getNumBitsExpr(),
1223 Int2->getNumBitsExpr()))
1224 return false;
1225 }
1226 } // end switch
1227
1228 return true;
1229 }
1230
1231 /// Determine structural equivalence of two fields.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FieldDecl * Field1,FieldDecl * Field2)1232 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1233 FieldDecl *Field1, FieldDecl *Field2) {
1234 const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
1235
1236 // For anonymous structs/unions, match up the anonymous struct/union type
1237 // declarations directly, so that we don't go off searching for anonymous
1238 // types
1239 if (Field1->isAnonymousStructOrUnion() &&
1240 Field2->isAnonymousStructOrUnion()) {
1241 RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
1242 RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
1243 return IsStructurallyEquivalent(Context, D1, D2);
1244 }
1245
1246 // Check for equivalent field names.
1247 IdentifierInfo *Name1 = Field1->getIdentifier();
1248 IdentifierInfo *Name2 = Field2->getIdentifier();
1249 if (!::IsStructurallyEquivalent(Name1, Name2)) {
1250 if (Context.Complain) {
1251 Context.Diag2(
1252 Owner2->getLocation(),
1253 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1254 << Context.ToCtx.getTypeDeclType(Owner2);
1255 Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
1256 << Field2->getDeclName();
1257 Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
1258 << Field1->getDeclName();
1259 }
1260 return false;
1261 }
1262
1263 if (!IsStructurallyEquivalent(Context, Field1->getType(),
1264 Field2->getType())) {
1265 if (Context.Complain) {
1266 Context.Diag2(
1267 Owner2->getLocation(),
1268 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1269 << Context.ToCtx.getTypeDeclType(Owner2);
1270 Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1271 << Field2->getDeclName() << Field2->getType();
1272 Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1273 << Field1->getDeclName() << Field1->getType();
1274 }
1275 return false;
1276 }
1277
1278 if (Field1->isBitField())
1279 return IsStructurallyEquivalent(Context, Field1->getBitWidth(),
1280 Field2->getBitWidth());
1281
1282 return true;
1283 }
1284
1285 /// Determine structural equivalence of two methods.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,CXXMethodDecl * Method1,CXXMethodDecl * Method2)1286 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1287 CXXMethodDecl *Method1,
1288 CXXMethodDecl *Method2) {
1289 bool PropertiesEqual =
1290 Method1->getDeclKind() == Method2->getDeclKind() &&
1291 Method1->getRefQualifier() == Method2->getRefQualifier() &&
1292 Method1->getAccess() == Method2->getAccess() &&
1293 Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
1294 Method1->isStatic() == Method2->isStatic() &&
1295 Method1->isConst() == Method2->isConst() &&
1296 Method1->isVolatile() == Method2->isVolatile() &&
1297 Method1->isVirtual() == Method2->isVirtual() &&
1298 Method1->isPure() == Method2->isPure() &&
1299 Method1->isDefaulted() == Method2->isDefaulted() &&
1300 Method1->isDeleted() == Method2->isDeleted();
1301 if (!PropertiesEqual)
1302 return false;
1303 // FIXME: Check for 'final'.
1304
1305 if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
1306 auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
1307 if (!Constructor1->getExplicitSpecifier().isEquivalent(
1308 Constructor2->getExplicitSpecifier()))
1309 return false;
1310 }
1311
1312 if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
1313 auto *Conversion2 = cast<CXXConversionDecl>(Method2);
1314 if (!Conversion1->getExplicitSpecifier().isEquivalent(
1315 Conversion2->getExplicitSpecifier()))
1316 return false;
1317 if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
1318 Conversion2->getConversionType()))
1319 return false;
1320 }
1321
1322 const IdentifierInfo *Name1 = Method1->getIdentifier();
1323 const IdentifierInfo *Name2 = Method2->getIdentifier();
1324 if (!::IsStructurallyEquivalent(Name1, Name2)) {
1325 return false;
1326 // TODO: Names do not match, add warning like at check for FieldDecl.
1327 }
1328
1329 // Check the prototypes.
1330 if (!::IsStructurallyEquivalent(Context,
1331 Method1->getType(), Method2->getType()))
1332 return false;
1333
1334 return true;
1335 }
1336
1337 /// Determine structural equivalence of two lambda classes.
1338 static bool
IsStructurallyEquivalentLambdas(StructuralEquivalenceContext & Context,CXXRecordDecl * D1,CXXRecordDecl * D2)1339 IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
1340 CXXRecordDecl *D1, CXXRecordDecl *D2) {
1341 assert(D1->isLambda() && D2->isLambda() &&
1342 "Must be called on lambda classes");
1343 if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(),
1344 D2->getLambdaCallOperator()))
1345 return false;
1346
1347 return true;
1348 }
1349
1350 /// Determine structural equivalence of two records.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,RecordDecl * D1,RecordDecl * D2)1351 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1352 RecordDecl *D1, RecordDecl *D2) {
1353
1354 // Check for equivalent structure names.
1355 IdentifierInfo *Name1 = D1->getIdentifier();
1356 if (!Name1 && D1->getTypedefNameForAnonDecl())
1357 Name1 = D1->getTypedefNameForAnonDecl()->getIdentifier();
1358 IdentifierInfo *Name2 = D2->getIdentifier();
1359 if (!Name2 && D2->getTypedefNameForAnonDecl())
1360 Name2 = D2->getTypedefNameForAnonDecl()->getIdentifier();
1361 if (!IsStructurallyEquivalent(Name1, Name2))
1362 return false;
1363
1364 if (D1->isUnion() != D2->isUnion()) {
1365 if (Context.Complain) {
1366 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1367 diag::err_odr_tag_type_inconsistent))
1368 << Context.ToCtx.getTypeDeclType(D2);
1369 Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1370 << D1->getDeclName() << (unsigned)D1->getTagKind();
1371 }
1372 return false;
1373 }
1374
1375 if (!D1->getDeclName() && !D2->getDeclName()) {
1376 // If both anonymous structs/unions are in a record context, make sure
1377 // they occur in the same location in the context records.
1378 if (Optional<unsigned> Index1 =
1379 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
1380 if (Optional<unsigned> Index2 =
1381 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1382 D2)) {
1383 if (*Index1 != *Index2)
1384 return false;
1385 }
1386 }
1387 }
1388
1389 // If both declarations are class template specializations, we know
1390 // the ODR applies, so check the template and template arguments.
1391 const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
1392 const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
1393 if (Spec1 && Spec2) {
1394 // Check that the specialized templates are the same.
1395 if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1396 Spec2->getSpecializedTemplate()))
1397 return false;
1398
1399 // Check that the template arguments are the same.
1400 if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1401 return false;
1402
1403 for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1404 if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
1405 Spec2->getTemplateArgs().get(I)))
1406 return false;
1407 }
1408 // If one is a class template specialization and the other is not, these
1409 // structures are different.
1410 else if (Spec1 || Spec2)
1411 return false;
1412
1413 // Compare the definitions of these two records. If either or both are
1414 // incomplete (i.e. it is a forward decl), we assume that they are
1415 // equivalent.
1416 D1 = D1->getDefinition();
1417 D2 = D2->getDefinition();
1418 if (!D1 || !D2)
1419 return true;
1420
1421 // If any of the records has external storage and we do a minimal check (or
1422 // AST import) we assume they are equivalent. (If we didn't have this
1423 // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1424 // another AST import which in turn would call the structural equivalency
1425 // check again and finally we'd have an improper result.)
1426 if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1427 if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
1428 return true;
1429
1430 // If one definition is currently being defined, we do not compare for
1431 // equality and we assume that the decls are equal.
1432 if (D1->isBeingDefined() || D2->isBeingDefined())
1433 return true;
1434
1435 if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
1436 if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
1437 if (D1CXX->hasExternalLexicalStorage() &&
1438 !D1CXX->isCompleteDefinition()) {
1439 D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1440 }
1441
1442 if (D1CXX->isLambda() != D2CXX->isLambda())
1443 return false;
1444 if (D1CXX->isLambda()) {
1445 if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))
1446 return false;
1447 }
1448
1449 if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1450 if (Context.Complain) {
1451 Context.Diag2(D2->getLocation(),
1452 Context.getApplicableDiagnostic(
1453 diag::err_odr_tag_type_inconsistent))
1454 << Context.ToCtx.getTypeDeclType(D2);
1455 Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1456 << D2CXX->getNumBases();
1457 Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1458 << D1CXX->getNumBases();
1459 }
1460 return false;
1461 }
1462
1463 // Check the base classes.
1464 for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1465 BaseEnd1 = D1CXX->bases_end(),
1466 Base2 = D2CXX->bases_begin();
1467 Base1 != BaseEnd1; ++Base1, ++Base2) {
1468 if (!IsStructurallyEquivalent(Context, Base1->getType(),
1469 Base2->getType())) {
1470 if (Context.Complain) {
1471 Context.Diag2(D2->getLocation(),
1472 Context.getApplicableDiagnostic(
1473 diag::err_odr_tag_type_inconsistent))
1474 << Context.ToCtx.getTypeDeclType(D2);
1475 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1476 << Base2->getType() << Base2->getSourceRange();
1477 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1478 << Base1->getType() << Base1->getSourceRange();
1479 }
1480 return false;
1481 }
1482
1483 // Check virtual vs. non-virtual inheritance mismatch.
1484 if (Base1->isVirtual() != Base2->isVirtual()) {
1485 if (Context.Complain) {
1486 Context.Diag2(D2->getLocation(),
1487 Context.getApplicableDiagnostic(
1488 diag::err_odr_tag_type_inconsistent))
1489 << Context.ToCtx.getTypeDeclType(D2);
1490 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1491 << Base2->isVirtual() << Base2->getSourceRange();
1492 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1493 << Base1->isVirtual() << Base1->getSourceRange();
1494 }
1495 return false;
1496 }
1497 }
1498
1499 // Check the friends for consistency.
1500 CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1501 Friend2End = D2CXX->friend_end();
1502 for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1503 Friend1End = D1CXX->friend_end();
1504 Friend1 != Friend1End; ++Friend1, ++Friend2) {
1505 if (Friend2 == Friend2End) {
1506 if (Context.Complain) {
1507 Context.Diag2(D2->getLocation(),
1508 Context.getApplicableDiagnostic(
1509 diag::err_odr_tag_type_inconsistent))
1510 << Context.ToCtx.getTypeDeclType(D2CXX);
1511 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1512 Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1513 }
1514 return false;
1515 }
1516
1517 if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1518 if (Context.Complain) {
1519 Context.Diag2(D2->getLocation(),
1520 Context.getApplicableDiagnostic(
1521 diag::err_odr_tag_type_inconsistent))
1522 << Context.ToCtx.getTypeDeclType(D2CXX);
1523 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1524 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1525 }
1526 return false;
1527 }
1528 }
1529
1530 if (Friend2 != Friend2End) {
1531 if (Context.Complain) {
1532 Context.Diag2(D2->getLocation(),
1533 Context.getApplicableDiagnostic(
1534 diag::err_odr_tag_type_inconsistent))
1535 << Context.ToCtx.getTypeDeclType(D2);
1536 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1537 Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1538 }
1539 return false;
1540 }
1541 } else if (D1CXX->getNumBases() > 0) {
1542 if (Context.Complain) {
1543 Context.Diag2(D2->getLocation(),
1544 Context.getApplicableDiagnostic(
1545 diag::err_odr_tag_type_inconsistent))
1546 << Context.ToCtx.getTypeDeclType(D2);
1547 const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1548 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1549 << Base1->getType() << Base1->getSourceRange();
1550 Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1551 }
1552 return false;
1553 }
1554 }
1555
1556 // Check the fields for consistency.
1557 RecordDecl::field_iterator Field2 = D2->field_begin(),
1558 Field2End = D2->field_end();
1559 for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1560 Field1End = D1->field_end();
1561 Field1 != Field1End; ++Field1, ++Field2) {
1562 if (Field2 == Field2End) {
1563 if (Context.Complain) {
1564 Context.Diag2(D2->getLocation(),
1565 Context.getApplicableDiagnostic(
1566 diag::err_odr_tag_type_inconsistent))
1567 << Context.ToCtx.getTypeDeclType(D2);
1568 Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1569 << Field1->getDeclName() << Field1->getType();
1570 Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1571 }
1572 return false;
1573 }
1574
1575 if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1576 return false;
1577 }
1578
1579 if (Field2 != Field2End) {
1580 if (Context.Complain) {
1581 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1582 diag::err_odr_tag_type_inconsistent))
1583 << Context.ToCtx.getTypeDeclType(D2);
1584 Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1585 << Field2->getDeclName() << Field2->getType();
1586 Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1587 }
1588 return false;
1589 }
1590
1591 return true;
1592 }
1593
1594 /// Determine structural equivalence of two enums.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,EnumDecl * D1,EnumDecl * D2)1595 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1596 EnumDecl *D1, EnumDecl *D2) {
1597
1598 // Check for equivalent enum names.
1599 IdentifierInfo *Name1 = D1->getIdentifier();
1600 if (!Name1 && D1->getTypedefNameForAnonDecl())
1601 Name1 = D1->getTypedefNameForAnonDecl()->getIdentifier();
1602 IdentifierInfo *Name2 = D2->getIdentifier();
1603 if (!Name2 && D2->getTypedefNameForAnonDecl())
1604 Name2 = D2->getTypedefNameForAnonDecl()->getIdentifier();
1605 if (!IsStructurallyEquivalent(Name1, Name2))
1606 return false;
1607
1608 // Compare the definitions of these two enums. If either or both are
1609 // incomplete (i.e. forward declared), we assume that they are equivalent.
1610 D1 = D1->getDefinition();
1611 D2 = D2->getDefinition();
1612 if (!D1 || !D2)
1613 return true;
1614
1615 EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1616 EC2End = D2->enumerator_end();
1617 for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1618 EC1End = D1->enumerator_end();
1619 EC1 != EC1End; ++EC1, ++EC2) {
1620 if (EC2 == EC2End) {
1621 if (Context.Complain) {
1622 Context.Diag2(D2->getLocation(),
1623 Context.getApplicableDiagnostic(
1624 diag::err_odr_tag_type_inconsistent))
1625 << Context.ToCtx.getTypeDeclType(D2);
1626 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1627 << EC1->getDeclName() << toString(EC1->getInitVal(), 10);
1628 Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1629 }
1630 return false;
1631 }
1632
1633 llvm::APSInt Val1 = EC1->getInitVal();
1634 llvm::APSInt Val2 = EC2->getInitVal();
1635 if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1636 !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1637 if (Context.Complain) {
1638 Context.Diag2(D2->getLocation(),
1639 Context.getApplicableDiagnostic(
1640 diag::err_odr_tag_type_inconsistent))
1641 << Context.ToCtx.getTypeDeclType(D2);
1642 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1643 << EC2->getDeclName() << toString(EC2->getInitVal(), 10);
1644 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1645 << EC1->getDeclName() << toString(EC1->getInitVal(), 10);
1646 }
1647 return false;
1648 }
1649 }
1650
1651 if (EC2 != EC2End) {
1652 if (Context.Complain) {
1653 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1654 diag::err_odr_tag_type_inconsistent))
1655 << Context.ToCtx.getTypeDeclType(D2);
1656 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1657 << EC2->getDeclName() << toString(EC2->getInitVal(), 10);
1658 Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1659 }
1660 return false;
1661 }
1662
1663 return true;
1664 }
1665
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,TemplateParameterList * Params1,TemplateParameterList * Params2)1666 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1667 TemplateParameterList *Params1,
1668 TemplateParameterList *Params2) {
1669 if (Params1->size() != Params2->size()) {
1670 if (Context.Complain) {
1671 Context.Diag2(Params2->getTemplateLoc(),
1672 Context.getApplicableDiagnostic(
1673 diag::err_odr_different_num_template_parameters))
1674 << Params1->size() << Params2->size();
1675 Context.Diag1(Params1->getTemplateLoc(),
1676 diag::note_odr_template_parameter_list);
1677 }
1678 return false;
1679 }
1680
1681 for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1682 if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1683 if (Context.Complain) {
1684 Context.Diag2(Params2->getParam(I)->getLocation(),
1685 Context.getApplicableDiagnostic(
1686 diag::err_odr_different_template_parameter_kind));
1687 Context.Diag1(Params1->getParam(I)->getLocation(),
1688 diag::note_odr_template_parameter_here);
1689 }
1690 return false;
1691 }
1692
1693 if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1694 Params2->getParam(I)))
1695 return false;
1696 }
1697
1698 return true;
1699 }
1700
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,TemplateTypeParmDecl * D1,TemplateTypeParmDecl * D2)1701 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1702 TemplateTypeParmDecl *D1,
1703 TemplateTypeParmDecl *D2) {
1704 if (D1->isParameterPack() != D2->isParameterPack()) {
1705 if (Context.Complain) {
1706 Context.Diag2(D2->getLocation(),
1707 Context.getApplicableDiagnostic(
1708 diag::err_odr_parameter_pack_non_pack))
1709 << D2->isParameterPack();
1710 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1711 << D1->isParameterPack();
1712 }
1713 return false;
1714 }
1715
1716 return true;
1717 }
1718
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,NonTypeTemplateParmDecl * D1,NonTypeTemplateParmDecl * D2)1719 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1720 NonTypeTemplateParmDecl *D1,
1721 NonTypeTemplateParmDecl *D2) {
1722 if (D1->isParameterPack() != D2->isParameterPack()) {
1723 if (Context.Complain) {
1724 Context.Diag2(D2->getLocation(),
1725 Context.getApplicableDiagnostic(
1726 diag::err_odr_parameter_pack_non_pack))
1727 << D2->isParameterPack();
1728 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1729 << D1->isParameterPack();
1730 }
1731 return false;
1732 }
1733
1734 // Check types.
1735 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1736 if (Context.Complain) {
1737 Context.Diag2(D2->getLocation(),
1738 Context.getApplicableDiagnostic(
1739 diag::err_odr_non_type_parameter_type_inconsistent))
1740 << D2->getType() << D1->getType();
1741 Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1742 << D1->getType();
1743 }
1744 return false;
1745 }
1746
1747 return true;
1748 }
1749
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,TemplateTemplateParmDecl * D1,TemplateTemplateParmDecl * D2)1750 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1751 TemplateTemplateParmDecl *D1,
1752 TemplateTemplateParmDecl *D2) {
1753 if (D1->isParameterPack() != D2->isParameterPack()) {
1754 if (Context.Complain) {
1755 Context.Diag2(D2->getLocation(),
1756 Context.getApplicableDiagnostic(
1757 diag::err_odr_parameter_pack_non_pack))
1758 << D2->isParameterPack();
1759 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1760 << D1->isParameterPack();
1761 }
1762 return false;
1763 }
1764
1765 // Check template parameter lists.
1766 return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1767 D2->getTemplateParameters());
1768 }
1769
IsTemplateDeclCommonStructurallyEquivalent(StructuralEquivalenceContext & Ctx,TemplateDecl * D1,TemplateDecl * D2)1770 static bool IsTemplateDeclCommonStructurallyEquivalent(
1771 StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1772 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1773 return false;
1774 if (!D1->getIdentifier()) // Special name
1775 if (D1->getNameAsString() != D2->getNameAsString())
1776 return false;
1777 return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1778 D2->getTemplateParameters());
1779 }
1780
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,ClassTemplateDecl * D1,ClassTemplateDecl * D2)1781 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1782 ClassTemplateDecl *D1,
1783 ClassTemplateDecl *D2) {
1784 // Check template parameters.
1785 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1786 return false;
1787
1788 // Check the templated declaration.
1789 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1790 D2->getTemplatedDecl());
1791 }
1792
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FunctionTemplateDecl * D1,FunctionTemplateDecl * D2)1793 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1794 FunctionTemplateDecl *D1,
1795 FunctionTemplateDecl *D2) {
1796 // Check template parameters.
1797 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1798 return false;
1799
1800 // Check the templated declaration.
1801 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1802 D2->getTemplatedDecl()->getType());
1803 }
1804
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,ConceptDecl * D1,ConceptDecl * D2)1805 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1806 ConceptDecl *D1,
1807 ConceptDecl *D2) {
1808 // Check template parameters.
1809 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1810 return false;
1811
1812 // Check the constraint expression.
1813 return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),
1814 D2->getConstraintExpr());
1815 }
1816
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FriendDecl * D1,FriendDecl * D2)1817 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1818 FriendDecl *D1, FriendDecl *D2) {
1819 if ((D1->getFriendType() && D2->getFriendDecl()) ||
1820 (D1->getFriendDecl() && D2->getFriendType())) {
1821 return false;
1822 }
1823 if (D1->getFriendType() && D2->getFriendType())
1824 return IsStructurallyEquivalent(Context,
1825 D1->getFriendType()->getType(),
1826 D2->getFriendType()->getType());
1827 if (D1->getFriendDecl() && D2->getFriendDecl())
1828 return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1829 D2->getFriendDecl());
1830 return false;
1831 }
1832
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,TypedefNameDecl * D1,TypedefNameDecl * D2)1833 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1834 TypedefNameDecl *D1, TypedefNameDecl *D2) {
1835 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1836 return false;
1837
1838 return IsStructurallyEquivalent(Context, D1->getUnderlyingType(),
1839 D2->getUnderlyingType());
1840 }
1841
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FunctionDecl * D1,FunctionDecl * D2)1842 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1843 FunctionDecl *D1, FunctionDecl *D2) {
1844 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1845 return false;
1846
1847 if (D1->isOverloadedOperator()) {
1848 if (!D2->isOverloadedOperator())
1849 return false;
1850 if (D1->getOverloadedOperator() != D2->getOverloadedOperator())
1851 return false;
1852 }
1853
1854 // FIXME: Consider checking for function attributes as well.
1855 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1856 return false;
1857
1858 return true;
1859 }
1860
1861 /// Determine structural equivalence of two declarations.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,Decl * D1,Decl * D2)1862 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1863 Decl *D1, Decl *D2) {
1864 // FIXME: Check for known structural equivalences via a callback of some sort.
1865
1866 D1 = D1->getCanonicalDecl();
1867 D2 = D2->getCanonicalDecl();
1868 std::pair<Decl *, Decl *> P{D1, D2};
1869
1870 // Check whether we already know that these two declarations are not
1871 // structurally equivalent.
1872 if (Context.NonEquivalentDecls.count(P))
1873 return false;
1874
1875 // Check if a check for these declarations is already pending.
1876 // If yes D1 and D2 will be checked later (from DeclsToCheck),
1877 // or these are already checked (and equivalent).
1878 bool Inserted = Context.VisitedDecls.insert(P).second;
1879 if (!Inserted)
1880 return true;
1881
1882 Context.DeclsToCheck.push(P);
1883
1884 return true;
1885 }
1886
Diag1(SourceLocation Loc,unsigned DiagID)1887 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1888 unsigned DiagID) {
1889 assert(Complain && "Not allowed to complain");
1890 if (LastDiagFromC2)
1891 FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1892 LastDiagFromC2 = false;
1893 return FromCtx.getDiagnostics().Report(Loc, DiagID);
1894 }
1895
Diag2(SourceLocation Loc,unsigned DiagID)1896 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1897 unsigned DiagID) {
1898 assert(Complain && "Not allowed to complain");
1899 if (!LastDiagFromC2)
1900 ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1901 LastDiagFromC2 = true;
1902 return ToCtx.getDiagnostics().Report(Loc, DiagID);
1903 }
1904
1905 Optional<unsigned>
findUntaggedStructOrUnionIndex(RecordDecl * Anon)1906 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1907 ASTContext &Context = Anon->getASTContext();
1908 QualType AnonTy = Context.getRecordType(Anon);
1909
1910 const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1911 if (!Owner)
1912 return None;
1913
1914 unsigned Index = 0;
1915 for (const auto *D : Owner->noload_decls()) {
1916 const auto *F = dyn_cast<FieldDecl>(D);
1917 if (!F)
1918 continue;
1919
1920 if (F->isAnonymousStructOrUnion()) {
1921 if (Context.hasSameType(F->getType(), AnonTy))
1922 break;
1923 ++Index;
1924 continue;
1925 }
1926
1927 // If the field looks like this:
1928 // struct { ... } A;
1929 QualType FieldType = F->getType();
1930 // In case of nested structs.
1931 while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1932 FieldType = ElabType->getNamedType();
1933
1934 if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1935 const RecordDecl *RecDecl = RecType->getDecl();
1936 if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1937 if (Context.hasSameType(FieldType, AnonTy))
1938 break;
1939 ++Index;
1940 continue;
1941 }
1942 }
1943 }
1944
1945 return Index;
1946 }
1947
getApplicableDiagnostic(unsigned ErrorDiagnostic)1948 unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
1949 unsigned ErrorDiagnostic) {
1950 if (ErrorOnTagTypeMismatch)
1951 return ErrorDiagnostic;
1952
1953 switch (ErrorDiagnostic) {
1954 case diag::err_odr_variable_type_inconsistent:
1955 return diag::warn_odr_variable_type_inconsistent;
1956 case diag::err_odr_variable_multiple_def:
1957 return diag::warn_odr_variable_multiple_def;
1958 case diag::err_odr_function_type_inconsistent:
1959 return diag::warn_odr_function_type_inconsistent;
1960 case diag::err_odr_tag_type_inconsistent:
1961 return diag::warn_odr_tag_type_inconsistent;
1962 case diag::err_odr_field_type_inconsistent:
1963 return diag::warn_odr_field_type_inconsistent;
1964 case diag::err_odr_ivar_type_inconsistent:
1965 return diag::warn_odr_ivar_type_inconsistent;
1966 case diag::err_odr_objc_superclass_inconsistent:
1967 return diag::warn_odr_objc_superclass_inconsistent;
1968 case diag::err_odr_objc_method_result_type_inconsistent:
1969 return diag::warn_odr_objc_method_result_type_inconsistent;
1970 case diag::err_odr_objc_method_num_params_inconsistent:
1971 return diag::warn_odr_objc_method_num_params_inconsistent;
1972 case diag::err_odr_objc_method_param_type_inconsistent:
1973 return diag::warn_odr_objc_method_param_type_inconsistent;
1974 case diag::err_odr_objc_method_variadic_inconsistent:
1975 return diag::warn_odr_objc_method_variadic_inconsistent;
1976 case diag::err_odr_objc_property_type_inconsistent:
1977 return diag::warn_odr_objc_property_type_inconsistent;
1978 case diag::err_odr_objc_property_impl_kind_inconsistent:
1979 return diag::warn_odr_objc_property_impl_kind_inconsistent;
1980 case diag::err_odr_objc_synthesize_ivar_inconsistent:
1981 return diag::warn_odr_objc_synthesize_ivar_inconsistent;
1982 case diag::err_odr_different_num_template_parameters:
1983 return diag::warn_odr_different_num_template_parameters;
1984 case diag::err_odr_different_template_parameter_kind:
1985 return diag::warn_odr_different_template_parameter_kind;
1986 case diag::err_odr_parameter_pack_non_pack:
1987 return diag::warn_odr_parameter_pack_non_pack;
1988 case diag::err_odr_non_type_parameter_type_inconsistent:
1989 return diag::warn_odr_non_type_parameter_type_inconsistent;
1990 }
1991 llvm_unreachable("Diagnostic kind not handled in preceding switch");
1992 }
1993
IsEquivalent(Decl * D1,Decl * D2)1994 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
1995
1996 // Ensure that the implementation functions (all static functions in this TU)
1997 // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
1998 // because that will wreak havoc the internal state (DeclsToCheck and
1999 // VisitedDecls members) and can cause faulty behaviour.
2000 // In other words: Do not start a graph search from a new node with the
2001 // internal data of another search in progress.
2002 // FIXME: Better encapsulation and separation of internal and public
2003 // functionality.
2004 assert(DeclsToCheck.empty());
2005 assert(VisitedDecls.empty());
2006
2007 if (!::IsStructurallyEquivalent(*this, D1, D2))
2008 return false;
2009
2010 return !Finish();
2011 }
2012
IsEquivalent(QualType T1,QualType T2)2013 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
2014 assert(DeclsToCheck.empty());
2015 assert(VisitedDecls.empty());
2016 if (!::IsStructurallyEquivalent(*this, T1, T2))
2017 return false;
2018
2019 return !Finish();
2020 }
2021
IsEquivalent(Stmt * S1,Stmt * S2)2022 bool StructuralEquivalenceContext::IsEquivalent(Stmt *S1, Stmt *S2) {
2023 assert(DeclsToCheck.empty());
2024 assert(VisitedDecls.empty());
2025 if (!::IsStructurallyEquivalent(*this, S1, S2))
2026 return false;
2027
2028 return !Finish();
2029 }
2030
CheckCommonEquivalence(Decl * D1,Decl * D2)2031 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
2032 // Check for equivalent described template.
2033 TemplateDecl *Template1 = D1->getDescribedTemplate();
2034 TemplateDecl *Template2 = D2->getDescribedTemplate();
2035 if ((Template1 != nullptr) != (Template2 != nullptr))
2036 return false;
2037 if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
2038 return false;
2039
2040 // FIXME: Move check for identifier names into this function.
2041
2042 return true;
2043 }
2044
CheckKindSpecificEquivalence(Decl * D1,Decl * D2)2045 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
2046 Decl *D1, Decl *D2) {
2047
2048 // Kind mismatch.
2049 if (D1->getKind() != D2->getKind())
2050 return false;
2051
2052 // Cast the Decls to their actual subclass so that the right overload of
2053 // IsStructurallyEquivalent is called.
2054 switch (D1->getKind()) {
2055 #define ABSTRACT_DECL(DECL)
2056 #define DECL(DERIVED, BASE) \
2057 case Decl::Kind::DERIVED: \
2058 return ::IsStructurallyEquivalent(*this, static_cast<DERIVED##Decl *>(D1), \
2059 static_cast<DERIVED##Decl *>(D2));
2060 #include "clang/AST/DeclNodes.inc"
2061 }
2062 return true;
2063 }
2064
Finish()2065 bool StructuralEquivalenceContext::Finish() {
2066 while (!DeclsToCheck.empty()) {
2067 // Check the next declaration.
2068 std::pair<Decl *, Decl *> P = DeclsToCheck.front();
2069 DeclsToCheck.pop();
2070
2071 Decl *D1 = P.first;
2072 Decl *D2 = P.second;
2073
2074 bool Equivalent =
2075 CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
2076
2077 if (!Equivalent) {
2078 // Note that these two declarations are not equivalent (and we already
2079 // know about it).
2080 NonEquivalentDecls.insert(P);
2081
2082 return true;
2083 }
2084 }
2085
2086 return false;
2087 }
2088