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