xref: /freebsd/contrib/llvm-project/clang/lib/AST/ASTStructuralEquivalence.cpp (revision 29fc4075e69fd27de0cded313ac6000165d99f8b)
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      // It is sufficient to check value of getAsTemplateDecl.
521      break;
522 
523   }
524 
525   return true;
526 }
527 
528 /// Determine whether two template arguments are equivalent.
529 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
530                                      const TemplateArgument &Arg1,
531                                      const TemplateArgument &Arg2) {
532   if (Arg1.getKind() != Arg2.getKind())
533     return false;
534 
535   switch (Arg1.getKind()) {
536   case TemplateArgument::Null:
537     return true;
538 
539   case TemplateArgument::Type:
540     return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());
541 
542   case TemplateArgument::Integral:
543     if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),
544                                           Arg2.getIntegralType()))
545       return false;
546 
547     return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
548                                      Arg2.getAsIntegral());
549 
550   case TemplateArgument::Declaration:
551     return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());
552 
553   case TemplateArgument::NullPtr:
554     return true; // FIXME: Is this correct?
555 
556   case TemplateArgument::Template:
557     return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
558                                     Arg2.getAsTemplate());
559 
560   case TemplateArgument::TemplateExpansion:
561     return IsStructurallyEquivalent(Context,
562                                     Arg1.getAsTemplateOrTemplatePattern(),
563                                     Arg2.getAsTemplateOrTemplatePattern());
564 
565   case TemplateArgument::Expression:
566     return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
567                                     Arg2.getAsExpr());
568 
569   case TemplateArgument::Pack:
570     if (Arg1.pack_size() != Arg2.pack_size())
571       return false;
572 
573     for (unsigned I = 0, N = Arg1.pack_size(); I != N; ++I)
574       if (!IsStructurallyEquivalent(Context, Arg1.pack_begin()[I],
575                                     Arg2.pack_begin()[I]))
576         return false;
577 
578     return true;
579   }
580 
581   llvm_unreachable("Invalid template argument kind");
582 }
583 
584 /// Determine structural equivalence for the common part of array
585 /// types.
586 static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
587                                           const ArrayType *Array1,
588                                           const ArrayType *Array2) {
589   if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
590                                 Array2->getElementType()))
591     return false;
592   if (Array1->getSizeModifier() != Array2->getSizeModifier())
593     return false;
594   if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
595     return false;
596 
597   return true;
598 }
599 
600 /// Determine structural equivalence based on the ExtInfo of functions. This
601 /// is inspired by ASTContext::mergeFunctionTypes(), we compare calling
602 /// conventions bits but must not compare some other bits.
603 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
604                                      FunctionType::ExtInfo EI1,
605                                      FunctionType::ExtInfo EI2) {
606   // Compatible functions must have compatible calling conventions.
607   if (EI1.getCC() != EI2.getCC())
608     return false;
609 
610   // Regparm is part of the calling convention.
611   if (EI1.getHasRegParm() != EI2.getHasRegParm())
612     return false;
613   if (EI1.getRegParm() != EI2.getRegParm())
614     return false;
615 
616   if (EI1.getProducesResult() != EI2.getProducesResult())
617     return false;
618   if (EI1.getNoCallerSavedRegs() != EI2.getNoCallerSavedRegs())
619     return false;
620   if (EI1.getNoCfCheck() != EI2.getNoCfCheck())
621     return false;
622 
623   return true;
624 }
625 
626 /// Check the equivalence of exception specifications.
627 static bool IsEquivalentExceptionSpec(StructuralEquivalenceContext &Context,
628                                       const FunctionProtoType *Proto1,
629                                       const FunctionProtoType *Proto2) {
630 
631   auto Spec1 = Proto1->getExceptionSpecType();
632   auto Spec2 = Proto2->getExceptionSpecType();
633 
634   if (isUnresolvedExceptionSpec(Spec1) || isUnresolvedExceptionSpec(Spec2))
635     return true;
636 
637   if (Spec1 != Spec2)
638     return false;
639   if (Spec1 == EST_Dynamic) {
640     if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
641       return false;
642     for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
643       if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
644                                     Proto2->getExceptionType(I)))
645         return false;
646     }
647   } else if (isComputedNoexcept(Spec1)) {
648     if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
649                                   Proto2->getNoexceptExpr()))
650       return false;
651   }
652 
653   return true;
654 }
655 
656 /// Determine structural equivalence of two types.
657 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
658                                      QualType T1, QualType T2) {
659   if (T1.isNull() || T2.isNull())
660     return T1.isNull() && T2.isNull();
661 
662   QualType OrigT1 = T1;
663   QualType OrigT2 = T2;
664 
665   if (!Context.StrictTypeSpelling) {
666     // We aren't being strict about token-to-token equivalence of types,
667     // so map down to the canonical type.
668     T1 = Context.FromCtx.getCanonicalType(T1);
669     T2 = Context.ToCtx.getCanonicalType(T2);
670   }
671 
672   if (T1.getQualifiers() != T2.getQualifiers())
673     return false;
674 
675   Type::TypeClass TC = T1->getTypeClass();
676 
677   if (T1->getTypeClass() != T2->getTypeClass()) {
678     // Compare function types with prototypes vs. without prototypes as if
679     // both did not have prototypes.
680     if (T1->getTypeClass() == Type::FunctionProto &&
681         T2->getTypeClass() == Type::FunctionNoProto)
682       TC = Type::FunctionNoProto;
683     else if (T1->getTypeClass() == Type::FunctionNoProto &&
684              T2->getTypeClass() == Type::FunctionProto)
685       TC = Type::FunctionNoProto;
686     else
687       return false;
688   }
689 
690   switch (TC) {
691   case Type::Builtin:
692     // FIXME: Deal with Char_S/Char_U.
693     if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
694       return false;
695     break;
696 
697   case Type::Complex:
698     if (!IsStructurallyEquivalent(Context,
699                                   cast<ComplexType>(T1)->getElementType(),
700                                   cast<ComplexType>(T2)->getElementType()))
701       return false;
702     break;
703 
704   case Type::Adjusted:
705   case Type::Decayed:
706     if (!IsStructurallyEquivalent(Context,
707                                   cast<AdjustedType>(T1)->getOriginalType(),
708                                   cast<AdjustedType>(T2)->getOriginalType()))
709       return false;
710     break;
711 
712   case Type::Pointer:
713     if (!IsStructurallyEquivalent(Context,
714                                   cast<PointerType>(T1)->getPointeeType(),
715                                   cast<PointerType>(T2)->getPointeeType()))
716       return false;
717     break;
718 
719   case Type::BlockPointer:
720     if (!IsStructurallyEquivalent(Context,
721                                   cast<BlockPointerType>(T1)->getPointeeType(),
722                                   cast<BlockPointerType>(T2)->getPointeeType()))
723       return false;
724     break;
725 
726   case Type::LValueReference:
727   case Type::RValueReference: {
728     const auto *Ref1 = cast<ReferenceType>(T1);
729     const auto *Ref2 = cast<ReferenceType>(T2);
730     if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
731       return false;
732     if (Ref1->isInnerRef() != Ref2->isInnerRef())
733       return false;
734     if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
735                                   Ref2->getPointeeTypeAsWritten()))
736       return false;
737     break;
738   }
739 
740   case Type::MemberPointer: {
741     const auto *MemPtr1 = cast<MemberPointerType>(T1);
742     const auto *MemPtr2 = cast<MemberPointerType>(T2);
743     if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
744                                   MemPtr2->getPointeeType()))
745       return false;
746     if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
747                                   QualType(MemPtr2->getClass(), 0)))
748       return false;
749     break;
750   }
751 
752   case Type::ConstantArray: {
753     const auto *Array1 = cast<ConstantArrayType>(T1);
754     const auto *Array2 = cast<ConstantArrayType>(T2);
755     if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
756       return false;
757 
758     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
759       return false;
760     break;
761   }
762 
763   case Type::IncompleteArray:
764     if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
765                                        cast<ArrayType>(T2)))
766       return false;
767     break;
768 
769   case Type::VariableArray: {
770     const auto *Array1 = cast<VariableArrayType>(T1);
771     const auto *Array2 = cast<VariableArrayType>(T2);
772     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
773                                   Array2->getSizeExpr()))
774       return false;
775 
776     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
777       return false;
778 
779     break;
780   }
781 
782   case Type::DependentSizedArray: {
783     const auto *Array1 = cast<DependentSizedArrayType>(T1);
784     const auto *Array2 = cast<DependentSizedArrayType>(T2);
785     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
786                                   Array2->getSizeExpr()))
787       return false;
788 
789     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
790       return false;
791 
792     break;
793   }
794 
795   case Type::DependentAddressSpace: {
796     const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);
797     const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);
798     if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),
799                                   DepAddressSpace2->getAddrSpaceExpr()))
800       return false;
801     if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
802                                   DepAddressSpace2->getPointeeType()))
803       return false;
804 
805     break;
806   }
807 
808   case Type::DependentSizedExtVector: {
809     const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);
810     const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);
811     if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
812                                   Vec2->getSizeExpr()))
813       return false;
814     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
815                                   Vec2->getElementType()))
816       return false;
817     break;
818   }
819 
820   case Type::DependentVector: {
821     const auto *Vec1 = cast<DependentVectorType>(T1);
822     const auto *Vec2 = cast<DependentVectorType>(T2);
823     if (Vec1->getVectorKind() != Vec2->getVectorKind())
824       return false;
825     if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
826                                   Vec2->getSizeExpr()))
827       return false;
828     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
829                                   Vec2->getElementType()))
830       return false;
831     break;
832   }
833 
834   case Type::Vector:
835   case Type::ExtVector: {
836     const auto *Vec1 = cast<VectorType>(T1);
837     const auto *Vec2 = cast<VectorType>(T2);
838     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
839                                   Vec2->getElementType()))
840       return false;
841     if (Vec1->getNumElements() != Vec2->getNumElements())
842       return false;
843     if (Vec1->getVectorKind() != Vec2->getVectorKind())
844       return false;
845     break;
846   }
847 
848   case Type::DependentSizedMatrix: {
849     const DependentSizedMatrixType *Mat1 = cast<DependentSizedMatrixType>(T1);
850     const DependentSizedMatrixType *Mat2 = cast<DependentSizedMatrixType>(T2);
851     // The element types, row and column expressions must be structurally
852     // equivalent.
853     if (!IsStructurallyEquivalent(Context, Mat1->getRowExpr(),
854                                   Mat2->getRowExpr()) ||
855         !IsStructurallyEquivalent(Context, Mat1->getColumnExpr(),
856                                   Mat2->getColumnExpr()) ||
857         !IsStructurallyEquivalent(Context, Mat1->getElementType(),
858                                   Mat2->getElementType()))
859       return false;
860     break;
861   }
862 
863   case Type::ConstantMatrix: {
864     const ConstantMatrixType *Mat1 = cast<ConstantMatrixType>(T1);
865     const ConstantMatrixType *Mat2 = cast<ConstantMatrixType>(T2);
866     // The element types must be structurally equivalent and the number of rows
867     // and columns must match.
868     if (!IsStructurallyEquivalent(Context, Mat1->getElementType(),
869                                   Mat2->getElementType()) ||
870         Mat1->getNumRows() != Mat2->getNumRows() ||
871         Mat1->getNumColumns() != Mat2->getNumColumns())
872       return false;
873     break;
874   }
875 
876   case Type::FunctionProto: {
877     const auto *Proto1 = cast<FunctionProtoType>(T1);
878     const auto *Proto2 = cast<FunctionProtoType>(T2);
879 
880     if (Proto1->getNumParams() != Proto2->getNumParams())
881       return false;
882     for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
883       if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
884                                     Proto2->getParamType(I)))
885         return false;
886     }
887     if (Proto1->isVariadic() != Proto2->isVariadic())
888       return false;
889 
890     if (Proto1->getMethodQuals() != Proto2->getMethodQuals())
891       return false;
892 
893     // Check exceptions, this information is lost in canonical type.
894     const auto *OrigProto1 =
895         cast<FunctionProtoType>(OrigT1.getDesugaredType(Context.FromCtx));
896     const auto *OrigProto2 =
897         cast<FunctionProtoType>(OrigT2.getDesugaredType(Context.ToCtx));
898     if (!IsEquivalentExceptionSpec(Context, OrigProto1, OrigProto2))
899       return false;
900 
901     // Fall through to check the bits common with FunctionNoProtoType.
902     LLVM_FALLTHROUGH;
903   }
904 
905   case Type::FunctionNoProto: {
906     const auto *Function1 = cast<FunctionType>(T1);
907     const auto *Function2 = cast<FunctionType>(T2);
908     if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
909                                   Function2->getReturnType()))
910       return false;
911     if (!IsStructurallyEquivalent(Context, Function1->getExtInfo(),
912                                   Function2->getExtInfo()))
913       return false;
914     break;
915   }
916 
917   case Type::UnresolvedUsing:
918     if (!IsStructurallyEquivalent(Context,
919                                   cast<UnresolvedUsingType>(T1)->getDecl(),
920                                   cast<UnresolvedUsingType>(T2)->getDecl()))
921       return false;
922     break;
923 
924   case Type::Attributed:
925     if (!IsStructurallyEquivalent(Context,
926                                   cast<AttributedType>(T1)->getModifiedType(),
927                                   cast<AttributedType>(T2)->getModifiedType()))
928       return false;
929     if (!IsStructurallyEquivalent(
930             Context, cast<AttributedType>(T1)->getEquivalentType(),
931             cast<AttributedType>(T2)->getEquivalentType()))
932       return false;
933     break;
934 
935   case Type::Paren:
936     if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
937                                   cast<ParenType>(T2)->getInnerType()))
938       return false;
939     break;
940 
941   case Type::MacroQualified:
942     if (!IsStructurallyEquivalent(
943             Context, cast<MacroQualifiedType>(T1)->getUnderlyingType(),
944             cast<MacroQualifiedType>(T2)->getUnderlyingType()))
945       return false;
946     break;
947 
948   case Type::Using:
949     if (!IsStructurallyEquivalent(Context, cast<UsingType>(T1)->getFoundDecl(),
950                                   cast<UsingType>(T2)->getFoundDecl()))
951       return false;
952     break;
953 
954   case Type::Typedef:
955     if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
956                                   cast<TypedefType>(T2)->getDecl()))
957       return false;
958     break;
959 
960   case Type::TypeOfExpr:
961     if (!IsStructurallyEquivalent(
962             Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
963             cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
964       return false;
965     break;
966 
967   case Type::TypeOf:
968     if (!IsStructurallyEquivalent(Context,
969                                   cast<TypeOfType>(T1)->getUnderlyingType(),
970                                   cast<TypeOfType>(T2)->getUnderlyingType()))
971       return false;
972     break;
973 
974   case Type::UnaryTransform:
975     if (!IsStructurallyEquivalent(
976             Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
977             cast<UnaryTransformType>(T2)->getUnderlyingType()))
978       return false;
979     break;
980 
981   case Type::Decltype:
982     if (!IsStructurallyEquivalent(Context,
983                                   cast<DecltypeType>(T1)->getUnderlyingExpr(),
984                                   cast<DecltypeType>(T2)->getUnderlyingExpr()))
985       return false;
986     break;
987 
988   case Type::Auto: {
989     auto *Auto1 = cast<AutoType>(T1);
990     auto *Auto2 = cast<AutoType>(T2);
991     if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),
992                                   Auto2->getDeducedType()))
993       return false;
994     if (Auto1->isConstrained() != Auto2->isConstrained())
995       return false;
996     if (Auto1->isConstrained()) {
997       if (Auto1->getTypeConstraintConcept() !=
998           Auto2->getTypeConstraintConcept())
999         return false;
1000       ArrayRef<TemplateArgument> Auto1Args =
1001           Auto1->getTypeConstraintArguments();
1002       ArrayRef<TemplateArgument> Auto2Args =
1003           Auto2->getTypeConstraintArguments();
1004       if (Auto1Args.size() != Auto2Args.size())
1005         return false;
1006       for (unsigned I = 0, N = Auto1Args.size(); I != N; ++I) {
1007         if (!IsStructurallyEquivalent(Context, Auto1Args[I], Auto2Args[I]))
1008           return false;
1009       }
1010     }
1011     break;
1012   }
1013 
1014   case Type::DeducedTemplateSpecialization: {
1015     const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
1016     const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
1017     if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
1018                                   DT2->getTemplateName()))
1019       return false;
1020     if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
1021                                   DT2->getDeducedType()))
1022       return false;
1023     break;
1024   }
1025 
1026   case Type::Record:
1027   case Type::Enum:
1028     if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
1029                                   cast<TagType>(T2)->getDecl()))
1030       return false;
1031     break;
1032 
1033   case Type::TemplateTypeParm: {
1034     const auto *Parm1 = cast<TemplateTypeParmType>(T1);
1035     const auto *Parm2 = cast<TemplateTypeParmType>(T2);
1036     if (Parm1->getDepth() != Parm2->getDepth())
1037       return false;
1038     if (Parm1->getIndex() != Parm2->getIndex())
1039       return false;
1040     if (Parm1->isParameterPack() != Parm2->isParameterPack())
1041       return false;
1042 
1043     // Names of template type parameters are never significant.
1044     break;
1045   }
1046 
1047   case Type::SubstTemplateTypeParm: {
1048     const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
1049     const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
1050     if (!IsStructurallyEquivalent(Context,
1051                                   QualType(Subst1->getReplacedParameter(), 0),
1052                                   QualType(Subst2->getReplacedParameter(), 0)))
1053       return false;
1054     if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
1055                                   Subst2->getReplacementType()))
1056       return false;
1057     break;
1058   }
1059 
1060   case Type::SubstTemplateTypeParmPack: {
1061     const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
1062     const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
1063     if (!IsStructurallyEquivalent(Context,
1064                                   QualType(Subst1->getReplacedParameter(), 0),
1065                                   QualType(Subst2->getReplacedParameter(), 0)))
1066       return false;
1067     if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
1068                                   Subst2->getArgumentPack()))
1069       return false;
1070     break;
1071   }
1072 
1073   case Type::TemplateSpecialization: {
1074     const auto *Spec1 = cast<TemplateSpecializationType>(T1);
1075     const auto *Spec2 = cast<TemplateSpecializationType>(T2);
1076     if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
1077                                   Spec2->getTemplateName()))
1078       return false;
1079     if (Spec1->getNumArgs() != Spec2->getNumArgs())
1080       return false;
1081     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
1082       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
1083                                     Spec2->getArg(I)))
1084         return false;
1085     }
1086     break;
1087   }
1088 
1089   case Type::Elaborated: {
1090     const auto *Elab1 = cast<ElaboratedType>(T1);
1091     const auto *Elab2 = cast<ElaboratedType>(T2);
1092     // CHECKME: what if a keyword is ETK_None or ETK_typename ?
1093     if (Elab1->getKeyword() != Elab2->getKeyword())
1094       return false;
1095     if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
1096                                   Elab2->getQualifier()))
1097       return false;
1098     if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
1099                                   Elab2->getNamedType()))
1100       return false;
1101     break;
1102   }
1103 
1104   case Type::InjectedClassName: {
1105     const auto *Inj1 = cast<InjectedClassNameType>(T1);
1106     const auto *Inj2 = cast<InjectedClassNameType>(T2);
1107     if (!IsStructurallyEquivalent(Context,
1108                                   Inj1->getInjectedSpecializationType(),
1109                                   Inj2->getInjectedSpecializationType()))
1110       return false;
1111     break;
1112   }
1113 
1114   case Type::DependentName: {
1115     const auto *Typename1 = cast<DependentNameType>(T1);
1116     const auto *Typename2 = cast<DependentNameType>(T2);
1117     if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
1118                                   Typename2->getQualifier()))
1119       return false;
1120     if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
1121                                   Typename2->getIdentifier()))
1122       return false;
1123 
1124     break;
1125   }
1126 
1127   case Type::DependentTemplateSpecialization: {
1128     const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
1129     const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
1130     if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
1131                                   Spec2->getQualifier()))
1132       return false;
1133     if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
1134                                   Spec2->getIdentifier()))
1135       return false;
1136     if (Spec1->getNumArgs() != Spec2->getNumArgs())
1137       return false;
1138     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
1139       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
1140                                     Spec2->getArg(I)))
1141         return false;
1142     }
1143     break;
1144   }
1145 
1146   case Type::PackExpansion:
1147     if (!IsStructurallyEquivalent(Context,
1148                                   cast<PackExpansionType>(T1)->getPattern(),
1149                                   cast<PackExpansionType>(T2)->getPattern()))
1150       return false;
1151     break;
1152 
1153   case Type::ObjCInterface: {
1154     const auto *Iface1 = cast<ObjCInterfaceType>(T1);
1155     const auto *Iface2 = cast<ObjCInterfaceType>(T2);
1156     if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
1157                                   Iface2->getDecl()))
1158       return false;
1159     break;
1160   }
1161 
1162   case Type::ObjCTypeParam: {
1163     const auto *Obj1 = cast<ObjCTypeParamType>(T1);
1164     const auto *Obj2 = cast<ObjCTypeParamType>(T2);
1165     if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
1166       return false;
1167 
1168     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
1169       return false;
1170     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
1171       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
1172                                     Obj2->getProtocol(I)))
1173         return false;
1174     }
1175     break;
1176   }
1177 
1178   case Type::ObjCObject: {
1179     const auto *Obj1 = cast<ObjCObjectType>(T1);
1180     const auto *Obj2 = cast<ObjCObjectType>(T2);
1181     if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
1182                                   Obj2->getBaseType()))
1183       return false;
1184     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
1185       return false;
1186     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
1187       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
1188                                     Obj2->getProtocol(I)))
1189         return false;
1190     }
1191     break;
1192   }
1193 
1194   case Type::ObjCObjectPointer: {
1195     const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
1196     const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
1197     if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
1198                                   Ptr2->getPointeeType()))
1199       return false;
1200     break;
1201   }
1202 
1203   case Type::Atomic:
1204     if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
1205                                   cast<AtomicType>(T2)->getValueType()))
1206       return false;
1207     break;
1208 
1209   case Type::Pipe:
1210     if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
1211                                   cast<PipeType>(T2)->getElementType()))
1212       return false;
1213     break;
1214   case Type::BitInt: {
1215     const auto *Int1 = cast<BitIntType>(T1);
1216     const auto *Int2 = cast<BitIntType>(T2);
1217 
1218     if (Int1->isUnsigned() != Int2->isUnsigned() ||
1219         Int1->getNumBits() != Int2->getNumBits())
1220       return false;
1221     break;
1222   }
1223   case Type::DependentBitInt: {
1224     const auto *Int1 = cast<DependentBitIntType>(T1);
1225     const auto *Int2 = cast<DependentBitIntType>(T2);
1226 
1227     if (Int1->isUnsigned() != Int2->isUnsigned() ||
1228         !IsStructurallyEquivalent(Context, Int1->getNumBitsExpr(),
1229                                   Int2->getNumBitsExpr()))
1230       return false;
1231   }
1232   } // end switch
1233 
1234   return true;
1235 }
1236 
1237 /// Determine structural equivalence of two fields.
1238 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1239                                      FieldDecl *Field1, FieldDecl *Field2) {
1240   const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
1241 
1242   // For anonymous structs/unions, match up the anonymous struct/union type
1243   // declarations directly, so that we don't go off searching for anonymous
1244   // types
1245   if (Field1->isAnonymousStructOrUnion() &&
1246       Field2->isAnonymousStructOrUnion()) {
1247     RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
1248     RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
1249     return IsStructurallyEquivalent(Context, D1, D2);
1250   }
1251 
1252   // Check for equivalent field names.
1253   IdentifierInfo *Name1 = Field1->getIdentifier();
1254   IdentifierInfo *Name2 = Field2->getIdentifier();
1255   if (!::IsStructurallyEquivalent(Name1, Name2)) {
1256     if (Context.Complain) {
1257       Context.Diag2(
1258           Owner2->getLocation(),
1259           Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1260           << Context.ToCtx.getTypeDeclType(Owner2);
1261       Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
1262           << Field2->getDeclName();
1263       Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
1264           << Field1->getDeclName();
1265     }
1266     return false;
1267   }
1268 
1269   if (!IsStructurallyEquivalent(Context, Field1->getType(),
1270                                 Field2->getType())) {
1271     if (Context.Complain) {
1272       Context.Diag2(
1273           Owner2->getLocation(),
1274           Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1275           << Context.ToCtx.getTypeDeclType(Owner2);
1276       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1277           << Field2->getDeclName() << Field2->getType();
1278       Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1279           << Field1->getDeclName() << Field1->getType();
1280     }
1281     return false;
1282   }
1283 
1284   if (Field1->isBitField())
1285     return IsStructurallyEquivalent(Context, Field1->getBitWidth(),
1286                                     Field2->getBitWidth());
1287 
1288   return true;
1289 }
1290 
1291 /// Determine structural equivalence of two methods.
1292 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1293                                      CXXMethodDecl *Method1,
1294                                      CXXMethodDecl *Method2) {
1295   bool PropertiesEqual =
1296       Method1->getDeclKind() == Method2->getDeclKind() &&
1297       Method1->getRefQualifier() == Method2->getRefQualifier() &&
1298       Method1->getAccess() == Method2->getAccess() &&
1299       Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
1300       Method1->isStatic() == Method2->isStatic() &&
1301       Method1->isConst() == Method2->isConst() &&
1302       Method1->isVolatile() == Method2->isVolatile() &&
1303       Method1->isVirtual() == Method2->isVirtual() &&
1304       Method1->isPure() == Method2->isPure() &&
1305       Method1->isDefaulted() == Method2->isDefaulted() &&
1306       Method1->isDeleted() == Method2->isDeleted();
1307   if (!PropertiesEqual)
1308     return false;
1309   // FIXME: Check for 'final'.
1310 
1311   if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
1312     auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
1313     if (!Constructor1->getExplicitSpecifier().isEquivalent(
1314             Constructor2->getExplicitSpecifier()))
1315       return false;
1316   }
1317 
1318   if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
1319     auto *Conversion2 = cast<CXXConversionDecl>(Method2);
1320     if (!Conversion1->getExplicitSpecifier().isEquivalent(
1321             Conversion2->getExplicitSpecifier()))
1322       return false;
1323     if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
1324                                   Conversion2->getConversionType()))
1325       return false;
1326   }
1327 
1328   const IdentifierInfo *Name1 = Method1->getIdentifier();
1329   const IdentifierInfo *Name2 = Method2->getIdentifier();
1330   if (!::IsStructurallyEquivalent(Name1, Name2)) {
1331     return false;
1332     // TODO: Names do not match, add warning like at check for FieldDecl.
1333   }
1334 
1335   // Check the prototypes.
1336   if (!::IsStructurallyEquivalent(Context,
1337                                   Method1->getType(), Method2->getType()))
1338     return false;
1339 
1340   return true;
1341 }
1342 
1343 /// Determine structural equivalence of two lambda classes.
1344 static bool
1345 IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
1346                                 CXXRecordDecl *D1, CXXRecordDecl *D2) {
1347   assert(D1->isLambda() && D2->isLambda() &&
1348          "Must be called on lambda classes");
1349   if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(),
1350                                 D2->getLambdaCallOperator()))
1351     return false;
1352 
1353   return true;
1354 }
1355 
1356 /// Determine if context of a class is equivalent.
1357 static bool IsRecordContextStructurallyEquivalent(RecordDecl *D1,
1358                                                   RecordDecl *D2) {
1359   // The context should be completely equal, including anonymous and inline
1360   // namespaces.
1361   // We compare objects as part of full translation units, not subtrees of
1362   // translation units.
1363   DeclContext *DC1 = D1->getDeclContext()->getNonTransparentContext();
1364   DeclContext *DC2 = D2->getDeclContext()->getNonTransparentContext();
1365   while (true) {
1366     // Special case: We allow a struct defined in a function to be equivalent
1367     // with a similar struct defined outside of a function.
1368     if ((DC1->isFunctionOrMethod() && DC2->isTranslationUnit()) ||
1369         (DC2->isFunctionOrMethod() && DC1->isTranslationUnit()))
1370       return true;
1371 
1372     if (DC1->getDeclKind() != DC2->getDeclKind())
1373       return false;
1374     if (DC1->isTranslationUnit())
1375       break;
1376     if (DC1->isInlineNamespace() != DC2->isInlineNamespace())
1377       return false;
1378     if (const auto *ND1 = dyn_cast<NamedDecl>(DC1)) {
1379       const auto *ND2 = cast<NamedDecl>(DC2);
1380       if (!DC1->isInlineNamespace() &&
1381           !IsStructurallyEquivalent(ND1->getIdentifier(), ND2->getIdentifier()))
1382         return false;
1383     }
1384 
1385     DC1 = DC1->getParent()->getNonTransparentContext();
1386     DC2 = DC2->getParent()->getNonTransparentContext();
1387   }
1388 
1389   return true;
1390 }
1391 
1392 /// Determine structural equivalence of two records.
1393 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1394                                      RecordDecl *D1, RecordDecl *D2) {
1395 
1396   // Check for equivalent structure names.
1397   IdentifierInfo *Name1 = D1->getIdentifier();
1398   if (!Name1 && D1->getTypedefNameForAnonDecl())
1399     Name1 = D1->getTypedefNameForAnonDecl()->getIdentifier();
1400   IdentifierInfo *Name2 = D2->getIdentifier();
1401   if (!Name2 && D2->getTypedefNameForAnonDecl())
1402     Name2 = D2->getTypedefNameForAnonDecl()->getIdentifier();
1403   if (!IsStructurallyEquivalent(Name1, Name2))
1404     return false;
1405 
1406   if (D1->isUnion() != D2->isUnion()) {
1407     if (Context.Complain) {
1408       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1409                                            diag::err_odr_tag_type_inconsistent))
1410           << Context.ToCtx.getTypeDeclType(D2);
1411       Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1412           << D1->getDeclName() << (unsigned)D1->getTagKind();
1413     }
1414     return false;
1415   }
1416 
1417   if (!D1->getDeclName() && !D2->getDeclName()) {
1418     // If both anonymous structs/unions are in a record context, make sure
1419     // they occur in the same location in the context records.
1420     if (Optional<unsigned> Index1 =
1421             StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
1422       if (Optional<unsigned> Index2 =
1423               StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1424                   D2)) {
1425         if (*Index1 != *Index2)
1426           return false;
1427       }
1428     }
1429   }
1430 
1431   // If the records occur in different context (namespace), these should be
1432   // different. This is specially important if the definition of one or both
1433   // records is missing.
1434   if (!IsRecordContextStructurallyEquivalent(D1, D2))
1435     return false;
1436 
1437   // If both declarations are class template specializations, we know
1438   // the ODR applies, so check the template and template arguments.
1439   const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
1440   const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
1441   if (Spec1 && Spec2) {
1442     // Check that the specialized templates are the same.
1443     if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1444                                   Spec2->getSpecializedTemplate()))
1445       return false;
1446 
1447     // Check that the template arguments are the same.
1448     if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1449       return false;
1450 
1451     for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1452       if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
1453                                     Spec2->getTemplateArgs().get(I)))
1454         return false;
1455   }
1456   // If one is a class template specialization and the other is not, these
1457   // structures are different.
1458   else if (Spec1 || Spec2)
1459     return false;
1460 
1461   // Compare the definitions of these two records. If either or both are
1462   // incomplete (i.e. it is a forward decl), we assume that they are
1463   // equivalent.
1464   D1 = D1->getDefinition();
1465   D2 = D2->getDefinition();
1466   if (!D1 || !D2)
1467     return true;
1468 
1469   // If any of the records has external storage and we do a minimal check (or
1470   // AST import) we assume they are equivalent. (If we didn't have this
1471   // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1472   // another AST import which in turn would call the structural equivalency
1473   // check again and finally we'd have an improper result.)
1474   if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1475     if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
1476       return true;
1477 
1478   // If one definition is currently being defined, we do not compare for
1479   // equality and we assume that the decls are equal.
1480   if (D1->isBeingDefined() || D2->isBeingDefined())
1481     return true;
1482 
1483   if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
1484     if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
1485       if (D1CXX->hasExternalLexicalStorage() &&
1486           !D1CXX->isCompleteDefinition()) {
1487         D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1488       }
1489 
1490       if (D1CXX->isLambda() != D2CXX->isLambda())
1491         return false;
1492       if (D1CXX->isLambda()) {
1493         if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))
1494           return false;
1495       }
1496 
1497       if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1498         if (Context.Complain) {
1499           Context.Diag2(D2->getLocation(),
1500                         Context.getApplicableDiagnostic(
1501                             diag::err_odr_tag_type_inconsistent))
1502               << Context.ToCtx.getTypeDeclType(D2);
1503           Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1504               << D2CXX->getNumBases();
1505           Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1506               << D1CXX->getNumBases();
1507         }
1508         return false;
1509       }
1510 
1511       // Check the base classes.
1512       for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1513                                               BaseEnd1 = D1CXX->bases_end(),
1514                                               Base2 = D2CXX->bases_begin();
1515            Base1 != BaseEnd1; ++Base1, ++Base2) {
1516         if (!IsStructurallyEquivalent(Context, Base1->getType(),
1517                                       Base2->getType())) {
1518           if (Context.Complain) {
1519             Context.Diag2(D2->getLocation(),
1520                           Context.getApplicableDiagnostic(
1521                               diag::err_odr_tag_type_inconsistent))
1522                 << Context.ToCtx.getTypeDeclType(D2);
1523             Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1524                 << Base2->getType() << Base2->getSourceRange();
1525             Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1526                 << Base1->getType() << Base1->getSourceRange();
1527           }
1528           return false;
1529         }
1530 
1531         // Check virtual vs. non-virtual inheritance mismatch.
1532         if (Base1->isVirtual() != Base2->isVirtual()) {
1533           if (Context.Complain) {
1534             Context.Diag2(D2->getLocation(),
1535                           Context.getApplicableDiagnostic(
1536                               diag::err_odr_tag_type_inconsistent))
1537                 << Context.ToCtx.getTypeDeclType(D2);
1538             Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1539                 << Base2->isVirtual() << Base2->getSourceRange();
1540             Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1541                 << Base1->isVirtual() << Base1->getSourceRange();
1542           }
1543           return false;
1544         }
1545       }
1546 
1547       // Check the friends for consistency.
1548       CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1549                                      Friend2End = D2CXX->friend_end();
1550       for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1551                                           Friend1End = D1CXX->friend_end();
1552            Friend1 != Friend1End; ++Friend1, ++Friend2) {
1553         if (Friend2 == Friend2End) {
1554           if (Context.Complain) {
1555             Context.Diag2(D2->getLocation(),
1556                           Context.getApplicableDiagnostic(
1557                               diag::err_odr_tag_type_inconsistent))
1558                 << Context.ToCtx.getTypeDeclType(D2CXX);
1559             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1560             Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1561           }
1562           return false;
1563         }
1564 
1565         if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1566           if (Context.Complain) {
1567             Context.Diag2(D2->getLocation(),
1568                           Context.getApplicableDiagnostic(
1569                               diag::err_odr_tag_type_inconsistent))
1570                 << Context.ToCtx.getTypeDeclType(D2CXX);
1571             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1572             Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1573           }
1574           return false;
1575         }
1576       }
1577 
1578       if (Friend2 != Friend2End) {
1579         if (Context.Complain) {
1580           Context.Diag2(D2->getLocation(),
1581                         Context.getApplicableDiagnostic(
1582                             diag::err_odr_tag_type_inconsistent))
1583               << Context.ToCtx.getTypeDeclType(D2);
1584           Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1585           Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1586         }
1587         return false;
1588       }
1589     } else if (D1CXX->getNumBases() > 0) {
1590       if (Context.Complain) {
1591         Context.Diag2(D2->getLocation(),
1592                       Context.getApplicableDiagnostic(
1593                           diag::err_odr_tag_type_inconsistent))
1594             << Context.ToCtx.getTypeDeclType(D2);
1595         const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1596         Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1597             << Base1->getType() << Base1->getSourceRange();
1598         Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1599       }
1600       return false;
1601     }
1602   }
1603 
1604   // Check the fields for consistency.
1605   RecordDecl::field_iterator Field2 = D2->field_begin(),
1606                              Field2End = D2->field_end();
1607   for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1608                                   Field1End = D1->field_end();
1609        Field1 != Field1End; ++Field1, ++Field2) {
1610     if (Field2 == Field2End) {
1611       if (Context.Complain) {
1612         Context.Diag2(D2->getLocation(),
1613                       Context.getApplicableDiagnostic(
1614                           diag::err_odr_tag_type_inconsistent))
1615             << Context.ToCtx.getTypeDeclType(D2);
1616         Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1617             << Field1->getDeclName() << Field1->getType();
1618         Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1619       }
1620       return false;
1621     }
1622 
1623     if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1624       return false;
1625   }
1626 
1627   if (Field2 != Field2End) {
1628     if (Context.Complain) {
1629       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1630                                            diag::err_odr_tag_type_inconsistent))
1631           << Context.ToCtx.getTypeDeclType(D2);
1632       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1633           << Field2->getDeclName() << Field2->getType();
1634       Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1635     }
1636     return false;
1637   }
1638 
1639   return true;
1640 }
1641 
1642 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1643                                      EnumConstantDecl *D1,
1644                                      EnumConstantDecl *D2) {
1645   const llvm::APSInt &FromVal = D1->getInitVal();
1646   const llvm::APSInt &ToVal = D2->getInitVal();
1647   if (FromVal.isSigned() != ToVal.isSigned())
1648     return false;
1649   if (FromVal.getBitWidth() != ToVal.getBitWidth())
1650     return false;
1651   if (FromVal != ToVal)
1652     return false;
1653 
1654   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1655     return false;
1656 
1657   // Init expressions are the most expensive check, so do them last.
1658   return IsStructurallyEquivalent(Context, D1->getInitExpr(),
1659                                   D2->getInitExpr());
1660 }
1661 
1662 /// Determine structural equivalence of two enums.
1663 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1664                                      EnumDecl *D1, EnumDecl *D2) {
1665 
1666   // Check for equivalent enum names.
1667   IdentifierInfo *Name1 = D1->getIdentifier();
1668   if (!Name1 && D1->getTypedefNameForAnonDecl())
1669     Name1 = D1->getTypedefNameForAnonDecl()->getIdentifier();
1670   IdentifierInfo *Name2 = D2->getIdentifier();
1671   if (!Name2 && D2->getTypedefNameForAnonDecl())
1672     Name2 = D2->getTypedefNameForAnonDecl()->getIdentifier();
1673   if (!IsStructurallyEquivalent(Name1, Name2))
1674     return false;
1675 
1676   // Compare the definitions of these two enums. If either or both are
1677   // incomplete (i.e. forward declared), we assume that they are equivalent.
1678   D1 = D1->getDefinition();
1679   D2 = D2->getDefinition();
1680   if (!D1 || !D2)
1681     return true;
1682 
1683   EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1684                                 EC2End = D2->enumerator_end();
1685   for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1686                                      EC1End = D1->enumerator_end();
1687        EC1 != EC1End; ++EC1, ++EC2) {
1688     if (EC2 == EC2End) {
1689       if (Context.Complain) {
1690         Context.Diag2(D2->getLocation(),
1691                       Context.getApplicableDiagnostic(
1692                           diag::err_odr_tag_type_inconsistent))
1693             << Context.ToCtx.getTypeDeclType(D2);
1694         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1695             << EC1->getDeclName() << toString(EC1->getInitVal(), 10);
1696         Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1697       }
1698       return false;
1699     }
1700 
1701     llvm::APSInt Val1 = EC1->getInitVal();
1702     llvm::APSInt Val2 = EC2->getInitVal();
1703     if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1704         !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1705       if (Context.Complain) {
1706         Context.Diag2(D2->getLocation(),
1707                       Context.getApplicableDiagnostic(
1708                           diag::err_odr_tag_type_inconsistent))
1709             << Context.ToCtx.getTypeDeclType(D2);
1710         Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1711             << EC2->getDeclName() << toString(EC2->getInitVal(), 10);
1712         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1713             << EC1->getDeclName() << toString(EC1->getInitVal(), 10);
1714       }
1715       return false;
1716     }
1717   }
1718 
1719   if (EC2 != EC2End) {
1720     if (Context.Complain) {
1721       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1722                                            diag::err_odr_tag_type_inconsistent))
1723           << Context.ToCtx.getTypeDeclType(D2);
1724       Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1725           << EC2->getDeclName() << toString(EC2->getInitVal(), 10);
1726       Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1727     }
1728     return false;
1729   }
1730 
1731   return true;
1732 }
1733 
1734 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1735                                      TemplateParameterList *Params1,
1736                                      TemplateParameterList *Params2) {
1737   if (Params1->size() != Params2->size()) {
1738     if (Context.Complain) {
1739       Context.Diag2(Params2->getTemplateLoc(),
1740                     Context.getApplicableDiagnostic(
1741                         diag::err_odr_different_num_template_parameters))
1742           << Params1->size() << Params2->size();
1743       Context.Diag1(Params1->getTemplateLoc(),
1744                     diag::note_odr_template_parameter_list);
1745     }
1746     return false;
1747   }
1748 
1749   for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1750     if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1751       if (Context.Complain) {
1752         Context.Diag2(Params2->getParam(I)->getLocation(),
1753                       Context.getApplicableDiagnostic(
1754                           diag::err_odr_different_template_parameter_kind));
1755         Context.Diag1(Params1->getParam(I)->getLocation(),
1756                       diag::note_odr_template_parameter_here);
1757       }
1758       return false;
1759     }
1760 
1761     if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1762                                   Params2->getParam(I)))
1763       return false;
1764   }
1765 
1766   return true;
1767 }
1768 
1769 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1770                                      TemplateTypeParmDecl *D1,
1771                                      TemplateTypeParmDecl *D2) {
1772   if (D1->isParameterPack() != D2->isParameterPack()) {
1773     if (Context.Complain) {
1774       Context.Diag2(D2->getLocation(),
1775                     Context.getApplicableDiagnostic(
1776                         diag::err_odr_parameter_pack_non_pack))
1777           << D2->isParameterPack();
1778       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1779           << D1->isParameterPack();
1780     }
1781     return false;
1782   }
1783 
1784   return true;
1785 }
1786 
1787 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1788                                      NonTypeTemplateParmDecl *D1,
1789                                      NonTypeTemplateParmDecl *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   // Check types.
1803   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1804     if (Context.Complain) {
1805       Context.Diag2(D2->getLocation(),
1806                     Context.getApplicableDiagnostic(
1807                         diag::err_odr_non_type_parameter_type_inconsistent))
1808           << D2->getType() << D1->getType();
1809       Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1810           << D1->getType();
1811     }
1812     return false;
1813   }
1814 
1815   return true;
1816 }
1817 
1818 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1819                                      TemplateTemplateParmDecl *D1,
1820                                      TemplateTemplateParmDecl *D2) {
1821   if (D1->isParameterPack() != D2->isParameterPack()) {
1822     if (Context.Complain) {
1823       Context.Diag2(D2->getLocation(),
1824                     Context.getApplicableDiagnostic(
1825                         diag::err_odr_parameter_pack_non_pack))
1826           << D2->isParameterPack();
1827       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1828           << D1->isParameterPack();
1829     }
1830     return false;
1831   }
1832 
1833   // Check template parameter lists.
1834   return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1835                                   D2->getTemplateParameters());
1836 }
1837 
1838 static bool IsTemplateDeclCommonStructurallyEquivalent(
1839     StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1840   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1841     return false;
1842   if (!D1->getIdentifier()) // Special name
1843     if (D1->getNameAsString() != D2->getNameAsString())
1844       return false;
1845   return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1846                                   D2->getTemplateParameters());
1847 }
1848 
1849 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1850                                      ClassTemplateDecl *D1,
1851                                      ClassTemplateDecl *D2) {
1852   // Check template parameters.
1853   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1854     return false;
1855 
1856   // Check the templated declaration.
1857   return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1858                                   D2->getTemplatedDecl());
1859 }
1860 
1861 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1862                                      FunctionTemplateDecl *D1,
1863                                      FunctionTemplateDecl *D2) {
1864   // Check template parameters.
1865   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1866     return false;
1867 
1868   // Check the templated declaration.
1869   return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1870                                   D2->getTemplatedDecl()->getType());
1871 }
1872 
1873 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1874                                      ConceptDecl *D1,
1875                                      ConceptDecl *D2) {
1876   // Check template parameters.
1877   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1878     return false;
1879 
1880   // Check the constraint expression.
1881   return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),
1882                                   D2->getConstraintExpr());
1883 }
1884 
1885 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1886                                      FriendDecl *D1, FriendDecl *D2) {
1887   if ((D1->getFriendType() && D2->getFriendDecl()) ||
1888       (D1->getFriendDecl() && D2->getFriendType())) {
1889       return false;
1890   }
1891   if (D1->getFriendType() && D2->getFriendType())
1892     return IsStructurallyEquivalent(Context,
1893                                     D1->getFriendType()->getType(),
1894                                     D2->getFriendType()->getType());
1895   if (D1->getFriendDecl() && D2->getFriendDecl())
1896     return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1897                                     D2->getFriendDecl());
1898   return false;
1899 }
1900 
1901 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1902                                      TypedefNameDecl *D1, TypedefNameDecl *D2) {
1903   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1904     return false;
1905 
1906   return IsStructurallyEquivalent(Context, D1->getUnderlyingType(),
1907                                   D2->getUnderlyingType());
1908 }
1909 
1910 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1911                                      FunctionDecl *D1, FunctionDecl *D2) {
1912   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1913     return false;
1914 
1915   if (D1->isOverloadedOperator()) {
1916     if (!D2->isOverloadedOperator())
1917       return false;
1918     if (D1->getOverloadedOperator() != D2->getOverloadedOperator())
1919       return false;
1920   }
1921 
1922   // FIXME: Consider checking for function attributes as well.
1923   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1924     return false;
1925 
1926   return true;
1927 }
1928 
1929 /// Determine structural equivalence of two declarations.
1930 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1931                                      Decl *D1, Decl *D2) {
1932   // FIXME: Check for known structural equivalences via a callback of some sort.
1933 
1934   D1 = D1->getCanonicalDecl();
1935   D2 = D2->getCanonicalDecl();
1936   std::pair<Decl *, Decl *> P{D1, D2};
1937 
1938   // Check whether we already know that these two declarations are not
1939   // structurally equivalent.
1940   if (Context.NonEquivalentDecls.count(P))
1941     return false;
1942 
1943   // Check if a check for these declarations is already pending.
1944   // If yes D1 and D2 will be checked later (from DeclsToCheck),
1945   // or these are already checked (and equivalent).
1946   bool Inserted = Context.VisitedDecls.insert(P).second;
1947   if (!Inserted)
1948     return true;
1949 
1950   Context.DeclsToCheck.push(P);
1951 
1952   return true;
1953 }
1954 
1955 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1956                                                       unsigned DiagID) {
1957   assert(Complain && "Not allowed to complain");
1958   if (LastDiagFromC2)
1959     FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1960   LastDiagFromC2 = false;
1961   return FromCtx.getDiagnostics().Report(Loc, DiagID);
1962 }
1963 
1964 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1965                                                       unsigned DiagID) {
1966   assert(Complain && "Not allowed to complain");
1967   if (!LastDiagFromC2)
1968     ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1969   LastDiagFromC2 = true;
1970   return ToCtx.getDiagnostics().Report(Loc, DiagID);
1971 }
1972 
1973 Optional<unsigned>
1974 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1975   ASTContext &Context = Anon->getASTContext();
1976   QualType AnonTy = Context.getRecordType(Anon);
1977 
1978   const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1979   if (!Owner)
1980     return None;
1981 
1982   unsigned Index = 0;
1983   for (const auto *D : Owner->noload_decls()) {
1984     const auto *F = dyn_cast<FieldDecl>(D);
1985     if (!F)
1986       continue;
1987 
1988     if (F->isAnonymousStructOrUnion()) {
1989       if (Context.hasSameType(F->getType(), AnonTy))
1990         break;
1991       ++Index;
1992       continue;
1993     }
1994 
1995     // If the field looks like this:
1996     // struct { ... } A;
1997     QualType FieldType = F->getType();
1998     // In case of nested structs.
1999     while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
2000       FieldType = ElabType->getNamedType();
2001 
2002     if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
2003       const RecordDecl *RecDecl = RecType->getDecl();
2004       if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
2005         if (Context.hasSameType(FieldType, AnonTy))
2006           break;
2007         ++Index;
2008         continue;
2009       }
2010     }
2011   }
2012 
2013   return Index;
2014 }
2015 
2016 unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
2017     unsigned ErrorDiagnostic) {
2018   if (ErrorOnTagTypeMismatch)
2019     return ErrorDiagnostic;
2020 
2021   switch (ErrorDiagnostic) {
2022   case diag::err_odr_variable_type_inconsistent:
2023     return diag::warn_odr_variable_type_inconsistent;
2024   case diag::err_odr_variable_multiple_def:
2025     return diag::warn_odr_variable_multiple_def;
2026   case diag::err_odr_function_type_inconsistent:
2027     return diag::warn_odr_function_type_inconsistent;
2028   case diag::err_odr_tag_type_inconsistent:
2029     return diag::warn_odr_tag_type_inconsistent;
2030   case diag::err_odr_field_type_inconsistent:
2031     return diag::warn_odr_field_type_inconsistent;
2032   case diag::err_odr_ivar_type_inconsistent:
2033     return diag::warn_odr_ivar_type_inconsistent;
2034   case diag::err_odr_objc_superclass_inconsistent:
2035     return diag::warn_odr_objc_superclass_inconsistent;
2036   case diag::err_odr_objc_method_result_type_inconsistent:
2037     return diag::warn_odr_objc_method_result_type_inconsistent;
2038   case diag::err_odr_objc_method_num_params_inconsistent:
2039     return diag::warn_odr_objc_method_num_params_inconsistent;
2040   case diag::err_odr_objc_method_param_type_inconsistent:
2041     return diag::warn_odr_objc_method_param_type_inconsistent;
2042   case diag::err_odr_objc_method_variadic_inconsistent:
2043     return diag::warn_odr_objc_method_variadic_inconsistent;
2044   case diag::err_odr_objc_property_type_inconsistent:
2045     return diag::warn_odr_objc_property_type_inconsistent;
2046   case diag::err_odr_objc_property_impl_kind_inconsistent:
2047     return diag::warn_odr_objc_property_impl_kind_inconsistent;
2048   case diag::err_odr_objc_synthesize_ivar_inconsistent:
2049     return diag::warn_odr_objc_synthesize_ivar_inconsistent;
2050   case diag::err_odr_different_num_template_parameters:
2051     return diag::warn_odr_different_num_template_parameters;
2052   case diag::err_odr_different_template_parameter_kind:
2053     return diag::warn_odr_different_template_parameter_kind;
2054   case diag::err_odr_parameter_pack_non_pack:
2055     return diag::warn_odr_parameter_pack_non_pack;
2056   case diag::err_odr_non_type_parameter_type_inconsistent:
2057     return diag::warn_odr_non_type_parameter_type_inconsistent;
2058   }
2059   llvm_unreachable("Diagnostic kind not handled in preceding switch");
2060 }
2061 
2062 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
2063 
2064   // Ensure that the implementation functions (all static functions in this TU)
2065   // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
2066   // because that will wreak havoc the internal state (DeclsToCheck and
2067   // VisitedDecls members) and can cause faulty behaviour.
2068   // In other words: Do not start a graph search from a new node with the
2069   // internal data of another search in progress.
2070   // FIXME: Better encapsulation and separation of internal and public
2071   // functionality.
2072   assert(DeclsToCheck.empty());
2073   assert(VisitedDecls.empty());
2074 
2075   if (!::IsStructurallyEquivalent(*this, D1, D2))
2076     return false;
2077 
2078   return !Finish();
2079 }
2080 
2081 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
2082   assert(DeclsToCheck.empty());
2083   assert(VisitedDecls.empty());
2084   if (!::IsStructurallyEquivalent(*this, T1, T2))
2085     return false;
2086 
2087   return !Finish();
2088 }
2089 
2090 bool StructuralEquivalenceContext::IsEquivalent(Stmt *S1, Stmt *S2) {
2091   assert(DeclsToCheck.empty());
2092   assert(VisitedDecls.empty());
2093   if (!::IsStructurallyEquivalent(*this, S1, S2))
2094     return false;
2095 
2096   return !Finish();
2097 }
2098 
2099 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
2100   // Check for equivalent described template.
2101   TemplateDecl *Template1 = D1->getDescribedTemplate();
2102   TemplateDecl *Template2 = D2->getDescribedTemplate();
2103   if ((Template1 != nullptr) != (Template2 != nullptr))
2104     return false;
2105   if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
2106     return false;
2107 
2108   // FIXME: Move check for identifier names into this function.
2109 
2110   return true;
2111 }
2112 
2113 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
2114     Decl *D1, Decl *D2) {
2115 
2116   // Kind mismatch.
2117   if (D1->getKind() != D2->getKind())
2118     return false;
2119 
2120   // Cast the Decls to their actual subclass so that the right overload of
2121   // IsStructurallyEquivalent is called.
2122   switch (D1->getKind()) {
2123 #define ABSTRACT_DECL(DECL)
2124 #define DECL(DERIVED, BASE)                                                    \
2125   case Decl::Kind::DERIVED:                                                    \
2126     return ::IsStructurallyEquivalent(*this, static_cast<DERIVED##Decl *>(D1), \
2127                                       static_cast<DERIVED##Decl *>(D2));
2128 #include "clang/AST/DeclNodes.inc"
2129   }
2130   return true;
2131 }
2132 
2133 bool StructuralEquivalenceContext::Finish() {
2134   while (!DeclsToCheck.empty()) {
2135     // Check the next declaration.
2136     std::pair<Decl *, Decl *> P = DeclsToCheck.front();
2137     DeclsToCheck.pop();
2138 
2139     Decl *D1 = P.first;
2140     Decl *D2 = P.second;
2141 
2142     bool Equivalent =
2143         CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
2144 
2145     if (!Equivalent) {
2146       // Note that these two declarations are not equivalent (and we already
2147       // know about it).
2148       NonEquivalentDecls.insert(P);
2149 
2150       return true;
2151     }
2152   }
2153 
2154   return false;
2155 }
2156