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