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 if (!IsStructurallyEquivalent(Context,
844 T1: cast<AdjustedType>(Val&: T1)->getOriginalType(),
845 T2: cast<AdjustedType>(Val&: T2)->getOriginalType()))
846 return false;
847 break;
848
849 case Type::Pointer:
850 if (!IsStructurallyEquivalent(Context,
851 T1: cast<PointerType>(Val&: T1)->getPointeeType(),
852 T2: cast<PointerType>(Val&: T2)->getPointeeType()))
853 return false;
854 break;
855
856 case Type::BlockPointer:
857 if (!IsStructurallyEquivalent(Context,
858 T1: cast<BlockPointerType>(Val&: T1)->getPointeeType(),
859 T2: cast<BlockPointerType>(Val&: T2)->getPointeeType()))
860 return false;
861 break;
862
863 case Type::LValueReference:
864 case Type::RValueReference: {
865 const auto *Ref1 = cast<ReferenceType>(Val&: T1);
866 const auto *Ref2 = cast<ReferenceType>(Val&: T2);
867 if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
868 return false;
869 if (Ref1->isInnerRef() != Ref2->isInnerRef())
870 return false;
871 if (!IsStructurallyEquivalent(Context, T1: Ref1->getPointeeTypeAsWritten(),
872 T2: Ref2->getPointeeTypeAsWritten()))
873 return false;
874 break;
875 }
876
877 case Type::MemberPointer: {
878 const auto *MemPtr1 = cast<MemberPointerType>(Val&: T1);
879 const auto *MemPtr2 = cast<MemberPointerType>(Val&: T2);
880 if (!IsStructurallyEquivalent(Context, T1: MemPtr1->getPointeeType(),
881 T2: MemPtr2->getPointeeType()))
882 return false;
883 if (!IsStructurallyEquivalent(Context, T1: QualType(MemPtr1->getClass(), 0),
884 T2: QualType(MemPtr2->getClass(), 0)))
885 return false;
886 break;
887 }
888
889 case Type::ConstantArray: {
890 const auto *Array1 = cast<ConstantArrayType>(Val&: T1);
891 const auto *Array2 = cast<ConstantArrayType>(Val&: T2);
892 if (!llvm::APInt::isSameValue(I1: Array1->getSize(), I2: Array2->getSize()))
893 return false;
894
895 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
896 return false;
897 break;
898 }
899
900 case Type::IncompleteArray:
901 if (!IsArrayStructurallyEquivalent(Context, Array1: cast<ArrayType>(Val&: T1),
902 Array2: cast<ArrayType>(Val&: T2)))
903 return false;
904 break;
905
906 case Type::VariableArray: {
907 const auto *Array1 = cast<VariableArrayType>(Val&: T1);
908 const auto *Array2 = cast<VariableArrayType>(Val&: T2);
909 if (!IsStructurallyEquivalent(Context, Arg1: Array1->getSizeExpr(),
910 Arg2: Array2->getSizeExpr()))
911 return false;
912
913 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
914 return false;
915
916 break;
917 }
918
919 case Type::DependentSizedArray: {
920 const auto *Array1 = cast<DependentSizedArrayType>(Val&: T1);
921 const auto *Array2 = cast<DependentSizedArrayType>(Val&: T2);
922 if (!IsStructurallyEquivalent(Context, Arg1: Array1->getSizeExpr(),
923 Arg2: Array2->getSizeExpr()))
924 return false;
925
926 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
927 return false;
928
929 break;
930 }
931
932 case Type::DependentAddressSpace: {
933 const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(Val&: T1);
934 const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(Val&: T2);
935 if (!IsStructurallyEquivalent(Context, Arg1: DepAddressSpace1->getAddrSpaceExpr(),
936 Arg2: DepAddressSpace2->getAddrSpaceExpr()))
937 return false;
938 if (!IsStructurallyEquivalent(Context, T1: DepAddressSpace1->getPointeeType(),
939 T2: DepAddressSpace2->getPointeeType()))
940 return false;
941
942 break;
943 }
944
945 case Type::DependentSizedExtVector: {
946 const auto *Vec1 = cast<DependentSizedExtVectorType>(Val&: T1);
947 const auto *Vec2 = cast<DependentSizedExtVectorType>(Val&: T2);
948 if (!IsStructurallyEquivalent(Context, Arg1: Vec1->getSizeExpr(),
949 Arg2: Vec2->getSizeExpr()))
950 return false;
951 if (!IsStructurallyEquivalent(Context, T1: Vec1->getElementType(),
952 T2: Vec2->getElementType()))
953 return false;
954 break;
955 }
956
957 case Type::DependentVector: {
958 const auto *Vec1 = cast<DependentVectorType>(Val&: T1);
959 const auto *Vec2 = cast<DependentVectorType>(Val&: T2);
960 if (Vec1->getVectorKind() != Vec2->getVectorKind())
961 return false;
962 if (!IsStructurallyEquivalent(Context, Arg1: Vec1->getSizeExpr(),
963 Arg2: Vec2->getSizeExpr()))
964 return false;
965 if (!IsStructurallyEquivalent(Context, T1: Vec1->getElementType(),
966 T2: Vec2->getElementType()))
967 return false;
968 break;
969 }
970
971 case Type::Vector:
972 case Type::ExtVector: {
973 const auto *Vec1 = cast<VectorType>(Val&: T1);
974 const auto *Vec2 = cast<VectorType>(Val&: T2);
975 if (!IsStructurallyEquivalent(Context, T1: Vec1->getElementType(),
976 T2: Vec2->getElementType()))
977 return false;
978 if (Vec1->getNumElements() != Vec2->getNumElements())
979 return false;
980 if (Vec1->getVectorKind() != Vec2->getVectorKind())
981 return false;
982 break;
983 }
984
985 case Type::DependentSizedMatrix: {
986 const DependentSizedMatrixType *Mat1 = cast<DependentSizedMatrixType>(Val&: T1);
987 const DependentSizedMatrixType *Mat2 = cast<DependentSizedMatrixType>(Val&: T2);
988 // The element types, row and column expressions must be structurally
989 // equivalent.
990 if (!IsStructurallyEquivalent(Context, Arg1: Mat1->getRowExpr(),
991 Arg2: Mat2->getRowExpr()) ||
992 !IsStructurallyEquivalent(Context, Arg1: Mat1->getColumnExpr(),
993 Arg2: Mat2->getColumnExpr()) ||
994 !IsStructurallyEquivalent(Context, Mat1->getElementType(),
995 Mat2->getElementType()))
996 return false;
997 break;
998 }
999
1000 case Type::ConstantMatrix: {
1001 const ConstantMatrixType *Mat1 = cast<ConstantMatrixType>(Val&: T1);
1002 const ConstantMatrixType *Mat2 = cast<ConstantMatrixType>(Val&: T2);
1003 // The element types must be structurally equivalent and the number of rows
1004 // and columns must match.
1005 if (!IsStructurallyEquivalent(Context, Mat1->getElementType(),
1006 Mat2->getElementType()) ||
1007 Mat1->getNumRows() != Mat2->getNumRows() ||
1008 Mat1->getNumColumns() != Mat2->getNumColumns())
1009 return false;
1010 break;
1011 }
1012
1013 case Type::FunctionProto: {
1014 const auto *Proto1 = cast<FunctionProtoType>(Val&: T1);
1015 const auto *Proto2 = cast<FunctionProtoType>(Val&: T2);
1016
1017 if (Proto1->getNumParams() != Proto2->getNumParams())
1018 return false;
1019 for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
1020 if (!IsStructurallyEquivalent(Context, T1: Proto1->getParamType(i: I),
1021 T2: Proto2->getParamType(i: I)))
1022 return false;
1023 }
1024 if (Proto1->isVariadic() != Proto2->isVariadic())
1025 return false;
1026
1027 if (Proto1->getMethodQuals() != Proto2->getMethodQuals())
1028 return false;
1029
1030 // Check exceptions, this information is lost in canonical type.
1031 const auto *OrigProto1 =
1032 cast<FunctionProtoType>(Val: OrigT1.getDesugaredType(Context: Context.FromCtx));
1033 const auto *OrigProto2 =
1034 cast<FunctionProtoType>(Val: OrigT2.getDesugaredType(Context: Context.ToCtx));
1035 if (!IsEquivalentExceptionSpec(Context, Proto1: OrigProto1, Proto2: OrigProto2))
1036 return false;
1037
1038 // Fall through to check the bits common with FunctionNoProtoType.
1039 [[fallthrough]];
1040 }
1041
1042 case Type::FunctionNoProto: {
1043 const auto *Function1 = cast<FunctionType>(Val&: T1);
1044 const auto *Function2 = cast<FunctionType>(Val&: T2);
1045 if (!IsStructurallyEquivalent(Context, T1: Function1->getReturnType(),
1046 T2: Function2->getReturnType()))
1047 return false;
1048 if (!IsStructurallyEquivalent(Context, EI1: Function1->getExtInfo(),
1049 EI2: Function2->getExtInfo()))
1050 return false;
1051 break;
1052 }
1053
1054 case Type::UnresolvedUsing:
1055 if (!IsStructurallyEquivalent(Context,
1056 cast<UnresolvedUsingType>(Val&: T1)->getDecl(),
1057 cast<UnresolvedUsingType>(Val&: T2)->getDecl()))
1058 return false;
1059 break;
1060
1061 case Type::Attributed:
1062 if (!IsStructurallyEquivalent(Context,
1063 T1: cast<AttributedType>(Val&: T1)->getModifiedType(),
1064 T2: cast<AttributedType>(Val&: T2)->getModifiedType()))
1065 return false;
1066 if (!IsStructurallyEquivalent(
1067 Context, T1: cast<AttributedType>(Val&: T1)->getEquivalentType(),
1068 T2: cast<AttributedType>(Val&: T2)->getEquivalentType()))
1069 return false;
1070 break;
1071
1072 case Type::BTFTagAttributed:
1073 if (!IsStructurallyEquivalent(
1074 Context, T1: cast<BTFTagAttributedType>(Val&: T1)->getWrappedType(),
1075 T2: cast<BTFTagAttributedType>(Val&: T2)->getWrappedType()))
1076 return false;
1077 break;
1078
1079 case Type::Paren:
1080 if (!IsStructurallyEquivalent(Context, T1: cast<ParenType>(Val&: T1)->getInnerType(),
1081 T2: cast<ParenType>(Val&: T2)->getInnerType()))
1082 return false;
1083 break;
1084
1085 case Type::MacroQualified:
1086 if (!IsStructurallyEquivalent(
1087 Context, T1: cast<MacroQualifiedType>(Val&: T1)->getUnderlyingType(),
1088 T2: cast<MacroQualifiedType>(Val&: T2)->getUnderlyingType()))
1089 return false;
1090 break;
1091
1092 case Type::Using:
1093 if (!IsStructurallyEquivalent(Context, cast<UsingType>(Val&: T1)->getFoundDecl(),
1094 cast<UsingType>(Val&: T2)->getFoundDecl()))
1095 return false;
1096 if (!IsStructurallyEquivalent(Context,
1097 T1: cast<UsingType>(Val&: T1)->getUnderlyingType(),
1098 T2: cast<UsingType>(Val&: T2)->getUnderlyingType()))
1099 return false;
1100 break;
1101
1102 case Type::Typedef:
1103 if (!IsStructurallyEquivalent(Context, cast<TypedefType>(Val&: T1)->getDecl(),
1104 cast<TypedefType>(Val&: T2)->getDecl()) ||
1105 !IsStructurallyEquivalent(Context, T1: cast<TypedefType>(Val&: T1)->desugar(),
1106 T2: cast<TypedefType>(Val&: T2)->desugar()))
1107 return false;
1108 break;
1109
1110 case Type::TypeOfExpr:
1111 if (!IsStructurallyEquivalent(
1112 Context, Arg1: cast<TypeOfExprType>(Val&: T1)->getUnderlyingExpr(),
1113 Arg2: cast<TypeOfExprType>(Val&: T2)->getUnderlyingExpr()))
1114 return false;
1115 break;
1116
1117 case Type::TypeOf:
1118 if (!IsStructurallyEquivalent(Context,
1119 T1: cast<TypeOfType>(Val&: T1)->getUnmodifiedType(),
1120 T2: cast<TypeOfType>(Val&: T2)->getUnmodifiedType()))
1121 return false;
1122 break;
1123
1124 case Type::UnaryTransform:
1125 if (!IsStructurallyEquivalent(
1126 Context, T1: cast<UnaryTransformType>(Val&: T1)->getUnderlyingType(),
1127 T2: cast<UnaryTransformType>(Val&: T2)->getUnderlyingType()))
1128 return false;
1129 break;
1130
1131 case Type::Decltype:
1132 if (!IsStructurallyEquivalent(Context,
1133 Arg1: cast<DecltypeType>(Val&: T1)->getUnderlyingExpr(),
1134 Arg2: cast<DecltypeType>(Val&: T2)->getUnderlyingExpr()))
1135 return false;
1136 break;
1137
1138 case Type::Auto: {
1139 auto *Auto1 = cast<AutoType>(Val&: T1);
1140 auto *Auto2 = cast<AutoType>(Val&: T2);
1141 if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),
1142 Auto2->getDeducedType()))
1143 return false;
1144 if (Auto1->isConstrained() != Auto2->isConstrained())
1145 return false;
1146 if (Auto1->isConstrained()) {
1147 if (Auto1->getTypeConstraintConcept() !=
1148 Auto2->getTypeConstraintConcept())
1149 return false;
1150 if (!IsStructurallyEquivalent(Context,
1151 Args1: Auto1->getTypeConstraintArguments(),
1152 Args2: Auto2->getTypeConstraintArguments()))
1153 return false;
1154 }
1155 break;
1156 }
1157
1158 case Type::DeducedTemplateSpecialization: {
1159 const auto *DT1 = cast<DeducedTemplateSpecializationType>(Val&: T1);
1160 const auto *DT2 = cast<DeducedTemplateSpecializationType>(Val&: T2);
1161 if (!IsStructurallyEquivalent(Context, N1: DT1->getTemplateName(),
1162 N2: DT2->getTemplateName()))
1163 return false;
1164 if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
1165 DT2->getDeducedType()))
1166 return false;
1167 break;
1168 }
1169
1170 case Type::Record:
1171 case Type::Enum:
1172 if (!IsStructurallyEquivalent(Context, cast<TagType>(Val&: T1)->getDecl(),
1173 cast<TagType>(Val&: T2)->getDecl()))
1174 return false;
1175 break;
1176
1177 case Type::TemplateTypeParm: {
1178 const auto *Parm1 = cast<TemplateTypeParmType>(Val&: T1);
1179 const auto *Parm2 = cast<TemplateTypeParmType>(Val&: T2);
1180 if (!Context.IgnoreTemplateParmDepth &&
1181 Parm1->getDepth() != Parm2->getDepth())
1182 return false;
1183 if (Parm1->getIndex() != Parm2->getIndex())
1184 return false;
1185 if (Parm1->isParameterPack() != Parm2->isParameterPack())
1186 return false;
1187
1188 // Names of template type parameters are never significant.
1189 break;
1190 }
1191
1192 case Type::SubstTemplateTypeParm: {
1193 const auto *Subst1 = cast<SubstTemplateTypeParmType>(Val&: T1);
1194 const auto *Subst2 = cast<SubstTemplateTypeParmType>(Val&: T2);
1195 if (!IsStructurallyEquivalent(Context, T1: Subst1->getReplacementType(),
1196 T2: Subst2->getReplacementType()))
1197 return false;
1198 if (!IsStructurallyEquivalent(Context, D1: Subst1->getAssociatedDecl(),
1199 D2: Subst2->getAssociatedDecl()))
1200 return false;
1201 if (Subst1->getIndex() != Subst2->getIndex())
1202 return false;
1203 if (Subst1->getPackIndex() != Subst2->getPackIndex())
1204 return false;
1205 break;
1206 }
1207
1208 case Type::SubstTemplateTypeParmPack: {
1209 const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(Val&: T1);
1210 const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(Val&: T2);
1211 if (!IsStructurallyEquivalent(Context, D1: Subst1->getAssociatedDecl(),
1212 D2: Subst2->getAssociatedDecl()))
1213 return false;
1214 if (Subst1->getIndex() != Subst2->getIndex())
1215 return false;
1216 if (!IsStructurallyEquivalent(Context, Arg1: Subst1->getArgumentPack(),
1217 Arg2: Subst2->getArgumentPack()))
1218 return false;
1219 break;
1220 }
1221
1222 case Type::TemplateSpecialization: {
1223 const auto *Spec1 = cast<TemplateSpecializationType>(Val&: T1);
1224 const auto *Spec2 = cast<TemplateSpecializationType>(Val&: T2);
1225 if (!IsStructurallyEquivalent(Context, N1: Spec1->getTemplateName(),
1226 N2: Spec2->getTemplateName()))
1227 return false;
1228 if (!IsStructurallyEquivalent(Context, Args1: Spec1->template_arguments(),
1229 Args2: Spec2->template_arguments()))
1230 return false;
1231 break;
1232 }
1233
1234 case Type::Elaborated: {
1235 const auto *Elab1 = cast<ElaboratedType>(Val&: T1);
1236 const auto *Elab2 = cast<ElaboratedType>(Val&: T2);
1237 // CHECKME: what if a keyword is ElaboratedTypeKeyword::None or
1238 // ElaboratedTypeKeyword::Typename
1239 // ?
1240 if (Elab1->getKeyword() != Elab2->getKeyword())
1241 return false;
1242 if (!IsStructurallyEquivalent(Context, NNS1: Elab1->getQualifier(),
1243 NNS2: Elab2->getQualifier()))
1244 return false;
1245 if (!IsStructurallyEquivalent(Context, T1: Elab1->getNamedType(),
1246 T2: Elab2->getNamedType()))
1247 return false;
1248 break;
1249 }
1250
1251 case Type::InjectedClassName: {
1252 const auto *Inj1 = cast<InjectedClassNameType>(Val&: T1);
1253 const auto *Inj2 = cast<InjectedClassNameType>(Val&: T2);
1254 if (!IsStructurallyEquivalent(Context,
1255 T1: Inj1->getInjectedSpecializationType(),
1256 T2: Inj2->getInjectedSpecializationType()))
1257 return false;
1258 break;
1259 }
1260
1261 case Type::DependentName: {
1262 const auto *Typename1 = cast<DependentNameType>(Val&: T1);
1263 const auto *Typename2 = cast<DependentNameType>(Val&: T2);
1264 if (!IsStructurallyEquivalent(Context, NNS1: Typename1->getQualifier(),
1265 NNS2: Typename2->getQualifier()))
1266 return false;
1267 if (!IsStructurallyEquivalent(Name1: Typename1->getIdentifier(),
1268 Name2: Typename2->getIdentifier()))
1269 return false;
1270
1271 break;
1272 }
1273
1274 case Type::DependentTemplateSpecialization: {
1275 const auto *Spec1 = cast<DependentTemplateSpecializationType>(Val&: T1);
1276 const auto *Spec2 = cast<DependentTemplateSpecializationType>(Val&: T2);
1277 if (!IsStructurallyEquivalent(Context, NNS1: Spec1->getQualifier(),
1278 NNS2: Spec2->getQualifier()))
1279 return false;
1280 if (!IsStructurallyEquivalent(Name1: Spec1->getIdentifier(),
1281 Name2: Spec2->getIdentifier()))
1282 return false;
1283 if (!IsStructurallyEquivalent(Context, Args1: Spec1->template_arguments(),
1284 Args2: Spec2->template_arguments()))
1285 return false;
1286 break;
1287 }
1288
1289 case Type::PackExpansion:
1290 if (!IsStructurallyEquivalent(Context,
1291 T1: cast<PackExpansionType>(Val&: T1)->getPattern(),
1292 T2: cast<PackExpansionType>(Val&: T2)->getPattern()))
1293 return false;
1294 break;
1295
1296 case Type::PackIndexing:
1297 if (!IsStructurallyEquivalent(Context,
1298 T1: cast<PackIndexingType>(Val&: T1)->getPattern(),
1299 T2: cast<PackIndexingType>(Val&: T2)->getPattern()))
1300 if (!IsStructurallyEquivalent(Context,
1301 Arg1: cast<PackIndexingType>(Val&: T1)->getIndexExpr(),
1302 Arg2: cast<PackIndexingType>(Val&: T2)->getIndexExpr()))
1303 return false;
1304 break;
1305
1306 case Type::ObjCInterface: {
1307 const auto *Iface1 = cast<ObjCInterfaceType>(Val&: T1);
1308 const auto *Iface2 = cast<ObjCInterfaceType>(Val&: T2);
1309 if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
1310 Iface2->getDecl()))
1311 return false;
1312 break;
1313 }
1314
1315 case Type::ObjCTypeParam: {
1316 const auto *Obj1 = cast<ObjCTypeParamType>(Val&: T1);
1317 const auto *Obj2 = cast<ObjCTypeParamType>(Val&: T2);
1318 if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
1319 return false;
1320
1321 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
1322 return false;
1323 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
1324 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
1325 Obj2->getProtocol(I)))
1326 return false;
1327 }
1328 break;
1329 }
1330
1331 case Type::ObjCObject: {
1332 const auto *Obj1 = cast<ObjCObjectType>(Val&: T1);
1333 const auto *Obj2 = cast<ObjCObjectType>(Val&: T2);
1334 if (!IsStructurallyEquivalent(Context, T1: Obj1->getBaseType(),
1335 T2: Obj2->getBaseType()))
1336 return false;
1337 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
1338 return false;
1339 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
1340 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
1341 Obj2->getProtocol(I)))
1342 return false;
1343 }
1344 break;
1345 }
1346
1347 case Type::ObjCObjectPointer: {
1348 const auto *Ptr1 = cast<ObjCObjectPointerType>(Val&: T1);
1349 const auto *Ptr2 = cast<ObjCObjectPointerType>(Val&: T2);
1350 if (!IsStructurallyEquivalent(Context, T1: Ptr1->getPointeeType(),
1351 T2: Ptr2->getPointeeType()))
1352 return false;
1353 break;
1354 }
1355
1356 case Type::Atomic:
1357 if (!IsStructurallyEquivalent(Context, T1: cast<AtomicType>(Val&: T1)->getValueType(),
1358 T2: cast<AtomicType>(Val&: T2)->getValueType()))
1359 return false;
1360 break;
1361
1362 case Type::Pipe:
1363 if (!IsStructurallyEquivalent(Context, T1: cast<PipeType>(Val&: T1)->getElementType(),
1364 T2: cast<PipeType>(Val&: T2)->getElementType()))
1365 return false;
1366 break;
1367 case Type::BitInt: {
1368 const auto *Int1 = cast<BitIntType>(Val&: T1);
1369 const auto *Int2 = cast<BitIntType>(Val&: T2);
1370
1371 if (Int1->isUnsigned() != Int2->isUnsigned() ||
1372 Int1->getNumBits() != Int2->getNumBits())
1373 return false;
1374 break;
1375 }
1376 case Type::DependentBitInt: {
1377 const auto *Int1 = cast<DependentBitIntType>(Val&: T1);
1378 const auto *Int2 = cast<DependentBitIntType>(Val&: T2);
1379
1380 if (Int1->isUnsigned() != Int2->isUnsigned() ||
1381 !IsStructurallyEquivalent(Context, Arg1: Int1->getNumBitsExpr(),
1382 Arg2: Int2->getNumBitsExpr()))
1383 return false;
1384 break;
1385 }
1386 } // end switch
1387
1388 return true;
1389}
1390
1391static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1392 VarDecl *D1, VarDecl *D2) {
1393 IdentifierInfo *Name1 = D1->getIdentifier();
1394 IdentifierInfo *Name2 = D2->getIdentifier();
1395 if (!::IsStructurallyEquivalent(Name1, Name2))
1396 return false;
1397
1398 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1399 return false;
1400
1401 // Compare storage class and initializer only if none or both are a
1402 // definition. Like a forward-declaration matches a class definition, variable
1403 // declarations that are not definitions should match with the definitions.
1404 if (D1->isThisDeclarationADefinition() != D2->isThisDeclarationADefinition())
1405 return true;
1406
1407 if (D1->getStorageClass() != D2->getStorageClass())
1408 return false;
1409
1410 return IsStructurallyEquivalent(Context, Arg1: D1->getInit(), Arg2: D2->getInit());
1411}
1412
1413static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1414 FieldDecl *Field1, FieldDecl *Field2,
1415 QualType Owner2Type) {
1416 const auto *Owner2 = cast<Decl>(Field2->getDeclContext());
1417
1418 // For anonymous structs/unions, match up the anonymous struct/union type
1419 // declarations directly, so that we don't go off searching for anonymous
1420 // types
1421 if (Field1->isAnonymousStructOrUnion() &&
1422 Field2->isAnonymousStructOrUnion()) {
1423 RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
1424 RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
1425 return IsStructurallyEquivalent(Context, D1, D2);
1426 }
1427
1428 // Check for equivalent field names.
1429 IdentifierInfo *Name1 = Field1->getIdentifier();
1430 IdentifierInfo *Name2 = Field2->getIdentifier();
1431 if (!::IsStructurallyEquivalent(Name1, Name2)) {
1432 if (Context.Complain) {
1433 Context.Diag2(
1434 Owner2->getLocation(),
1435 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1436 << Owner2Type;
1437 Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
1438 << Field2->getDeclName();
1439 Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
1440 << Field1->getDeclName();
1441 }
1442 return false;
1443 }
1444
1445 if (!IsStructurallyEquivalent(Context, Field1->getType(),
1446 Field2->getType())) {
1447 if (Context.Complain) {
1448 Context.Diag2(
1449 Owner2->getLocation(),
1450 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1451 << Owner2Type;
1452 Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1453 << Field2->getDeclName() << Field2->getType();
1454 Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1455 << Field1->getDeclName() << Field1->getType();
1456 }
1457 return false;
1458 }
1459
1460 if (Field1->isBitField())
1461 return IsStructurallyEquivalent(Context, Arg1: Field1->getBitWidth(),
1462 Arg2: Field2->getBitWidth());
1463
1464 return true;
1465}
1466
1467/// Determine structural equivalence of two fields.
1468static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1469 FieldDecl *Field1, FieldDecl *Field2) {
1470 const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
1471 return IsStructurallyEquivalent(Context, Field1, Field2,
1472 Context.ToCtx.getTypeDeclType(Decl: Owner2));
1473}
1474
1475/// Determine structural equivalence of two methods.
1476static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1477 CXXMethodDecl *Method1,
1478 CXXMethodDecl *Method2) {
1479 bool PropertiesEqual =
1480 Method1->getDeclKind() == Method2->getDeclKind() &&
1481 Method1->getRefQualifier() == Method2->getRefQualifier() &&
1482 Method1->getAccess() == Method2->getAccess() &&
1483 Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
1484 Method1->isStatic() == Method2->isStatic() &&
1485 Method1->isImplicitObjectMemberFunction() ==
1486 Method2->isImplicitObjectMemberFunction() &&
1487 Method1->isConst() == Method2->isConst() &&
1488 Method1->isVolatile() == Method2->isVolatile() &&
1489 Method1->isVirtual() == Method2->isVirtual() &&
1490 Method1->isPureVirtual() == Method2->isPureVirtual() &&
1491 Method1->isDefaulted() == Method2->isDefaulted() &&
1492 Method1->isDeleted() == Method2->isDeleted();
1493 if (!PropertiesEqual)
1494 return false;
1495 // FIXME: Check for 'final'.
1496
1497 if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Val: Method1)) {
1498 auto *Constructor2 = cast<CXXConstructorDecl>(Val: Method2);
1499 if (!Constructor1->getExplicitSpecifier().isEquivalent(
1500 Other: Constructor2->getExplicitSpecifier()))
1501 return false;
1502 }
1503
1504 if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Val: Method1)) {
1505 auto *Conversion2 = cast<CXXConversionDecl>(Val: Method2);
1506 if (!Conversion1->getExplicitSpecifier().isEquivalent(
1507 Other: Conversion2->getExplicitSpecifier()))
1508 return false;
1509 if (!IsStructurallyEquivalent(Context, T1: Conversion1->getConversionType(),
1510 T2: Conversion2->getConversionType()))
1511 return false;
1512 }
1513
1514 const IdentifierInfo *Name1 = Method1->getIdentifier();
1515 const IdentifierInfo *Name2 = Method2->getIdentifier();
1516 if (!::IsStructurallyEquivalent(Name1, Name2)) {
1517 return false;
1518 // TODO: Names do not match, add warning like at check for FieldDecl.
1519 }
1520
1521 // Check the prototypes.
1522 if (!::IsStructurallyEquivalent(Context,
1523 Method1->getType(), Method2->getType()))
1524 return false;
1525
1526 return true;
1527}
1528
1529/// Determine structural equivalence of two lambda classes.
1530static bool
1531IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
1532 CXXRecordDecl *D1, CXXRecordDecl *D2) {
1533 assert(D1->isLambda() && D2->isLambda() &&
1534 "Must be called on lambda classes");
1535 if (!IsStructurallyEquivalent(Context, Method1: D1->getLambdaCallOperator(),
1536 Method2: D2->getLambdaCallOperator()))
1537 return false;
1538
1539 return true;
1540}
1541
1542/// Determine if context of a class is equivalent.
1543static bool
1544IsRecordContextStructurallyEquivalent(StructuralEquivalenceContext &Context,
1545 RecordDecl *D1, RecordDecl *D2) {
1546 // The context should be completely equal, including anonymous and inline
1547 // namespaces.
1548 // We compare objects as part of full translation units, not subtrees of
1549 // translation units.
1550 DeclContext *DC1 = D1->getDeclContext()->getNonTransparentContext();
1551 DeclContext *DC2 = D2->getDeclContext()->getNonTransparentContext();
1552 while (true) {
1553 // Special case: We allow a struct defined in a function to be equivalent
1554 // with a similar struct defined outside of a function.
1555 if ((DC1->isFunctionOrMethod() && DC2->isTranslationUnit()) ||
1556 (DC2->isFunctionOrMethod() && DC1->isTranslationUnit()))
1557 return true;
1558
1559 if (DC1->getDeclKind() != DC2->getDeclKind())
1560 return false;
1561 if (DC1->isTranslationUnit())
1562 break;
1563 if (DC1->isInlineNamespace() != DC2->isInlineNamespace())
1564 return false;
1565 if (const auto *ND1 = dyn_cast<NamedDecl>(DC1)) {
1566 const auto *ND2 = cast<NamedDecl>(Val: DC2);
1567 if (!DC1->isInlineNamespace() &&
1568 !IsStructurallyEquivalent(ND1->getIdentifier(), ND2->getIdentifier()))
1569 return false;
1570 }
1571
1572 if (auto *D1Spec = dyn_cast<ClassTemplateSpecializationDecl>(DC1)) {
1573 auto *D2Spec = dyn_cast<ClassTemplateSpecializationDecl>(Val: DC2);
1574 if (!IsStructurallyEquivalent(Context, D1Spec, D2Spec))
1575 return false;
1576 }
1577
1578 DC1 = DC1->getParent()->getNonTransparentContext();
1579 DC2 = DC2->getParent()->getNonTransparentContext();
1580 }
1581
1582 return true;
1583}
1584
1585static bool NameIsStructurallyEquivalent(const TagDecl &D1, const TagDecl &D2) {
1586 auto GetName = [](const TagDecl &D) -> const IdentifierInfo * {
1587 if (const IdentifierInfo *Name = D.getIdentifier())
1588 return Name;
1589 if (const TypedefNameDecl *TypedefName = D.getTypedefNameForAnonDecl())
1590 return TypedefName->getIdentifier();
1591 return nullptr;
1592 };
1593 return IsStructurallyEquivalent(Name1: GetName(D1), Name2: GetName(D2));
1594}
1595
1596/// Determine structural equivalence of two records.
1597static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1598 RecordDecl *D1, RecordDecl *D2) {
1599 if (!NameIsStructurallyEquivalent(*D1, *D2)) {
1600 return false;
1601 }
1602
1603 if (D1->isUnion() != D2->isUnion()) {
1604 if (Context.Complain) {
1605 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1606 diag::err_odr_tag_type_inconsistent))
1607 << Context.ToCtx.getTypeDeclType(D2);
1608 Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1609 << D1->getDeclName() << (unsigned)D1->getTagKind();
1610 }
1611 return false;
1612 }
1613
1614 if (!D1->getDeclName() && !D2->getDeclName()) {
1615 // If both anonymous structs/unions are in a record context, make sure
1616 // they occur in the same location in the context records.
1617 if (std::optional<unsigned> Index1 =
1618 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(Anon: D1)) {
1619 if (std::optional<unsigned> Index2 =
1620 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1621 Anon: D2)) {
1622 if (*Index1 != *Index2)
1623 return false;
1624 }
1625 }
1626 }
1627
1628 // If the records occur in different context (namespace), these should be
1629 // different. This is specially important if the definition of one or both
1630 // records is missing.
1631 if (!IsRecordContextStructurallyEquivalent(Context, D1, D2))
1632 return false;
1633
1634 // If both declarations are class template specializations, we know
1635 // the ODR applies, so check the template and template arguments.
1636 const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(Val: D1);
1637 const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(Val: D2);
1638 if (Spec1 && Spec2) {
1639 // Check that the specialized templates are the same.
1640 if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1641 Spec2->getSpecializedTemplate()))
1642 return false;
1643
1644 // Check that the template arguments are the same.
1645 if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1646 return false;
1647
1648 for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1649 if (!IsStructurallyEquivalent(Context, Arg1: Spec1->getTemplateArgs().get(Idx: I),
1650 Arg2: Spec2->getTemplateArgs().get(Idx: I)))
1651 return false;
1652 }
1653 // If one is a class template specialization and the other is not, these
1654 // structures are different.
1655 else if (Spec1 || Spec2)
1656 return false;
1657
1658 // Compare the definitions of these two records. If either or both are
1659 // incomplete (i.e. it is a forward decl), we assume that they are
1660 // equivalent.
1661 D1 = D1->getDefinition();
1662 D2 = D2->getDefinition();
1663 if (!D1 || !D2)
1664 return true;
1665
1666 // If any of the records has external storage and we do a minimal check (or
1667 // AST import) we assume they are equivalent. (If we didn't have this
1668 // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1669 // another AST import which in turn would call the structural equivalency
1670 // check again and finally we'd have an improper result.)
1671 if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1672 if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
1673 return true;
1674
1675 // If one definition is currently being defined, we do not compare for
1676 // equality and we assume that the decls are equal.
1677 if (D1->isBeingDefined() || D2->isBeingDefined())
1678 return true;
1679
1680 if (auto *D1CXX = dyn_cast<CXXRecordDecl>(Val: D1)) {
1681 if (auto *D2CXX = dyn_cast<CXXRecordDecl>(Val: D2)) {
1682 if (D1CXX->hasExternalLexicalStorage() &&
1683 !D1CXX->isCompleteDefinition()) {
1684 D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1685 }
1686
1687 if (D1CXX->isLambda() != D2CXX->isLambda())
1688 return false;
1689 if (D1CXX->isLambda()) {
1690 if (!IsStructurallyEquivalentLambdas(Context, D1: D1CXX, D2: D2CXX))
1691 return false;
1692 }
1693
1694 if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1695 if (Context.Complain) {
1696 Context.Diag2(D2->getLocation(),
1697 Context.getApplicableDiagnostic(
1698 diag::err_odr_tag_type_inconsistent))
1699 << Context.ToCtx.getTypeDeclType(D2);
1700 Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1701 << D2CXX->getNumBases();
1702 Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1703 << D1CXX->getNumBases();
1704 }
1705 return false;
1706 }
1707
1708 // Check the base classes.
1709 for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1710 BaseEnd1 = D1CXX->bases_end(),
1711 Base2 = D2CXX->bases_begin();
1712 Base1 != BaseEnd1; ++Base1, ++Base2) {
1713 if (!IsStructurallyEquivalent(Context, T1: Base1->getType(),
1714 T2: Base2->getType())) {
1715 if (Context.Complain) {
1716 Context.Diag2(D2->getLocation(),
1717 Context.getApplicableDiagnostic(
1718 diag::err_odr_tag_type_inconsistent))
1719 << Context.ToCtx.getTypeDeclType(D2);
1720 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1721 << Base2->getType() << Base2->getSourceRange();
1722 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1723 << Base1->getType() << Base1->getSourceRange();
1724 }
1725 return false;
1726 }
1727
1728 // Check virtual vs. non-virtual inheritance mismatch.
1729 if (Base1->isVirtual() != Base2->isVirtual()) {
1730 if (Context.Complain) {
1731 Context.Diag2(D2->getLocation(),
1732 Context.getApplicableDiagnostic(
1733 diag::err_odr_tag_type_inconsistent))
1734 << Context.ToCtx.getTypeDeclType(D2);
1735 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1736 << Base2->isVirtual() << Base2->getSourceRange();
1737 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1738 << Base1->isVirtual() << Base1->getSourceRange();
1739 }
1740 return false;
1741 }
1742 }
1743
1744 // Check the friends for consistency.
1745 CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1746 Friend2End = D2CXX->friend_end();
1747 for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1748 Friend1End = D1CXX->friend_end();
1749 Friend1 != Friend1End; ++Friend1, ++Friend2) {
1750 if (Friend2 == Friend2End) {
1751 if (Context.Complain) {
1752 Context.Diag2(D2->getLocation(),
1753 Context.getApplicableDiagnostic(
1754 diag::err_odr_tag_type_inconsistent))
1755 << Context.ToCtx.getTypeDeclType(D2CXX);
1756 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1757 Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1758 }
1759 return false;
1760 }
1761
1762 if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1763 if (Context.Complain) {
1764 Context.Diag2(D2->getLocation(),
1765 Context.getApplicableDiagnostic(
1766 diag::err_odr_tag_type_inconsistent))
1767 << Context.ToCtx.getTypeDeclType(D2CXX);
1768 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1769 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1770 }
1771 return false;
1772 }
1773 }
1774
1775 if (Friend2 != Friend2End) {
1776 if (Context.Complain) {
1777 Context.Diag2(D2->getLocation(),
1778 Context.getApplicableDiagnostic(
1779 diag::err_odr_tag_type_inconsistent))
1780 << Context.ToCtx.getTypeDeclType(D2);
1781 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1782 Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1783 }
1784 return false;
1785 }
1786 } else if (D1CXX->getNumBases() > 0) {
1787 if (Context.Complain) {
1788 Context.Diag2(D2->getLocation(),
1789 Context.getApplicableDiagnostic(
1790 diag::err_odr_tag_type_inconsistent))
1791 << Context.ToCtx.getTypeDeclType(D2);
1792 const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1793 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1794 << Base1->getType() << Base1->getSourceRange();
1795 Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1796 }
1797 return false;
1798 }
1799 }
1800
1801 // Check the fields for consistency.
1802 QualType D2Type = Context.ToCtx.getTypeDeclType(D2);
1803 RecordDecl::field_iterator Field2 = D2->field_begin(),
1804 Field2End = D2->field_end();
1805 for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1806 Field1End = D1->field_end();
1807 Field1 != Field1End; ++Field1, ++Field2) {
1808 if (Field2 == Field2End) {
1809 if (Context.Complain) {
1810 Context.Diag2(D2->getLocation(),
1811 Context.getApplicableDiagnostic(
1812 diag::err_odr_tag_type_inconsistent))
1813 << Context.ToCtx.getTypeDeclType(D2);
1814 Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1815 << Field1->getDeclName() << Field1->getType();
1816 Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1817 }
1818 return false;
1819 }
1820
1821 if (!IsStructurallyEquivalent(Context, Field1: *Field1, Field2: *Field2, Owner2Type: D2Type))
1822 return false;
1823 }
1824
1825 if (Field2 != Field2End) {
1826 if (Context.Complain) {
1827 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1828 diag::err_odr_tag_type_inconsistent))
1829 << Context.ToCtx.getTypeDeclType(D2);
1830 Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1831 << Field2->getDeclName() << Field2->getType();
1832 Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1833 }
1834 return false;
1835 }
1836
1837 return true;
1838}
1839
1840static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1841 EnumConstantDecl *D1,
1842 EnumConstantDecl *D2) {
1843 const llvm::APSInt &FromVal = D1->getInitVal();
1844 const llvm::APSInt &ToVal = D2->getInitVal();
1845 if (FromVal.isSigned() != ToVal.isSigned())
1846 return false;
1847 if (FromVal.getBitWidth() != ToVal.getBitWidth())
1848 return false;
1849 if (FromVal != ToVal)
1850 return false;
1851
1852 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1853 return false;
1854
1855 // Init expressions are the most expensive check, so do them last.
1856 return IsStructurallyEquivalent(Context, Arg1: D1->getInitExpr(),
1857 Arg2: D2->getInitExpr());
1858}
1859
1860/// Determine structural equivalence of two enums.
1861static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1862 EnumDecl *D1, EnumDecl *D2) {
1863 if (!NameIsStructurallyEquivalent(*D1, *D2)) {
1864 return false;
1865 }
1866
1867 // Compare the definitions of these two enums. If either or both are
1868 // incomplete (i.e. forward declared), we assume that they are equivalent.
1869 D1 = D1->getDefinition();
1870 D2 = D2->getDefinition();
1871 if (!D1 || !D2)
1872 return true;
1873
1874 EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1875 EC2End = D2->enumerator_end();
1876 for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1877 EC1End = D1->enumerator_end();
1878 EC1 != EC1End; ++EC1, ++EC2) {
1879 if (EC2 == EC2End) {
1880 if (Context.Complain) {
1881 Context.Diag2(D2->getLocation(),
1882 Context.getApplicableDiagnostic(
1883 diag::err_odr_tag_type_inconsistent))
1884 << Context.ToCtx.getTypeDeclType(D2);
1885 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1886 << EC1->getDeclName() << toString(EC1->getInitVal(), 10);
1887 Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1888 }
1889 return false;
1890 }
1891
1892 llvm::APSInt Val1 = EC1->getInitVal();
1893 llvm::APSInt Val2 = EC2->getInitVal();
1894 if (!llvm::APSInt::isSameValue(I1: Val1, I2: Val2) ||
1895 !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1896 if (Context.Complain) {
1897 Context.Diag2(D2->getLocation(),
1898 Context.getApplicableDiagnostic(
1899 diag::err_odr_tag_type_inconsistent))
1900 << Context.ToCtx.getTypeDeclType(D2);
1901 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1902 << EC2->getDeclName() << toString(EC2->getInitVal(), 10);
1903 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1904 << EC1->getDeclName() << toString(EC1->getInitVal(), 10);
1905 }
1906 return false;
1907 }
1908 }
1909
1910 if (EC2 != EC2End) {
1911 if (Context.Complain) {
1912 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1913 diag::err_odr_tag_type_inconsistent))
1914 << Context.ToCtx.getTypeDeclType(D2);
1915 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1916 << EC2->getDeclName() << toString(EC2->getInitVal(), 10);
1917 Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1918 }
1919 return false;
1920 }
1921
1922 return true;
1923}
1924
1925static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1926 TemplateParameterList *Params1,
1927 TemplateParameterList *Params2) {
1928 if (Params1->size() != Params2->size()) {
1929 if (Context.Complain) {
1930 Context.Diag2(Params2->getTemplateLoc(),
1931 Context.getApplicableDiagnostic(
1932 diag::err_odr_different_num_template_parameters))
1933 << Params1->size() << Params2->size();
1934 Context.Diag1(Params1->getTemplateLoc(),
1935 diag::note_odr_template_parameter_list);
1936 }
1937 return false;
1938 }
1939
1940 for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1941 if (Params1->getParam(Idx: I)->getKind() != Params2->getParam(Idx: I)->getKind()) {
1942 if (Context.Complain) {
1943 Context.Diag2(Params2->getParam(I)->getLocation(),
1944 Context.getApplicableDiagnostic(
1945 diag::err_odr_different_template_parameter_kind));
1946 Context.Diag1(Params1->getParam(I)->getLocation(),
1947 diag::note_odr_template_parameter_here);
1948 }
1949 return false;
1950 }
1951
1952 if (!IsStructurallyEquivalent(Context, Params1->getParam(Idx: I),
1953 Params2->getParam(Idx: I)))
1954 return false;
1955 }
1956
1957 return true;
1958}
1959
1960static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1961 TemplateTypeParmDecl *D1,
1962 TemplateTypeParmDecl *D2) {
1963 if (D1->isParameterPack() != D2->isParameterPack()) {
1964 if (Context.Complain) {
1965 Context.Diag2(D2->getLocation(),
1966 Context.getApplicableDiagnostic(
1967 diag::err_odr_parameter_pack_non_pack))
1968 << D2->isParameterPack();
1969 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1970 << D1->isParameterPack();
1971 }
1972 return false;
1973 }
1974
1975 return true;
1976}
1977
1978static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1979 NonTypeTemplateParmDecl *D1,
1980 NonTypeTemplateParmDecl *D2) {
1981 if (D1->isParameterPack() != D2->isParameterPack()) {
1982 if (Context.Complain) {
1983 Context.Diag2(D2->getLocation(),
1984 Context.getApplicableDiagnostic(
1985 diag::err_odr_parameter_pack_non_pack))
1986 << D2->isParameterPack();
1987 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1988 << D1->isParameterPack();
1989 }
1990 return false;
1991 }
1992
1993 // Check types.
1994 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1995 if (Context.Complain) {
1996 Context.Diag2(D2->getLocation(),
1997 Context.getApplicableDiagnostic(
1998 diag::err_odr_non_type_parameter_type_inconsistent))
1999 << D2->getType() << D1->getType();
2000 Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
2001 << D1->getType();
2002 }
2003 return false;
2004 }
2005
2006 return true;
2007}
2008
2009static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2010 TemplateTemplateParmDecl *D1,
2011 TemplateTemplateParmDecl *D2) {
2012 if (D1->isParameterPack() != D2->isParameterPack()) {
2013 if (Context.Complain) {
2014 Context.Diag2(D2->getLocation(),
2015 Context.getApplicableDiagnostic(
2016 diag::err_odr_parameter_pack_non_pack))
2017 << D2->isParameterPack();
2018 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
2019 << D1->isParameterPack();
2020 }
2021 return false;
2022 }
2023
2024 // Check template parameter lists.
2025 return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
2026 D2->getTemplateParameters());
2027}
2028
2029static bool IsTemplateDeclCommonStructurallyEquivalent(
2030 StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
2031 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
2032 return false;
2033 if (!D1->getIdentifier()) // Special name
2034 if (D1->getNameAsString() != D2->getNameAsString())
2035 return false;
2036 return IsStructurallyEquivalent(Context&: Ctx, Params1: D1->getTemplateParameters(),
2037 Params2: D2->getTemplateParameters());
2038}
2039
2040static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2041 ClassTemplateDecl *D1,
2042 ClassTemplateDecl *D2) {
2043 // Check template parameters.
2044 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
2045 return false;
2046
2047 // Check the templated declaration.
2048 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
2049 D2->getTemplatedDecl());
2050}
2051
2052static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2053 FunctionTemplateDecl *D1,
2054 FunctionTemplateDecl *D2) {
2055 // Check template parameters.
2056 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
2057 return false;
2058
2059 // Check the templated declaration.
2060 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
2061 D2->getTemplatedDecl()->getType());
2062}
2063
2064static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2065 TypeAliasTemplateDecl *D1,
2066 TypeAliasTemplateDecl *D2) {
2067 // Check template parameters.
2068 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
2069 return false;
2070
2071 // Check the templated declaration.
2072 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
2073 D2->getTemplatedDecl());
2074}
2075
2076static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2077 ConceptDecl *D1,
2078 ConceptDecl *D2) {
2079 // Check template parameters.
2080 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
2081 return false;
2082
2083 // Check the constraint expression.
2084 return IsStructurallyEquivalent(Context, Arg1: D1->getConstraintExpr(),
2085 Arg2: D2->getConstraintExpr());
2086}
2087
2088static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2089 FriendDecl *D1, FriendDecl *D2) {
2090 if ((D1->getFriendType() && D2->getFriendDecl()) ||
2091 (D1->getFriendDecl() && D2->getFriendType())) {
2092 return false;
2093 }
2094 if (D1->getFriendType() && D2->getFriendType())
2095 return IsStructurallyEquivalent(Context,
2096 T1: D1->getFriendType()->getType(),
2097 T2: D2->getFriendType()->getType());
2098 if (D1->getFriendDecl() && D2->getFriendDecl())
2099 return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
2100 D2->getFriendDecl());
2101 return false;
2102}
2103
2104static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2105 TypedefNameDecl *D1, TypedefNameDecl *D2) {
2106 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
2107 return false;
2108
2109 return IsStructurallyEquivalent(Context, T1: D1->getUnderlyingType(),
2110 T2: D2->getUnderlyingType());
2111}
2112
2113static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2114 FunctionDecl *D1, FunctionDecl *D2) {
2115 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
2116 return false;
2117
2118 if (D1->isOverloadedOperator()) {
2119 if (!D2->isOverloadedOperator())
2120 return false;
2121 if (D1->getOverloadedOperator() != D2->getOverloadedOperator())
2122 return false;
2123 }
2124
2125 // FIXME: Consider checking for function attributes as well.
2126 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
2127 return false;
2128
2129 return true;
2130}
2131
2132static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2133 ObjCIvarDecl *D1, ObjCIvarDecl *D2,
2134 QualType Owner2Type) {
2135 if (D1->getAccessControl() != D2->getAccessControl())
2136 return false;
2137
2138 return IsStructurallyEquivalent(Context, Field1: cast<FieldDecl>(Val: D1),
2139 Field2: cast<FieldDecl>(Val: D2), Owner2Type);
2140}
2141
2142static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2143 ObjCIvarDecl *D1, ObjCIvarDecl *D2) {
2144 QualType Owner2Type =
2145 Context.ToCtx.getObjCInterfaceType(Decl: D2->getContainingInterface());
2146 return IsStructurallyEquivalent(Context, D1, D2, Owner2Type);
2147}
2148
2149static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2150 ObjCMethodDecl *Method1,
2151 ObjCMethodDecl *Method2) {
2152 bool PropertiesEqual =
2153 Method1->isInstanceMethod() == Method2->isInstanceMethod() &&
2154 Method1->isVariadic() == Method2->isVariadic() &&
2155 Method1->isDirectMethod() == Method2->isDirectMethod();
2156 if (!PropertiesEqual)
2157 return false;
2158
2159 // Compare selector slot names.
2160 Selector Selector1 = Method1->getSelector(),
2161 Selector2 = Method2->getSelector();
2162 unsigned NumArgs = Selector1.getNumArgs();
2163 if (NumArgs != Selector2.getNumArgs())
2164 return false;
2165 // Compare all selector slots. For selectors with arguments it means all arg
2166 // slots. And if there are no arguments, compare the first-and-only slot.
2167 unsigned SlotsToCheck = NumArgs > 0 ? NumArgs : 1;
2168 for (unsigned I = 0; I < SlotsToCheck; ++I) {
2169 if (!IsStructurallyEquivalent(Name1: Selector1.getIdentifierInfoForSlot(argIndex: I),
2170 Name2: Selector2.getIdentifierInfoForSlot(argIndex: I)))
2171 return false;
2172 }
2173
2174 // Compare types.
2175 if (!IsStructurallyEquivalent(Context, T1: Method1->getReturnType(),
2176 T2: Method2->getReturnType()))
2177 return false;
2178 assert(
2179 Method1->param_size() == Method2->param_size() &&
2180 "Same number of arguments should be already enforced in Selector checks");
2181 for (ObjCMethodDecl::param_type_iterator
2182 ParamT1 = Method1->param_type_begin(),
2183 ParamT1End = Method1->param_type_end(),
2184 ParamT2 = Method2->param_type_begin(),
2185 ParamT2End = Method2->param_type_end();
2186 (ParamT1 != ParamT1End) && (ParamT2 != ParamT2End);
2187 ++ParamT1, ++ParamT2) {
2188 if (!IsStructurallyEquivalent(Context, T1: *ParamT1, T2: *ParamT2))
2189 return false;
2190 }
2191
2192 return true;
2193}
2194
2195static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2196 ObjCCategoryDecl *D1,
2197 ObjCCategoryDecl *D2) {
2198 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
2199 return false;
2200
2201 const ObjCInterfaceDecl *Intf1 = D1->getClassInterface(),
2202 *Intf2 = D2->getClassInterface();
2203 if ((!Intf1 || !Intf2) && (Intf1 != Intf2))
2204 return false;
2205
2206 if (Intf1 &&
2207 !IsStructurallyEquivalent(Intf1->getIdentifier(), Intf2->getIdentifier()))
2208 return false;
2209
2210 // Compare protocols.
2211 ObjCCategoryDecl::protocol_iterator Protocol2 = D2->protocol_begin(),
2212 Protocol2End = D2->protocol_end();
2213 for (ObjCCategoryDecl::protocol_iterator Protocol1 = D1->protocol_begin(),
2214 Protocol1End = D1->protocol_end();
2215 Protocol1 != Protocol1End; ++Protocol1, ++Protocol2) {
2216 if (Protocol2 == Protocol2End)
2217 return false;
2218 if (!IsStructurallyEquivalent((*Protocol1)->getIdentifier(),
2219 (*Protocol2)->getIdentifier()))
2220 return false;
2221 }
2222 if (Protocol2 != Protocol2End)
2223 return false;
2224
2225 // Compare ivars.
2226 QualType D2Type =
2227 Intf2 ? Context.ToCtx.getObjCInterfaceType(Decl: Intf2) : QualType();
2228 ObjCCategoryDecl::ivar_iterator Ivar2 = D2->ivar_begin(),
2229 Ivar2End = D2->ivar_end();
2230 for (ObjCCategoryDecl::ivar_iterator Ivar1 = D1->ivar_begin(),
2231 Ivar1End = D1->ivar_end();
2232 Ivar1 != Ivar1End; ++Ivar1, ++Ivar2) {
2233 if (Ivar2 == Ivar2End)
2234 return false;
2235 if (!IsStructurallyEquivalent(Context, D1: *Ivar1, D2: *Ivar2, Owner2Type: D2Type))
2236 return false;
2237 }
2238 if (Ivar2 != Ivar2End)
2239 return false;
2240
2241 // Compare methods.
2242 ObjCCategoryDecl::method_iterator Method2 = D2->meth_begin(),
2243 Method2End = D2->meth_end();
2244 for (ObjCCategoryDecl::method_iterator Method1 = D1->meth_begin(),
2245 Method1End = D1->meth_end();
2246 Method1 != Method1End; ++Method1, ++Method2) {
2247 if (Method2 == Method2End)
2248 return false;
2249 if (!IsStructurallyEquivalent(Context, Method1: *Method1, Method2: *Method2))
2250 return false;
2251 }
2252 if (Method2 != Method2End)
2253 return false;
2254
2255 return true;
2256}
2257
2258/// Determine structural equivalence of two declarations.
2259static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
2260 Decl *D1, Decl *D2) {
2261 // FIXME: Check for known structural equivalences via a callback of some sort.
2262
2263 D1 = D1->getCanonicalDecl();
2264 D2 = D2->getCanonicalDecl();
2265 std::pair<Decl *, Decl *> P{D1, D2};
2266
2267 // Check whether we already know that these two declarations are not
2268 // structurally equivalent.
2269 if (Context.NonEquivalentDecls.count(V: P))
2270 return false;
2271
2272 // Check if a check for these declarations is already pending.
2273 // If yes D1 and D2 will be checked later (from DeclsToCheck),
2274 // or these are already checked (and equivalent).
2275 bool Inserted = Context.VisitedDecls.insert(V: P).second;
2276 if (!Inserted)
2277 return true;
2278
2279 Context.DeclsToCheck.push(x: P);
2280
2281 return true;
2282}
2283
2284DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
2285 unsigned DiagID) {
2286 assert(Complain && "Not allowed to complain");
2287 if (LastDiagFromC2)
2288 FromCtx.getDiagnostics().notePriorDiagnosticFrom(Other: ToCtx.getDiagnostics());
2289 LastDiagFromC2 = false;
2290 return FromCtx.getDiagnostics().Report(Loc, DiagID);
2291}
2292
2293DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
2294 unsigned DiagID) {
2295 assert(Complain && "Not allowed to complain");
2296 if (!LastDiagFromC2)
2297 ToCtx.getDiagnostics().notePriorDiagnosticFrom(Other: FromCtx.getDiagnostics());
2298 LastDiagFromC2 = true;
2299 return ToCtx.getDiagnostics().Report(Loc, DiagID);
2300}
2301
2302std::optional<unsigned>
2303StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
2304 ASTContext &Context = Anon->getASTContext();
2305 QualType AnonTy = Context.getRecordType(Decl: Anon);
2306
2307 const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
2308 if (!Owner)
2309 return std::nullopt;
2310
2311 unsigned Index = 0;
2312 for (const auto *D : Owner->noload_decls()) {
2313 const auto *F = dyn_cast<FieldDecl>(D);
2314 if (!F)
2315 continue;
2316
2317 if (F->isAnonymousStructOrUnion()) {
2318 if (Context.hasSameType(F->getType(), AnonTy))
2319 break;
2320 ++Index;
2321 continue;
2322 }
2323
2324 // If the field looks like this:
2325 // struct { ... } A;
2326 QualType FieldType = F->getType();
2327 // In case of nested structs.
2328 while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
2329 FieldType = ElabType->getNamedType();
2330
2331 if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
2332 const RecordDecl *RecDecl = RecType->getDecl();
2333 if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
2334 if (Context.hasSameType(FieldType, AnonTy))
2335 break;
2336 ++Index;
2337 continue;
2338 }
2339 }
2340 }
2341
2342 return Index;
2343}
2344
2345unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
2346 unsigned ErrorDiagnostic) {
2347 if (ErrorOnTagTypeMismatch)
2348 return ErrorDiagnostic;
2349
2350 switch (ErrorDiagnostic) {
2351 case diag::err_odr_variable_type_inconsistent:
2352 return diag::warn_odr_variable_type_inconsistent;
2353 case diag::err_odr_variable_multiple_def:
2354 return diag::warn_odr_variable_multiple_def;
2355 case diag::err_odr_function_type_inconsistent:
2356 return diag::warn_odr_function_type_inconsistent;
2357 case diag::err_odr_tag_type_inconsistent:
2358 return diag::warn_odr_tag_type_inconsistent;
2359 case diag::err_odr_field_type_inconsistent:
2360 return diag::warn_odr_field_type_inconsistent;
2361 case diag::err_odr_ivar_type_inconsistent:
2362 return diag::warn_odr_ivar_type_inconsistent;
2363 case diag::err_odr_objc_superclass_inconsistent:
2364 return diag::warn_odr_objc_superclass_inconsistent;
2365 case diag::err_odr_objc_method_result_type_inconsistent:
2366 return diag::warn_odr_objc_method_result_type_inconsistent;
2367 case diag::err_odr_objc_method_num_params_inconsistent:
2368 return diag::warn_odr_objc_method_num_params_inconsistent;
2369 case diag::err_odr_objc_method_param_type_inconsistent:
2370 return diag::warn_odr_objc_method_param_type_inconsistent;
2371 case diag::err_odr_objc_method_variadic_inconsistent:
2372 return diag::warn_odr_objc_method_variadic_inconsistent;
2373 case diag::err_odr_objc_property_type_inconsistent:
2374 return diag::warn_odr_objc_property_type_inconsistent;
2375 case diag::err_odr_objc_property_impl_kind_inconsistent:
2376 return diag::warn_odr_objc_property_impl_kind_inconsistent;
2377 case diag::err_odr_objc_synthesize_ivar_inconsistent:
2378 return diag::warn_odr_objc_synthesize_ivar_inconsistent;
2379 case diag::err_odr_different_num_template_parameters:
2380 return diag::warn_odr_different_num_template_parameters;
2381 case diag::err_odr_different_template_parameter_kind:
2382 return diag::warn_odr_different_template_parameter_kind;
2383 case diag::err_odr_parameter_pack_non_pack:
2384 return diag::warn_odr_parameter_pack_non_pack;
2385 case diag::err_odr_non_type_parameter_type_inconsistent:
2386 return diag::warn_odr_non_type_parameter_type_inconsistent;
2387 }
2388 llvm_unreachable("Diagnostic kind not handled in preceding switch");
2389}
2390
2391bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
2392
2393 // Ensure that the implementation functions (all static functions in this TU)
2394 // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
2395 // because that will wreak havoc the internal state (DeclsToCheck and
2396 // VisitedDecls members) and can cause faulty behaviour.
2397 // In other words: Do not start a graph search from a new node with the
2398 // internal data of another search in progress.
2399 // FIXME: Better encapsulation and separation of internal and public
2400 // functionality.
2401 assert(DeclsToCheck.empty());
2402 assert(VisitedDecls.empty());
2403
2404 if (!::IsStructurallyEquivalent(Context&: *this, D1, D2))
2405 return false;
2406
2407 return !Finish();
2408}
2409
2410bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
2411 assert(DeclsToCheck.empty());
2412 assert(VisitedDecls.empty());
2413 if (!::IsStructurallyEquivalent(Context&: *this, T1, T2))
2414 return false;
2415
2416 return !Finish();
2417}
2418
2419bool StructuralEquivalenceContext::IsEquivalent(Stmt *S1, Stmt *S2) {
2420 assert(DeclsToCheck.empty());
2421 assert(VisitedDecls.empty());
2422 if (!::IsStructurallyEquivalent(Context&: *this, S1, S2))
2423 return false;
2424
2425 return !Finish();
2426}
2427
2428bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
2429 // Check for equivalent described template.
2430 TemplateDecl *Template1 = D1->getDescribedTemplate();
2431 TemplateDecl *Template2 = D2->getDescribedTemplate();
2432 if ((Template1 != nullptr) != (Template2 != nullptr))
2433 return false;
2434 if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
2435 return false;
2436
2437 // FIXME: Move check for identifier names into this function.
2438
2439 return true;
2440}
2441
2442bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
2443 Decl *D1, Decl *D2) {
2444
2445 // Kind mismatch.
2446 if (D1->getKind() != D2->getKind())
2447 return false;
2448
2449 // Cast the Decls to their actual subclass so that the right overload of
2450 // IsStructurallyEquivalent is called.
2451 switch (D1->getKind()) {
2452#define ABSTRACT_DECL(DECL)
2453#define DECL(DERIVED, BASE) \
2454 case Decl::Kind::DERIVED: \
2455 return ::IsStructurallyEquivalent(*this, static_cast<DERIVED##Decl *>(D1), \
2456 static_cast<DERIVED##Decl *>(D2));
2457#include "clang/AST/DeclNodes.inc"
2458 }
2459 return true;
2460}
2461
2462bool StructuralEquivalenceContext::Finish() {
2463 while (!DeclsToCheck.empty()) {
2464 // Check the next declaration.
2465 std::pair<Decl *, Decl *> P = DeclsToCheck.front();
2466 DeclsToCheck.pop();
2467
2468 Decl *D1 = P.first;
2469 Decl *D2 = P.second;
2470
2471 bool Equivalent =
2472 CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
2473
2474 if (!Equivalent) {
2475 // Note that these two declarations are not equivalent (and we already
2476 // know about it).
2477 NonEquivalentDecls.insert(V: P);
2478
2479 return true;
2480 }
2481 }
2482
2483 return false;
2484}
2485

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