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

Provided by KDAB

Privacy Policy
Update your C++ knowledge – Modern C++11/14/17 Training
Find out more

source code of clang/lib/AST/ASTStructuralEquivalence.cpp