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