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

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