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