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