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