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