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