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   } // end switch
953 
954   return true;
955 }
956 
957 /// Determine structural equivalence of two fields.
958 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
959                                      FieldDecl *Field1, FieldDecl *Field2) {
960   const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
961 
962   // For anonymous structs/unions, match up the anonymous struct/union type
963   // declarations directly, so that we don't go off searching for anonymous
964   // types
965   if (Field1->isAnonymousStructOrUnion() &&
966       Field2->isAnonymousStructOrUnion()) {
967     RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
968     RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
969     return IsStructurallyEquivalent(Context, D1, D2);
970   }
971 
972   // Check for equivalent field names.
973   IdentifierInfo *Name1 = Field1->getIdentifier();
974   IdentifierInfo *Name2 = Field2->getIdentifier();
975   if (!::IsStructurallyEquivalent(Name1, Name2)) {
976     if (Context.Complain) {
977       Context.Diag2(
978           Owner2->getLocation(),
979           Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
980           << Context.ToCtx.getTypeDeclType(Owner2);
981       Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
982           << Field2->getDeclName();
983       Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
984           << Field1->getDeclName();
985     }
986     return false;
987   }
988 
989   if (!IsStructurallyEquivalent(Context, Field1->getType(),
990                                 Field2->getType())) {
991     if (Context.Complain) {
992       Context.Diag2(
993           Owner2->getLocation(),
994           Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
995           << Context.ToCtx.getTypeDeclType(Owner2);
996       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
997           << Field2->getDeclName() << Field2->getType();
998       Context.Diag1(Field1->getLocation(), diag::note_odr_field)
999           << Field1->getDeclName() << Field1->getType();
1000     }
1001     return false;
1002   }
1003 
1004   if (Field1->isBitField() != Field2->isBitField()) {
1005     if (Context.Complain) {
1006       Context.Diag2(
1007           Owner2->getLocation(),
1008           Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1009           << Context.ToCtx.getTypeDeclType(Owner2);
1010       if (Field1->isBitField()) {
1011         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
1012             << Field1->getDeclName() << Field1->getType()
1013             << Field1->getBitWidthValue(Context.FromCtx);
1014         Context.Diag2(Field2->getLocation(), diag::note_odr_not_bit_field)
1015             << Field2->getDeclName();
1016       } else {
1017         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
1018             << Field2->getDeclName() << Field2->getType()
1019             << Field2->getBitWidthValue(Context.ToCtx);
1020         Context.Diag1(Field1->getLocation(), diag::note_odr_not_bit_field)
1021             << Field1->getDeclName();
1022       }
1023     }
1024     return false;
1025   }
1026 
1027   if (Field1->isBitField()) {
1028     // Make sure that the bit-fields are the same length.
1029     unsigned Bits1 = Field1->getBitWidthValue(Context.FromCtx);
1030     unsigned Bits2 = Field2->getBitWidthValue(Context.ToCtx);
1031 
1032     if (Bits1 != Bits2) {
1033       if (Context.Complain) {
1034         Context.Diag2(Owner2->getLocation(),
1035                       Context.getApplicableDiagnostic(
1036                           diag::err_odr_tag_type_inconsistent))
1037             << Context.ToCtx.getTypeDeclType(Owner2);
1038         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
1039             << Field2->getDeclName() << Field2->getType() << Bits2;
1040         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
1041             << Field1->getDeclName() << Field1->getType() << Bits1;
1042       }
1043       return false;
1044     }
1045   }
1046 
1047   return true;
1048 }
1049 
1050 /// Determine structural equivalence of two methods.
1051 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1052                                      CXXMethodDecl *Method1,
1053                                      CXXMethodDecl *Method2) {
1054   bool PropertiesEqual =
1055       Method1->getDeclKind() == Method2->getDeclKind() &&
1056       Method1->getRefQualifier() == Method2->getRefQualifier() &&
1057       Method1->getAccess() == Method2->getAccess() &&
1058       Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
1059       Method1->isStatic() == Method2->isStatic() &&
1060       Method1->isConst() == Method2->isConst() &&
1061       Method1->isVolatile() == Method2->isVolatile() &&
1062       Method1->isVirtual() == Method2->isVirtual() &&
1063       Method1->isPure() == Method2->isPure() &&
1064       Method1->isDefaulted() == Method2->isDefaulted() &&
1065       Method1->isDeleted() == Method2->isDeleted();
1066   if (!PropertiesEqual)
1067     return false;
1068   // FIXME: Check for 'final'.
1069 
1070   if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
1071     auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
1072     if (!Constructor1->getExplicitSpecifier().isEquivalent(
1073             Constructor2->getExplicitSpecifier()))
1074       return false;
1075   }
1076 
1077   if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
1078     auto *Conversion2 = cast<CXXConversionDecl>(Method2);
1079     if (!Conversion1->getExplicitSpecifier().isEquivalent(
1080             Conversion2->getExplicitSpecifier()))
1081       return false;
1082     if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
1083                                   Conversion2->getConversionType()))
1084       return false;
1085   }
1086 
1087   const IdentifierInfo *Name1 = Method1->getIdentifier();
1088   const IdentifierInfo *Name2 = Method2->getIdentifier();
1089   if (!::IsStructurallyEquivalent(Name1, Name2)) {
1090     return false;
1091     // TODO: Names do not match, add warning like at check for FieldDecl.
1092   }
1093 
1094   // Check the prototypes.
1095   if (!::IsStructurallyEquivalent(Context,
1096                                   Method1->getType(), Method2->getType()))
1097     return false;
1098 
1099   return true;
1100 }
1101 
1102 /// Determine structural equivalence of two lambda classes.
1103 static bool
1104 IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
1105                                 CXXRecordDecl *D1, CXXRecordDecl *D2) {
1106   assert(D1->isLambda() && D2->isLambda() &&
1107          "Must be called on lambda classes");
1108   if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(),
1109                                 D2->getLambdaCallOperator()))
1110     return false;
1111 
1112   return true;
1113 }
1114 
1115 /// Determine structural equivalence of two records.
1116 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1117                                      RecordDecl *D1, RecordDecl *D2) {
1118   if (D1->isUnion() != D2->isUnion()) {
1119     if (Context.Complain) {
1120       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1121                                            diag::err_odr_tag_type_inconsistent))
1122           << Context.ToCtx.getTypeDeclType(D2);
1123       Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1124           << D1->getDeclName() << (unsigned)D1->getTagKind();
1125     }
1126     return false;
1127   }
1128 
1129   if (!D1->getDeclName() && !D2->getDeclName()) {
1130     // If both anonymous structs/unions are in a record context, make sure
1131     // they occur in the same location in the context records.
1132     if (Optional<unsigned> Index1 =
1133             StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
1134       if (Optional<unsigned> Index2 =
1135               StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1136                   D2)) {
1137         if (*Index1 != *Index2)
1138           return false;
1139       }
1140     }
1141   }
1142 
1143   // If both declarations are class template specializations, we know
1144   // the ODR applies, so check the template and template arguments.
1145   const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
1146   const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
1147   if (Spec1 && Spec2) {
1148     // Check that the specialized templates are the same.
1149     if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1150                                   Spec2->getSpecializedTemplate()))
1151       return false;
1152 
1153     // Check that the template arguments are the same.
1154     if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1155       return false;
1156 
1157     for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1158       if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
1159                                     Spec2->getTemplateArgs().get(I)))
1160         return false;
1161   }
1162   // If one is a class template specialization and the other is not, these
1163   // structures are different.
1164   else if (Spec1 || Spec2)
1165     return false;
1166 
1167   // Compare the definitions of these two records. If either or both are
1168   // incomplete (i.e. it is a forward decl), we assume that they are
1169   // equivalent.
1170   D1 = D1->getDefinition();
1171   D2 = D2->getDefinition();
1172   if (!D1 || !D2)
1173     return true;
1174 
1175   // If any of the records has external storage and we do a minimal check (or
1176   // AST import) we assume they are equivalent. (If we didn't have this
1177   // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1178   // another AST import which in turn would call the structural equivalency
1179   // check again and finally we'd have an improper result.)
1180   if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1181     if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
1182       return true;
1183 
1184   // If one definition is currently being defined, we do not compare for
1185   // equality and we assume that the decls are equal.
1186   if (D1->isBeingDefined() || D2->isBeingDefined())
1187     return true;
1188 
1189   if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
1190     if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
1191       if (D1CXX->hasExternalLexicalStorage() &&
1192           !D1CXX->isCompleteDefinition()) {
1193         D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1194       }
1195 
1196       if (D1CXX->isLambda() != D2CXX->isLambda())
1197         return false;
1198       if (D1CXX->isLambda()) {
1199         if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))
1200           return false;
1201       }
1202 
1203       if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1204         if (Context.Complain) {
1205           Context.Diag2(D2->getLocation(),
1206                         Context.getApplicableDiagnostic(
1207                             diag::err_odr_tag_type_inconsistent))
1208               << Context.ToCtx.getTypeDeclType(D2);
1209           Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1210               << D2CXX->getNumBases();
1211           Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1212               << D1CXX->getNumBases();
1213         }
1214         return false;
1215       }
1216 
1217       // Check the base classes.
1218       for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1219                                               BaseEnd1 = D1CXX->bases_end(),
1220                                               Base2 = D2CXX->bases_begin();
1221            Base1 != BaseEnd1; ++Base1, ++Base2) {
1222         if (!IsStructurallyEquivalent(Context, Base1->getType(),
1223                                       Base2->getType())) {
1224           if (Context.Complain) {
1225             Context.Diag2(D2->getLocation(),
1226                           Context.getApplicableDiagnostic(
1227                               diag::err_odr_tag_type_inconsistent))
1228                 << Context.ToCtx.getTypeDeclType(D2);
1229             Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1230                 << Base2->getType() << Base2->getSourceRange();
1231             Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1232                 << Base1->getType() << Base1->getSourceRange();
1233           }
1234           return false;
1235         }
1236 
1237         // Check virtual vs. non-virtual inheritance mismatch.
1238         if (Base1->isVirtual() != Base2->isVirtual()) {
1239           if (Context.Complain) {
1240             Context.Diag2(D2->getLocation(),
1241                           Context.getApplicableDiagnostic(
1242                               diag::err_odr_tag_type_inconsistent))
1243                 << Context.ToCtx.getTypeDeclType(D2);
1244             Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1245                 << Base2->isVirtual() << Base2->getSourceRange();
1246             Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1247                 << Base1->isVirtual() << Base1->getSourceRange();
1248           }
1249           return false;
1250         }
1251       }
1252 
1253       // Check the friends for consistency.
1254       CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1255                                      Friend2End = D2CXX->friend_end();
1256       for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1257                                           Friend1End = D1CXX->friend_end();
1258            Friend1 != Friend1End; ++Friend1, ++Friend2) {
1259         if (Friend2 == Friend2End) {
1260           if (Context.Complain) {
1261             Context.Diag2(D2->getLocation(),
1262                           Context.getApplicableDiagnostic(
1263                               diag::err_odr_tag_type_inconsistent))
1264                 << Context.ToCtx.getTypeDeclType(D2CXX);
1265             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1266             Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1267           }
1268           return false;
1269         }
1270 
1271         if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1272           if (Context.Complain) {
1273             Context.Diag2(D2->getLocation(),
1274                           Context.getApplicableDiagnostic(
1275                               diag::err_odr_tag_type_inconsistent))
1276                 << Context.ToCtx.getTypeDeclType(D2CXX);
1277             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1278             Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1279           }
1280           return false;
1281         }
1282       }
1283 
1284       if (Friend2 != Friend2End) {
1285         if (Context.Complain) {
1286           Context.Diag2(D2->getLocation(),
1287                         Context.getApplicableDiagnostic(
1288                             diag::err_odr_tag_type_inconsistent))
1289               << Context.ToCtx.getTypeDeclType(D2);
1290           Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1291           Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1292         }
1293         return false;
1294       }
1295     } else if (D1CXX->getNumBases() > 0) {
1296       if (Context.Complain) {
1297         Context.Diag2(D2->getLocation(),
1298                       Context.getApplicableDiagnostic(
1299                           diag::err_odr_tag_type_inconsistent))
1300             << Context.ToCtx.getTypeDeclType(D2);
1301         const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1302         Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1303             << Base1->getType() << Base1->getSourceRange();
1304         Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1305       }
1306       return false;
1307     }
1308   }
1309 
1310   // Check the fields for consistency.
1311   RecordDecl::field_iterator Field2 = D2->field_begin(),
1312                              Field2End = D2->field_end();
1313   for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1314                                   Field1End = D1->field_end();
1315        Field1 != Field1End; ++Field1, ++Field2) {
1316     if (Field2 == Field2End) {
1317       if (Context.Complain) {
1318         Context.Diag2(D2->getLocation(),
1319                       Context.getApplicableDiagnostic(
1320                           diag::err_odr_tag_type_inconsistent))
1321             << Context.ToCtx.getTypeDeclType(D2);
1322         Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1323             << Field1->getDeclName() << Field1->getType();
1324         Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1325       }
1326       return false;
1327     }
1328 
1329     if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1330       return false;
1331   }
1332 
1333   if (Field2 != Field2End) {
1334     if (Context.Complain) {
1335       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1336                                            diag::err_odr_tag_type_inconsistent))
1337           << Context.ToCtx.getTypeDeclType(D2);
1338       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1339           << Field2->getDeclName() << Field2->getType();
1340       Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1341     }
1342     return false;
1343   }
1344 
1345   return true;
1346 }
1347 
1348 /// Determine structural equivalence of two enums.
1349 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1350                                      EnumDecl *D1, EnumDecl *D2) {
1351 
1352   // Compare the definitions of these two enums. If either or both are
1353   // incomplete (i.e. forward declared), we assume that they are equivalent.
1354   D1 = D1->getDefinition();
1355   D2 = D2->getDefinition();
1356   if (!D1 || !D2)
1357     return true;
1358 
1359   EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1360                                 EC2End = D2->enumerator_end();
1361   for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1362                                      EC1End = D1->enumerator_end();
1363        EC1 != EC1End; ++EC1, ++EC2) {
1364     if (EC2 == EC2End) {
1365       if (Context.Complain) {
1366         Context.Diag2(D2->getLocation(),
1367                       Context.getApplicableDiagnostic(
1368                           diag::err_odr_tag_type_inconsistent))
1369             << Context.ToCtx.getTypeDeclType(D2);
1370         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1371             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1372         Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1373       }
1374       return false;
1375     }
1376 
1377     llvm::APSInt Val1 = EC1->getInitVal();
1378     llvm::APSInt Val2 = EC2->getInitVal();
1379     if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1380         !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1381       if (Context.Complain) {
1382         Context.Diag2(D2->getLocation(),
1383                       Context.getApplicableDiagnostic(
1384                           diag::err_odr_tag_type_inconsistent))
1385             << Context.ToCtx.getTypeDeclType(D2);
1386         Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1387             << EC2->getDeclName() << EC2->getInitVal().toString(10);
1388         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1389             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1390       }
1391       return false;
1392     }
1393   }
1394 
1395   if (EC2 != EC2End) {
1396     if (Context.Complain) {
1397       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1398                                            diag::err_odr_tag_type_inconsistent))
1399           << Context.ToCtx.getTypeDeclType(D2);
1400       Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1401           << EC2->getDeclName() << EC2->getInitVal().toString(10);
1402       Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1403     }
1404     return false;
1405   }
1406 
1407   return true;
1408 }
1409 
1410 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1411                                      TemplateParameterList *Params1,
1412                                      TemplateParameterList *Params2) {
1413   if (Params1->size() != Params2->size()) {
1414     if (Context.Complain) {
1415       Context.Diag2(Params2->getTemplateLoc(),
1416                     Context.getApplicableDiagnostic(
1417                         diag::err_odr_different_num_template_parameters))
1418           << Params1->size() << Params2->size();
1419       Context.Diag1(Params1->getTemplateLoc(),
1420                     diag::note_odr_template_parameter_list);
1421     }
1422     return false;
1423   }
1424 
1425   for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1426     if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1427       if (Context.Complain) {
1428         Context.Diag2(Params2->getParam(I)->getLocation(),
1429                       Context.getApplicableDiagnostic(
1430                           diag::err_odr_different_template_parameter_kind));
1431         Context.Diag1(Params1->getParam(I)->getLocation(),
1432                       diag::note_odr_template_parameter_here);
1433       }
1434       return false;
1435     }
1436 
1437     if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1438                                   Params2->getParam(I)))
1439       return false;
1440   }
1441 
1442   return true;
1443 }
1444 
1445 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1446                                      TemplateTypeParmDecl *D1,
1447                                      TemplateTypeParmDecl *D2) {
1448   if (D1->isParameterPack() != D2->isParameterPack()) {
1449     if (Context.Complain) {
1450       Context.Diag2(D2->getLocation(),
1451                     Context.getApplicableDiagnostic(
1452                         diag::err_odr_parameter_pack_non_pack))
1453           << D2->isParameterPack();
1454       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1455           << D1->isParameterPack();
1456     }
1457     return false;
1458   }
1459 
1460   return true;
1461 }
1462 
1463 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1464                                      NonTypeTemplateParmDecl *D1,
1465                                      NonTypeTemplateParmDecl *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   // Check types.
1479   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1480     if (Context.Complain) {
1481       Context.Diag2(D2->getLocation(),
1482                     Context.getApplicableDiagnostic(
1483                         diag::err_odr_non_type_parameter_type_inconsistent))
1484           << D2->getType() << D1->getType();
1485       Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1486           << D1->getType();
1487     }
1488     return false;
1489   }
1490 
1491   return true;
1492 }
1493 
1494 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1495                                      TemplateTemplateParmDecl *D1,
1496                                      TemplateTemplateParmDecl *D2) {
1497   if (D1->isParameterPack() != D2->isParameterPack()) {
1498     if (Context.Complain) {
1499       Context.Diag2(D2->getLocation(),
1500                     Context.getApplicableDiagnostic(
1501                         diag::err_odr_parameter_pack_non_pack))
1502           << D2->isParameterPack();
1503       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1504           << D1->isParameterPack();
1505     }
1506     return false;
1507   }
1508 
1509   // Check template parameter lists.
1510   return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1511                                   D2->getTemplateParameters());
1512 }
1513 
1514 static bool IsTemplateDeclCommonStructurallyEquivalent(
1515     StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1516   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1517     return false;
1518   if (!D1->getIdentifier()) // Special name
1519     if (D1->getNameAsString() != D2->getNameAsString())
1520       return false;
1521   return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1522                                   D2->getTemplateParameters());
1523 }
1524 
1525 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1526                                      ClassTemplateDecl *D1,
1527                                      ClassTemplateDecl *D2) {
1528   // Check template parameters.
1529   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1530     return false;
1531 
1532   // Check the templated declaration.
1533   return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1534                                   D2->getTemplatedDecl());
1535 }
1536 
1537 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1538                                      FunctionTemplateDecl *D1,
1539                                      FunctionTemplateDecl *D2) {
1540   // Check template parameters.
1541   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1542     return false;
1543 
1544   // Check the templated declaration.
1545   return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1546                                   D2->getTemplatedDecl()->getType());
1547 }
1548 
1549 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1550                                      ConceptDecl *D1,
1551                                      ConceptDecl *D2) {
1552   // Check template parameters.
1553   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1554     return false;
1555 
1556   // Check the constraint expression.
1557   return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),
1558                                   D2->getConstraintExpr());
1559 }
1560 
1561 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1562                                      FriendDecl *D1, FriendDecl *D2) {
1563   if ((D1->getFriendType() && D2->getFriendDecl()) ||
1564       (D1->getFriendDecl() && D2->getFriendType())) {
1565       return false;
1566   }
1567   if (D1->getFriendType() && D2->getFriendType())
1568     return IsStructurallyEquivalent(Context,
1569                                     D1->getFriendType()->getType(),
1570                                     D2->getFriendType()->getType());
1571   if (D1->getFriendDecl() && D2->getFriendDecl())
1572     return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1573                                     D2->getFriendDecl());
1574   return false;
1575 }
1576 
1577 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1578                                      FunctionDecl *D1, FunctionDecl *D2) {
1579   // FIXME: Consider checking for function attributes as well.
1580   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1581     return false;
1582 
1583   return true;
1584 }
1585 
1586 /// Determine structural equivalence of two declarations.
1587 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1588                                      Decl *D1, Decl *D2) {
1589   // FIXME: Check for known structural equivalences via a callback of some sort.
1590 
1591   D1 = D1->getCanonicalDecl();
1592   D2 = D2->getCanonicalDecl();
1593   std::pair<Decl *, Decl *> P{D1, D2};
1594 
1595   // Check whether we already know that these two declarations are not
1596   // structurally equivalent.
1597   if (Context.NonEquivalentDecls.count(P))
1598     return false;
1599 
1600   // Check if a check for these declarations is already pending.
1601   // If yes D1 and D2 will be checked later (from DeclsToCheck),
1602   // or these are already checked (and equivalent).
1603   bool Inserted = Context.VisitedDecls.insert(P).second;
1604   if (!Inserted)
1605     return true;
1606 
1607   Context.DeclsToCheck.push(P);
1608 
1609   return true;
1610 }
1611 
1612 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1613                                                       unsigned DiagID) {
1614   assert(Complain && "Not allowed to complain");
1615   if (LastDiagFromC2)
1616     FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1617   LastDiagFromC2 = false;
1618   return FromCtx.getDiagnostics().Report(Loc, DiagID);
1619 }
1620 
1621 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1622                                                       unsigned DiagID) {
1623   assert(Complain && "Not allowed to complain");
1624   if (!LastDiagFromC2)
1625     ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1626   LastDiagFromC2 = true;
1627   return ToCtx.getDiagnostics().Report(Loc, DiagID);
1628 }
1629 
1630 Optional<unsigned>
1631 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1632   ASTContext &Context = Anon->getASTContext();
1633   QualType AnonTy = Context.getRecordType(Anon);
1634 
1635   const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1636   if (!Owner)
1637     return None;
1638 
1639   unsigned Index = 0;
1640   for (const auto *D : Owner->noload_decls()) {
1641     const auto *F = dyn_cast<FieldDecl>(D);
1642     if (!F)
1643       continue;
1644 
1645     if (F->isAnonymousStructOrUnion()) {
1646       if (Context.hasSameType(F->getType(), AnonTy))
1647         break;
1648       ++Index;
1649       continue;
1650     }
1651 
1652     // If the field looks like this:
1653     // struct { ... } A;
1654     QualType FieldType = F->getType();
1655     // In case of nested structs.
1656     while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1657       FieldType = ElabType->getNamedType();
1658 
1659     if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1660       const RecordDecl *RecDecl = RecType->getDecl();
1661       if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1662         if (Context.hasSameType(FieldType, AnonTy))
1663           break;
1664         ++Index;
1665         continue;
1666       }
1667     }
1668   }
1669 
1670   return Index;
1671 }
1672 
1673 unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
1674     unsigned ErrorDiagnostic) {
1675   if (ErrorOnTagTypeMismatch)
1676     return ErrorDiagnostic;
1677 
1678   switch (ErrorDiagnostic) {
1679   case diag::err_odr_variable_type_inconsistent:
1680     return diag::warn_odr_variable_type_inconsistent;
1681   case diag::err_odr_variable_multiple_def:
1682     return diag::warn_odr_variable_multiple_def;
1683   case diag::err_odr_function_type_inconsistent:
1684     return diag::warn_odr_function_type_inconsistent;
1685   case diag::err_odr_tag_type_inconsistent:
1686     return diag::warn_odr_tag_type_inconsistent;
1687   case diag::err_odr_field_type_inconsistent:
1688     return diag::warn_odr_field_type_inconsistent;
1689   case diag::err_odr_ivar_type_inconsistent:
1690     return diag::warn_odr_ivar_type_inconsistent;
1691   case diag::err_odr_objc_superclass_inconsistent:
1692     return diag::warn_odr_objc_superclass_inconsistent;
1693   case diag::err_odr_objc_method_result_type_inconsistent:
1694     return diag::warn_odr_objc_method_result_type_inconsistent;
1695   case diag::err_odr_objc_method_num_params_inconsistent:
1696     return diag::warn_odr_objc_method_num_params_inconsistent;
1697   case diag::err_odr_objc_method_param_type_inconsistent:
1698     return diag::warn_odr_objc_method_param_type_inconsistent;
1699   case diag::err_odr_objc_method_variadic_inconsistent:
1700     return diag::warn_odr_objc_method_variadic_inconsistent;
1701   case diag::err_odr_objc_property_type_inconsistent:
1702     return diag::warn_odr_objc_property_type_inconsistent;
1703   case diag::err_odr_objc_property_impl_kind_inconsistent:
1704     return diag::warn_odr_objc_property_impl_kind_inconsistent;
1705   case diag::err_odr_objc_synthesize_ivar_inconsistent:
1706     return diag::warn_odr_objc_synthesize_ivar_inconsistent;
1707   case diag::err_odr_different_num_template_parameters:
1708     return diag::warn_odr_different_num_template_parameters;
1709   case diag::err_odr_different_template_parameter_kind:
1710     return diag::warn_odr_different_template_parameter_kind;
1711   case diag::err_odr_parameter_pack_non_pack:
1712     return diag::warn_odr_parameter_pack_non_pack;
1713   case diag::err_odr_non_type_parameter_type_inconsistent:
1714     return diag::warn_odr_non_type_parameter_type_inconsistent;
1715   }
1716   llvm_unreachable("Diagnostic kind not handled in preceding switch");
1717 }
1718 
1719 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
1720 
1721   // Ensure that the implementation functions (all static functions in this TU)
1722   // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
1723   // because that will wreak havoc the internal state (DeclsToCheck and
1724   // VisitedDecls members) and can cause faulty behaviour.
1725   // In other words: Do not start a graph search from a new node with the
1726   // internal data of another search in progress.
1727   // FIXME: Better encapsulation and separation of internal and public
1728   // functionality.
1729   assert(DeclsToCheck.empty());
1730   assert(VisitedDecls.empty());
1731 
1732   if (!::IsStructurallyEquivalent(*this, D1, D2))
1733     return false;
1734 
1735   return !Finish();
1736 }
1737 
1738 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
1739   assert(DeclsToCheck.empty());
1740   assert(VisitedDecls.empty());
1741   if (!::IsStructurallyEquivalent(*this, T1, T2))
1742     return false;
1743 
1744   return !Finish();
1745 }
1746 
1747 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
1748   // Check for equivalent described template.
1749   TemplateDecl *Template1 = D1->getDescribedTemplate();
1750   TemplateDecl *Template2 = D2->getDescribedTemplate();
1751   if ((Template1 != nullptr) != (Template2 != nullptr))
1752     return false;
1753   if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
1754     return false;
1755 
1756   // FIXME: Move check for identifier names into this function.
1757 
1758   return true;
1759 }
1760 
1761 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
1762     Decl *D1, Decl *D2) {
1763   // FIXME: Switch on all declaration kinds. For now, we're just going to
1764   // check the obvious ones.
1765   if (auto *Record1 = dyn_cast<RecordDecl>(D1)) {
1766     if (auto *Record2 = dyn_cast<RecordDecl>(D2)) {
1767       // Check for equivalent structure names.
1768       IdentifierInfo *Name1 = Record1->getIdentifier();
1769       if (!Name1 && Record1->getTypedefNameForAnonDecl())
1770         Name1 = Record1->getTypedefNameForAnonDecl()->getIdentifier();
1771       IdentifierInfo *Name2 = Record2->getIdentifier();
1772       if (!Name2 && Record2->getTypedefNameForAnonDecl())
1773         Name2 = Record2->getTypedefNameForAnonDecl()->getIdentifier();
1774       if (!::IsStructurallyEquivalent(Name1, Name2) ||
1775           !::IsStructurallyEquivalent(*this, Record1, Record2))
1776         return false;
1777     } else {
1778       // Record/non-record mismatch.
1779       return false;
1780     }
1781   } else if (auto *Enum1 = dyn_cast<EnumDecl>(D1)) {
1782     if (auto *Enum2 = dyn_cast<EnumDecl>(D2)) {
1783       // Check for equivalent enum names.
1784       IdentifierInfo *Name1 = Enum1->getIdentifier();
1785       if (!Name1 && Enum1->getTypedefNameForAnonDecl())
1786         Name1 = Enum1->getTypedefNameForAnonDecl()->getIdentifier();
1787       IdentifierInfo *Name2 = Enum2->getIdentifier();
1788       if (!Name2 && Enum2->getTypedefNameForAnonDecl())
1789         Name2 = Enum2->getTypedefNameForAnonDecl()->getIdentifier();
1790       if (!::IsStructurallyEquivalent(Name1, Name2) ||
1791           !::IsStructurallyEquivalent(*this, Enum1, Enum2))
1792         return false;
1793     } else {
1794       // Enum/non-enum mismatch
1795       return false;
1796     }
1797   } else if (const auto *Typedef1 = dyn_cast<TypedefNameDecl>(D1)) {
1798     if (const auto *Typedef2 = dyn_cast<TypedefNameDecl>(D2)) {
1799       if (!::IsStructurallyEquivalent(Typedef1->getIdentifier(),
1800                                       Typedef2->getIdentifier()) ||
1801           !::IsStructurallyEquivalent(*this, Typedef1->getUnderlyingType(),
1802                                       Typedef2->getUnderlyingType()))
1803         return false;
1804     } else {
1805       // Typedef/non-typedef mismatch.
1806       return false;
1807     }
1808   } else if (auto *ClassTemplate1 = dyn_cast<ClassTemplateDecl>(D1)) {
1809     if (auto *ClassTemplate2 = dyn_cast<ClassTemplateDecl>(D2)) {
1810       if (!::IsStructurallyEquivalent(*this, ClassTemplate1,
1811                                       ClassTemplate2))
1812         return false;
1813     } else {
1814       // Class template/non-class-template mismatch.
1815       return false;
1816     }
1817   } else if (auto *FunctionTemplate1 = dyn_cast<FunctionTemplateDecl>(D1)) {
1818     if (auto *FunctionTemplate2 = dyn_cast<FunctionTemplateDecl>(D2)) {
1819       if (!::IsStructurallyEquivalent(*this, FunctionTemplate1,
1820                                       FunctionTemplate2))
1821         return false;
1822     } else {
1823       // Class template/non-class-template mismatch.
1824       return false;
1825     }
1826   } else if (auto *ConceptDecl1 = dyn_cast<ConceptDecl>(D1)) {
1827     if (auto *ConceptDecl2 = dyn_cast<ConceptDecl>(D2)) {
1828       if (!::IsStructurallyEquivalent(*this, ConceptDecl1, ConceptDecl2))
1829         return false;
1830     } else {
1831       // Concept/non-concept mismatch.
1832       return false;
1833     }
1834   } else if (auto *TTP1 = dyn_cast<TemplateTypeParmDecl>(D1)) {
1835     if (auto *TTP2 = dyn_cast<TemplateTypeParmDecl>(D2)) {
1836       if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1837         return false;
1838     } else {
1839       // Kind mismatch.
1840       return false;
1841     }
1842   } else if (auto *NTTP1 = dyn_cast<NonTypeTemplateParmDecl>(D1)) {
1843     if (auto *NTTP2 = dyn_cast<NonTypeTemplateParmDecl>(D2)) {
1844       if (!::IsStructurallyEquivalent(*this, NTTP1, NTTP2))
1845         return false;
1846     } else {
1847       // Kind mismatch.
1848       return false;
1849     }
1850   } else if (auto *TTP1 = dyn_cast<TemplateTemplateParmDecl>(D1)) {
1851     if (auto *TTP2 = dyn_cast<TemplateTemplateParmDecl>(D2)) {
1852       if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1853         return false;
1854     } else {
1855       // Kind mismatch.
1856       return false;
1857     }
1858   } else if (auto *MD1 = dyn_cast<CXXMethodDecl>(D1)) {
1859     if (auto *MD2 = dyn_cast<CXXMethodDecl>(D2)) {
1860       if (!::IsStructurallyEquivalent(*this, MD1, MD2))
1861         return false;
1862     } else {
1863       // Kind mismatch.
1864       return false;
1865     }
1866   } else if (FunctionDecl *FD1 = dyn_cast<FunctionDecl>(D1)) {
1867     if (FunctionDecl *FD2 = dyn_cast<FunctionDecl>(D2)) {
1868       if (FD1->isOverloadedOperator()) {
1869         if (!FD2->isOverloadedOperator())
1870           return false;
1871         if (FD1->getOverloadedOperator() != FD2->getOverloadedOperator())
1872           return false;
1873       }
1874       if (!::IsStructurallyEquivalent(FD1->getIdentifier(),
1875                                       FD2->getIdentifier()))
1876         return false;
1877       if (!::IsStructurallyEquivalent(*this, FD1, FD2))
1878         return false;
1879     } else {
1880       // Kind mismatch.
1881       return false;
1882     }
1883   } else if (FriendDecl *FrD1 = dyn_cast<FriendDecl>(D1)) {
1884     if (FriendDecl *FrD2 = dyn_cast<FriendDecl>(D2)) {
1885         if (!::IsStructurallyEquivalent(*this, FrD1, FrD2))
1886           return false;
1887     } else {
1888       // Kind mismatch.
1889       return false;
1890     }
1891   }
1892 
1893   return true;
1894 }
1895 
1896 bool StructuralEquivalenceContext::Finish() {
1897   while (!DeclsToCheck.empty()) {
1898     // Check the next declaration.
1899     std::pair<Decl *, Decl *> P = DeclsToCheck.front();
1900     DeclsToCheck.pop();
1901 
1902     Decl *D1 = P.first;
1903     Decl *D2 = P.second;
1904 
1905     bool Equivalent =
1906         CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
1907 
1908     if (!Equivalent) {
1909       // Note that these two declarations are not equivalent (and we already
1910       // know about it).
1911       NonEquivalentDecls.insert(P);
1912 
1913       return true;
1914     }
1915   }
1916 
1917   return false;
1918 }
1919