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   TemplateDecl *TemplateDeclN1 = N1.getAsTemplateDecl();
239   TemplateDecl *TemplateDeclN2 = N2.getAsTemplateDecl();
240   if (TemplateDeclN1 && TemplateDeclN2) {
241     if (!IsStructurallyEquivalent(Context, TemplateDeclN1, TemplateDeclN2))
242       return false;
243     // If the kind is different we compare only the template decl.
244     if (N1.getKind() != N2.getKind())
245       return true;
246   } else if (TemplateDeclN1 || TemplateDeclN2)
247     return false;
248   else if (N1.getKind() != N2.getKind())
249     return false;
250 
251   // Check for special case incompatibilities.
252   switch (N1.getKind()) {
253 
254   case TemplateName::OverloadedTemplate: {
255     OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),
256                               *OS2 = N2.getAsOverloadedTemplate();
257     OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),
258                                         E1 = OS1->end(), E2 = OS2->end();
259     for (; I1 != E1 && I2 != E2; ++I1, ++I2)
260       if (!IsStructurallyEquivalent(Context, *I1, *I2))
261         return false;
262     return I1 == E1 && I2 == E2;
263   }
264 
265   case TemplateName::AssumedTemplate: {
266     AssumedTemplateStorage *TN1 = N1.getAsAssumedTemplateName(),
267                            *TN2 = N1.getAsAssumedTemplateName();
268     return TN1->getDeclName() == TN2->getDeclName();
269   }
270 
271   case TemplateName::DependentTemplate: {
272     DependentTemplateName *DN1 = N1.getAsDependentTemplateName(),
273                           *DN2 = N2.getAsDependentTemplateName();
274     if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
275                                   DN2->getQualifier()))
276       return false;
277     if (DN1->isIdentifier() && DN2->isIdentifier())
278       return IsStructurallyEquivalent(DN1->getIdentifier(),
279                                       DN2->getIdentifier());
280     else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
281       return DN1->getOperator() == DN2->getOperator();
282     return false;
283   }
284 
285   case TemplateName::SubstTemplateTemplateParmPack: {
286     SubstTemplateTemplateParmPackStorage
287         *P1 = N1.getAsSubstTemplateTemplateParmPack(),
288         *P2 = N2.getAsSubstTemplateTemplateParmPack();
289     return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
290                                     P2->getArgumentPack()) &&
291            IsStructurallyEquivalent(Context, P1->getParameterPack(),
292                                     P2->getParameterPack());
293   }
294 
295    case TemplateName::Template:
296    case TemplateName::QualifiedTemplate:
297    case TemplateName::SubstTemplateTemplateParm:
298      // It is sufficient to check value of getAsTemplateDecl.
299      break;
300 
301   }
302 
303   return true;
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     auto *Auto1 = cast<AutoType>(T1);
734     auto *Auto2 = cast<AutoType>(T2);
735     if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),
736                                   Auto2->getDeducedType()))
737       return false;
738     if (Auto1->isConstrained() != Auto2->isConstrained())
739       return false;
740     if (Auto1->isConstrained()) {
741       if (Auto1->getTypeConstraintConcept() !=
742           Auto2->getTypeConstraintConcept())
743         return false;
744       ArrayRef<TemplateArgument> Auto1Args =
745           Auto1->getTypeConstraintArguments();
746       ArrayRef<TemplateArgument> Auto2Args =
747           Auto2->getTypeConstraintArguments();
748       if (Auto1Args.size() != Auto2Args.size())
749         return false;
750       for (unsigned I = 0, N = Auto1Args.size(); I != N; ++I) {
751         if (!IsStructurallyEquivalent(Context, Auto1Args[I], Auto2Args[I]))
752           return false;
753       }
754     }
755     break;
756   }
757 
758   case Type::DeducedTemplateSpecialization: {
759     const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
760     const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
761     if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
762                                   DT2->getTemplateName()))
763       return false;
764     if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
765                                   DT2->getDeducedType()))
766       return false;
767     break;
768   }
769 
770   case Type::Record:
771   case Type::Enum:
772     if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
773                                   cast<TagType>(T2)->getDecl()))
774       return false;
775     break;
776 
777   case Type::TemplateTypeParm: {
778     const auto *Parm1 = cast<TemplateTypeParmType>(T1);
779     const auto *Parm2 = cast<TemplateTypeParmType>(T2);
780     if (Parm1->getDepth() != Parm2->getDepth())
781       return false;
782     if (Parm1->getIndex() != Parm2->getIndex())
783       return false;
784     if (Parm1->isParameterPack() != Parm2->isParameterPack())
785       return false;
786 
787     // Names of template type parameters are never significant.
788     break;
789   }
790 
791   case Type::SubstTemplateTypeParm: {
792     const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
793     const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
794     if (!IsStructurallyEquivalent(Context,
795                                   QualType(Subst1->getReplacedParameter(), 0),
796                                   QualType(Subst2->getReplacedParameter(), 0)))
797       return false;
798     if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
799                                   Subst2->getReplacementType()))
800       return false;
801     break;
802   }
803 
804   case Type::SubstTemplateTypeParmPack: {
805     const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
806     const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
807     if (!IsStructurallyEquivalent(Context,
808                                   QualType(Subst1->getReplacedParameter(), 0),
809                                   QualType(Subst2->getReplacedParameter(), 0)))
810       return false;
811     if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
812                                   Subst2->getArgumentPack()))
813       return false;
814     break;
815   }
816 
817   case Type::TemplateSpecialization: {
818     const auto *Spec1 = cast<TemplateSpecializationType>(T1);
819     const auto *Spec2 = cast<TemplateSpecializationType>(T2);
820     if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
821                                   Spec2->getTemplateName()))
822       return false;
823     if (Spec1->getNumArgs() != Spec2->getNumArgs())
824       return false;
825     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
826       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
827                                     Spec2->getArg(I)))
828         return false;
829     }
830     break;
831   }
832 
833   case Type::Elaborated: {
834     const auto *Elab1 = cast<ElaboratedType>(T1);
835     const auto *Elab2 = cast<ElaboratedType>(T2);
836     // CHECKME: what if a keyword is ETK_None or ETK_typename ?
837     if (Elab1->getKeyword() != Elab2->getKeyword())
838       return false;
839     if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
840                                   Elab2->getQualifier()))
841       return false;
842     if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
843                                   Elab2->getNamedType()))
844       return false;
845     break;
846   }
847 
848   case Type::InjectedClassName: {
849     const auto *Inj1 = cast<InjectedClassNameType>(T1);
850     const auto *Inj2 = cast<InjectedClassNameType>(T2);
851     if (!IsStructurallyEquivalent(Context,
852                                   Inj1->getInjectedSpecializationType(),
853                                   Inj2->getInjectedSpecializationType()))
854       return false;
855     break;
856   }
857 
858   case Type::DependentName: {
859     const auto *Typename1 = cast<DependentNameType>(T1);
860     const auto *Typename2 = cast<DependentNameType>(T2);
861     if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
862                                   Typename2->getQualifier()))
863       return false;
864     if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
865                                   Typename2->getIdentifier()))
866       return false;
867 
868     break;
869   }
870 
871   case Type::DependentTemplateSpecialization: {
872     const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
873     const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
874     if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
875                                   Spec2->getQualifier()))
876       return false;
877     if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
878                                   Spec2->getIdentifier()))
879       return false;
880     if (Spec1->getNumArgs() != Spec2->getNumArgs())
881       return false;
882     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
883       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
884                                     Spec2->getArg(I)))
885         return false;
886     }
887     break;
888   }
889 
890   case Type::PackExpansion:
891     if (!IsStructurallyEquivalent(Context,
892                                   cast<PackExpansionType>(T1)->getPattern(),
893                                   cast<PackExpansionType>(T2)->getPattern()))
894       return false;
895     break;
896 
897   case Type::ObjCInterface: {
898     const auto *Iface1 = cast<ObjCInterfaceType>(T1);
899     const auto *Iface2 = cast<ObjCInterfaceType>(T2);
900     if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
901                                   Iface2->getDecl()))
902       return false;
903     break;
904   }
905 
906   case Type::ObjCTypeParam: {
907     const auto *Obj1 = cast<ObjCTypeParamType>(T1);
908     const auto *Obj2 = cast<ObjCTypeParamType>(T2);
909     if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
910       return false;
911 
912     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
913       return false;
914     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
915       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
916                                     Obj2->getProtocol(I)))
917         return false;
918     }
919     break;
920   }
921 
922   case Type::ObjCObject: {
923     const auto *Obj1 = cast<ObjCObjectType>(T1);
924     const auto *Obj2 = cast<ObjCObjectType>(T2);
925     if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
926                                   Obj2->getBaseType()))
927       return false;
928     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
929       return false;
930     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
931       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
932                                     Obj2->getProtocol(I)))
933         return false;
934     }
935     break;
936   }
937 
938   case Type::ObjCObjectPointer: {
939     const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
940     const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
941     if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
942                                   Ptr2->getPointeeType()))
943       return false;
944     break;
945   }
946 
947   case Type::Atomic:
948     if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
949                                   cast<AtomicType>(T2)->getValueType()))
950       return false;
951     break;
952 
953   case Type::Pipe:
954     if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
955                                   cast<PipeType>(T2)->getElementType()))
956       return false;
957     break;
958   } // end switch
959 
960   return true;
961 }
962 
963 /// Determine structural equivalence of two fields.
964 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
965                                      FieldDecl *Field1, FieldDecl *Field2) {
966   const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
967 
968   // For anonymous structs/unions, match up the anonymous struct/union type
969   // declarations directly, so that we don't go off searching for anonymous
970   // types
971   if (Field1->isAnonymousStructOrUnion() &&
972       Field2->isAnonymousStructOrUnion()) {
973     RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
974     RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
975     return IsStructurallyEquivalent(Context, D1, D2);
976   }
977 
978   // Check for equivalent field names.
979   IdentifierInfo *Name1 = Field1->getIdentifier();
980   IdentifierInfo *Name2 = Field2->getIdentifier();
981   if (!::IsStructurallyEquivalent(Name1, Name2)) {
982     if (Context.Complain) {
983       Context.Diag2(
984           Owner2->getLocation(),
985           Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
986           << Context.ToCtx.getTypeDeclType(Owner2);
987       Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
988           << Field2->getDeclName();
989       Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
990           << Field1->getDeclName();
991     }
992     return false;
993   }
994 
995   if (!IsStructurallyEquivalent(Context, Field1->getType(),
996                                 Field2->getType())) {
997     if (Context.Complain) {
998       Context.Diag2(
999           Owner2->getLocation(),
1000           Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1001           << Context.ToCtx.getTypeDeclType(Owner2);
1002       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1003           << Field2->getDeclName() << Field2->getType();
1004       Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1005           << Field1->getDeclName() << Field1->getType();
1006     }
1007     return false;
1008   }
1009 
1010   if (Field1->isBitField() != Field2->isBitField()) {
1011     if (Context.Complain) {
1012       Context.Diag2(
1013           Owner2->getLocation(),
1014           Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1015           << Context.ToCtx.getTypeDeclType(Owner2);
1016       if (Field1->isBitField()) {
1017         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
1018             << Field1->getDeclName() << Field1->getType()
1019             << Field1->getBitWidthValue(Context.FromCtx);
1020         Context.Diag2(Field2->getLocation(), diag::note_odr_not_bit_field)
1021             << Field2->getDeclName();
1022       } else {
1023         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
1024             << Field2->getDeclName() << Field2->getType()
1025             << Field2->getBitWidthValue(Context.ToCtx);
1026         Context.Diag1(Field1->getLocation(), diag::note_odr_not_bit_field)
1027             << Field1->getDeclName();
1028       }
1029     }
1030     return false;
1031   }
1032 
1033   if (Field1->isBitField()) {
1034     // Make sure that the bit-fields are the same length.
1035     unsigned Bits1 = Field1->getBitWidthValue(Context.FromCtx);
1036     unsigned Bits2 = Field2->getBitWidthValue(Context.ToCtx);
1037 
1038     if (Bits1 != Bits2) {
1039       if (Context.Complain) {
1040         Context.Diag2(Owner2->getLocation(),
1041                       Context.getApplicableDiagnostic(
1042                           diag::err_odr_tag_type_inconsistent))
1043             << Context.ToCtx.getTypeDeclType(Owner2);
1044         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
1045             << Field2->getDeclName() << Field2->getType() << Bits2;
1046         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
1047             << Field1->getDeclName() << Field1->getType() << Bits1;
1048       }
1049       return false;
1050     }
1051   }
1052 
1053   return true;
1054 }
1055 
1056 /// Determine structural equivalence of two methods.
1057 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1058                                      CXXMethodDecl *Method1,
1059                                      CXXMethodDecl *Method2) {
1060   bool PropertiesEqual =
1061       Method1->getDeclKind() == Method2->getDeclKind() &&
1062       Method1->getRefQualifier() == Method2->getRefQualifier() &&
1063       Method1->getAccess() == Method2->getAccess() &&
1064       Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
1065       Method1->isStatic() == Method2->isStatic() &&
1066       Method1->isConst() == Method2->isConst() &&
1067       Method1->isVolatile() == Method2->isVolatile() &&
1068       Method1->isVirtual() == Method2->isVirtual() &&
1069       Method1->isPure() == Method2->isPure() &&
1070       Method1->isDefaulted() == Method2->isDefaulted() &&
1071       Method1->isDeleted() == Method2->isDeleted();
1072   if (!PropertiesEqual)
1073     return false;
1074   // FIXME: Check for 'final'.
1075 
1076   if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
1077     auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
1078     if (!Constructor1->getExplicitSpecifier().isEquivalent(
1079             Constructor2->getExplicitSpecifier()))
1080       return false;
1081   }
1082 
1083   if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
1084     auto *Conversion2 = cast<CXXConversionDecl>(Method2);
1085     if (!Conversion1->getExplicitSpecifier().isEquivalent(
1086             Conversion2->getExplicitSpecifier()))
1087       return false;
1088     if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
1089                                   Conversion2->getConversionType()))
1090       return false;
1091   }
1092 
1093   const IdentifierInfo *Name1 = Method1->getIdentifier();
1094   const IdentifierInfo *Name2 = Method2->getIdentifier();
1095   if (!::IsStructurallyEquivalent(Name1, Name2)) {
1096     return false;
1097     // TODO: Names do not match, add warning like at check for FieldDecl.
1098   }
1099 
1100   // Check the prototypes.
1101   if (!::IsStructurallyEquivalent(Context,
1102                                   Method1->getType(), Method2->getType()))
1103     return false;
1104 
1105   return true;
1106 }
1107 
1108 /// Determine structural equivalence of two lambda classes.
1109 static bool
1110 IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
1111                                 CXXRecordDecl *D1, CXXRecordDecl *D2) {
1112   assert(D1->isLambda() && D2->isLambda() &&
1113          "Must be called on lambda classes");
1114   if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(),
1115                                 D2->getLambdaCallOperator()))
1116     return false;
1117 
1118   return true;
1119 }
1120 
1121 /// Determine structural equivalence of two records.
1122 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1123                                      RecordDecl *D1, RecordDecl *D2) {
1124   if (D1->isUnion() != D2->isUnion()) {
1125     if (Context.Complain) {
1126       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1127                                            diag::err_odr_tag_type_inconsistent))
1128           << Context.ToCtx.getTypeDeclType(D2);
1129       Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1130           << D1->getDeclName() << (unsigned)D1->getTagKind();
1131     }
1132     return false;
1133   }
1134 
1135   if (!D1->getDeclName() && !D2->getDeclName()) {
1136     // If both anonymous structs/unions are in a record context, make sure
1137     // they occur in the same location in the context records.
1138     if (Optional<unsigned> Index1 =
1139             StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
1140       if (Optional<unsigned> Index2 =
1141               StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1142                   D2)) {
1143         if (*Index1 != *Index2)
1144           return false;
1145       }
1146     }
1147   }
1148 
1149   // If both declarations are class template specializations, we know
1150   // the ODR applies, so check the template and template arguments.
1151   const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
1152   const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
1153   if (Spec1 && Spec2) {
1154     // Check that the specialized templates are the same.
1155     if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1156                                   Spec2->getSpecializedTemplate()))
1157       return false;
1158 
1159     // Check that the template arguments are the same.
1160     if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1161       return false;
1162 
1163     for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1164       if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
1165                                     Spec2->getTemplateArgs().get(I)))
1166         return false;
1167   }
1168   // If one is a class template specialization and the other is not, these
1169   // structures are different.
1170   else if (Spec1 || Spec2)
1171     return false;
1172 
1173   // Compare the definitions of these two records. If either or both are
1174   // incomplete (i.e. it is a forward decl), we assume that they are
1175   // equivalent.
1176   D1 = D1->getDefinition();
1177   D2 = D2->getDefinition();
1178   if (!D1 || !D2)
1179     return true;
1180 
1181   // If any of the records has external storage and we do a minimal check (or
1182   // AST import) we assume they are equivalent. (If we didn't have this
1183   // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1184   // another AST import which in turn would call the structural equivalency
1185   // check again and finally we'd have an improper result.)
1186   if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1187     if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
1188       return true;
1189 
1190   // If one definition is currently being defined, we do not compare for
1191   // equality and we assume that the decls are equal.
1192   if (D1->isBeingDefined() || D2->isBeingDefined())
1193     return true;
1194 
1195   if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
1196     if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
1197       if (D1CXX->hasExternalLexicalStorage() &&
1198           !D1CXX->isCompleteDefinition()) {
1199         D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1200       }
1201 
1202       if (D1CXX->isLambda() != D2CXX->isLambda())
1203         return false;
1204       if (D1CXX->isLambda()) {
1205         if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))
1206           return false;
1207       }
1208 
1209       if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1210         if (Context.Complain) {
1211           Context.Diag2(D2->getLocation(),
1212                         Context.getApplicableDiagnostic(
1213                             diag::err_odr_tag_type_inconsistent))
1214               << Context.ToCtx.getTypeDeclType(D2);
1215           Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1216               << D2CXX->getNumBases();
1217           Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1218               << D1CXX->getNumBases();
1219         }
1220         return false;
1221       }
1222 
1223       // Check the base classes.
1224       for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1225                                               BaseEnd1 = D1CXX->bases_end(),
1226                                               Base2 = D2CXX->bases_begin();
1227            Base1 != BaseEnd1; ++Base1, ++Base2) {
1228         if (!IsStructurallyEquivalent(Context, Base1->getType(),
1229                                       Base2->getType())) {
1230           if (Context.Complain) {
1231             Context.Diag2(D2->getLocation(),
1232                           Context.getApplicableDiagnostic(
1233                               diag::err_odr_tag_type_inconsistent))
1234                 << Context.ToCtx.getTypeDeclType(D2);
1235             Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1236                 << Base2->getType() << Base2->getSourceRange();
1237             Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1238                 << Base1->getType() << Base1->getSourceRange();
1239           }
1240           return false;
1241         }
1242 
1243         // Check virtual vs. non-virtual inheritance mismatch.
1244         if (Base1->isVirtual() != Base2->isVirtual()) {
1245           if (Context.Complain) {
1246             Context.Diag2(D2->getLocation(),
1247                           Context.getApplicableDiagnostic(
1248                               diag::err_odr_tag_type_inconsistent))
1249                 << Context.ToCtx.getTypeDeclType(D2);
1250             Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1251                 << Base2->isVirtual() << Base2->getSourceRange();
1252             Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1253                 << Base1->isVirtual() << Base1->getSourceRange();
1254           }
1255           return false;
1256         }
1257       }
1258 
1259       // Check the friends for consistency.
1260       CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1261                                      Friend2End = D2CXX->friend_end();
1262       for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1263                                           Friend1End = D1CXX->friend_end();
1264            Friend1 != Friend1End; ++Friend1, ++Friend2) {
1265         if (Friend2 == Friend2End) {
1266           if (Context.Complain) {
1267             Context.Diag2(D2->getLocation(),
1268                           Context.getApplicableDiagnostic(
1269                               diag::err_odr_tag_type_inconsistent))
1270                 << Context.ToCtx.getTypeDeclType(D2CXX);
1271             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1272             Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1273           }
1274           return false;
1275         }
1276 
1277         if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1278           if (Context.Complain) {
1279             Context.Diag2(D2->getLocation(),
1280                           Context.getApplicableDiagnostic(
1281                               diag::err_odr_tag_type_inconsistent))
1282                 << Context.ToCtx.getTypeDeclType(D2CXX);
1283             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1284             Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1285           }
1286           return false;
1287         }
1288       }
1289 
1290       if (Friend2 != Friend2End) {
1291         if (Context.Complain) {
1292           Context.Diag2(D2->getLocation(),
1293                         Context.getApplicableDiagnostic(
1294                             diag::err_odr_tag_type_inconsistent))
1295               << Context.ToCtx.getTypeDeclType(D2);
1296           Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1297           Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1298         }
1299         return false;
1300       }
1301     } else if (D1CXX->getNumBases() > 0) {
1302       if (Context.Complain) {
1303         Context.Diag2(D2->getLocation(),
1304                       Context.getApplicableDiagnostic(
1305                           diag::err_odr_tag_type_inconsistent))
1306             << Context.ToCtx.getTypeDeclType(D2);
1307         const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1308         Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1309             << Base1->getType() << Base1->getSourceRange();
1310         Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1311       }
1312       return false;
1313     }
1314   }
1315 
1316   // Check the fields for consistency.
1317   RecordDecl::field_iterator Field2 = D2->field_begin(),
1318                              Field2End = D2->field_end();
1319   for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1320                                   Field1End = D1->field_end();
1321        Field1 != Field1End; ++Field1, ++Field2) {
1322     if (Field2 == Field2End) {
1323       if (Context.Complain) {
1324         Context.Diag2(D2->getLocation(),
1325                       Context.getApplicableDiagnostic(
1326                           diag::err_odr_tag_type_inconsistent))
1327             << Context.ToCtx.getTypeDeclType(D2);
1328         Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1329             << Field1->getDeclName() << Field1->getType();
1330         Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1331       }
1332       return false;
1333     }
1334 
1335     if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1336       return false;
1337   }
1338 
1339   if (Field2 != Field2End) {
1340     if (Context.Complain) {
1341       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1342                                            diag::err_odr_tag_type_inconsistent))
1343           << Context.ToCtx.getTypeDeclType(D2);
1344       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1345           << Field2->getDeclName() << Field2->getType();
1346       Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1347     }
1348     return false;
1349   }
1350 
1351   return true;
1352 }
1353 
1354 /// Determine structural equivalence of two enums.
1355 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1356                                      EnumDecl *D1, EnumDecl *D2) {
1357 
1358   // Compare the definitions of these two enums. If either or both are
1359   // incomplete (i.e. forward declared), we assume that they are equivalent.
1360   D1 = D1->getDefinition();
1361   D2 = D2->getDefinition();
1362   if (!D1 || !D2)
1363     return true;
1364 
1365   EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1366                                 EC2End = D2->enumerator_end();
1367   for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1368                                      EC1End = D1->enumerator_end();
1369        EC1 != EC1End; ++EC1, ++EC2) {
1370     if (EC2 == EC2End) {
1371       if (Context.Complain) {
1372         Context.Diag2(D2->getLocation(),
1373                       Context.getApplicableDiagnostic(
1374                           diag::err_odr_tag_type_inconsistent))
1375             << Context.ToCtx.getTypeDeclType(D2);
1376         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1377             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1378         Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1379       }
1380       return false;
1381     }
1382 
1383     llvm::APSInt Val1 = EC1->getInitVal();
1384     llvm::APSInt Val2 = EC2->getInitVal();
1385     if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1386         !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1387       if (Context.Complain) {
1388         Context.Diag2(D2->getLocation(),
1389                       Context.getApplicableDiagnostic(
1390                           diag::err_odr_tag_type_inconsistent))
1391             << Context.ToCtx.getTypeDeclType(D2);
1392         Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1393             << EC2->getDeclName() << EC2->getInitVal().toString(10);
1394         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1395             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1396       }
1397       return false;
1398     }
1399   }
1400 
1401   if (EC2 != EC2End) {
1402     if (Context.Complain) {
1403       Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1404                                            diag::err_odr_tag_type_inconsistent))
1405           << Context.ToCtx.getTypeDeclType(D2);
1406       Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1407           << EC2->getDeclName() << EC2->getInitVal().toString(10);
1408       Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1409     }
1410     return false;
1411   }
1412 
1413   return true;
1414 }
1415 
1416 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1417                                      TemplateParameterList *Params1,
1418                                      TemplateParameterList *Params2) {
1419   if (Params1->size() != Params2->size()) {
1420     if (Context.Complain) {
1421       Context.Diag2(Params2->getTemplateLoc(),
1422                     Context.getApplicableDiagnostic(
1423                         diag::err_odr_different_num_template_parameters))
1424           << Params1->size() << Params2->size();
1425       Context.Diag1(Params1->getTemplateLoc(),
1426                     diag::note_odr_template_parameter_list);
1427     }
1428     return false;
1429   }
1430 
1431   for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1432     if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1433       if (Context.Complain) {
1434         Context.Diag2(Params2->getParam(I)->getLocation(),
1435                       Context.getApplicableDiagnostic(
1436                           diag::err_odr_different_template_parameter_kind));
1437         Context.Diag1(Params1->getParam(I)->getLocation(),
1438                       diag::note_odr_template_parameter_here);
1439       }
1440       return false;
1441     }
1442 
1443     if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1444                                   Params2->getParam(I)))
1445       return false;
1446   }
1447 
1448   return true;
1449 }
1450 
1451 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1452                                      TemplateTypeParmDecl *D1,
1453                                      TemplateTypeParmDecl *D2) {
1454   if (D1->isParameterPack() != D2->isParameterPack()) {
1455     if (Context.Complain) {
1456       Context.Diag2(D2->getLocation(),
1457                     Context.getApplicableDiagnostic(
1458                         diag::err_odr_parameter_pack_non_pack))
1459           << D2->isParameterPack();
1460       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1461           << D1->isParameterPack();
1462     }
1463     return false;
1464   }
1465 
1466   return true;
1467 }
1468 
1469 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1470                                      NonTypeTemplateParmDecl *D1,
1471                                      NonTypeTemplateParmDecl *D2) {
1472   if (D1->isParameterPack() != D2->isParameterPack()) {
1473     if (Context.Complain) {
1474       Context.Diag2(D2->getLocation(),
1475                     Context.getApplicableDiagnostic(
1476                         diag::err_odr_parameter_pack_non_pack))
1477           << D2->isParameterPack();
1478       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1479           << D1->isParameterPack();
1480     }
1481     return false;
1482   }
1483 
1484   // Check types.
1485   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1486     if (Context.Complain) {
1487       Context.Diag2(D2->getLocation(),
1488                     Context.getApplicableDiagnostic(
1489                         diag::err_odr_non_type_parameter_type_inconsistent))
1490           << D2->getType() << D1->getType();
1491       Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1492           << D1->getType();
1493     }
1494     return false;
1495   }
1496 
1497   return true;
1498 }
1499 
1500 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1501                                      TemplateTemplateParmDecl *D1,
1502                                      TemplateTemplateParmDecl *D2) {
1503   if (D1->isParameterPack() != D2->isParameterPack()) {
1504     if (Context.Complain) {
1505       Context.Diag2(D2->getLocation(),
1506                     Context.getApplicableDiagnostic(
1507                         diag::err_odr_parameter_pack_non_pack))
1508           << D2->isParameterPack();
1509       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1510           << D1->isParameterPack();
1511     }
1512     return false;
1513   }
1514 
1515   // Check template parameter lists.
1516   return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1517                                   D2->getTemplateParameters());
1518 }
1519 
1520 static bool IsTemplateDeclCommonStructurallyEquivalent(
1521     StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1522   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1523     return false;
1524   if (!D1->getIdentifier()) // Special name
1525     if (D1->getNameAsString() != D2->getNameAsString())
1526       return false;
1527   return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1528                                   D2->getTemplateParameters());
1529 }
1530 
1531 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1532                                      ClassTemplateDecl *D1,
1533                                      ClassTemplateDecl *D2) {
1534   // Check template parameters.
1535   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1536     return false;
1537 
1538   // Check the templated declaration.
1539   return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1540                                   D2->getTemplatedDecl());
1541 }
1542 
1543 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1544                                      FunctionTemplateDecl *D1,
1545                                      FunctionTemplateDecl *D2) {
1546   // Check template parameters.
1547   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1548     return false;
1549 
1550   // Check the templated declaration.
1551   return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1552                                   D2->getTemplatedDecl()->getType());
1553 }
1554 
1555 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1556                                      ConceptDecl *D1,
1557                                      ConceptDecl *D2) {
1558   // Check template parameters.
1559   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1560     return false;
1561 
1562   // Check the constraint expression.
1563   return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),
1564                                   D2->getConstraintExpr());
1565 }
1566 
1567 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1568                                      FriendDecl *D1, FriendDecl *D2) {
1569   if ((D1->getFriendType() && D2->getFriendDecl()) ||
1570       (D1->getFriendDecl() && D2->getFriendType())) {
1571       return false;
1572   }
1573   if (D1->getFriendType() && D2->getFriendType())
1574     return IsStructurallyEquivalent(Context,
1575                                     D1->getFriendType()->getType(),
1576                                     D2->getFriendType()->getType());
1577   if (D1->getFriendDecl() && D2->getFriendDecl())
1578     return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1579                                     D2->getFriendDecl());
1580   return false;
1581 }
1582 
1583 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1584                                      FunctionDecl *D1, FunctionDecl *D2) {
1585   // FIXME: Consider checking for function attributes as well.
1586   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1587     return false;
1588 
1589   return true;
1590 }
1591 
1592 /// Determine structural equivalence of two declarations.
1593 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1594                                      Decl *D1, Decl *D2) {
1595   // FIXME: Check for known structural equivalences via a callback of some sort.
1596 
1597   D1 = D1->getCanonicalDecl();
1598   D2 = D2->getCanonicalDecl();
1599   std::pair<Decl *, Decl *> P{D1, D2};
1600 
1601   // Check whether we already know that these two declarations are not
1602   // structurally equivalent.
1603   if (Context.NonEquivalentDecls.count(P))
1604     return false;
1605 
1606   // Check if a check for these declarations is already pending.
1607   // If yes D1 and D2 will be checked later (from DeclsToCheck),
1608   // or these are already checked (and equivalent).
1609   bool Inserted = Context.VisitedDecls.insert(P).second;
1610   if (!Inserted)
1611     return true;
1612 
1613   Context.DeclsToCheck.push(P);
1614 
1615   return true;
1616 }
1617 
1618 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1619                                                       unsigned DiagID) {
1620   assert(Complain && "Not allowed to complain");
1621   if (LastDiagFromC2)
1622     FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1623   LastDiagFromC2 = false;
1624   return FromCtx.getDiagnostics().Report(Loc, DiagID);
1625 }
1626 
1627 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1628                                                       unsigned DiagID) {
1629   assert(Complain && "Not allowed to complain");
1630   if (!LastDiagFromC2)
1631     ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1632   LastDiagFromC2 = true;
1633   return ToCtx.getDiagnostics().Report(Loc, DiagID);
1634 }
1635 
1636 Optional<unsigned>
1637 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1638   ASTContext &Context = Anon->getASTContext();
1639   QualType AnonTy = Context.getRecordType(Anon);
1640 
1641   const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1642   if (!Owner)
1643     return None;
1644 
1645   unsigned Index = 0;
1646   for (const auto *D : Owner->noload_decls()) {
1647     const auto *F = dyn_cast<FieldDecl>(D);
1648     if (!F)
1649       continue;
1650 
1651     if (F->isAnonymousStructOrUnion()) {
1652       if (Context.hasSameType(F->getType(), AnonTy))
1653         break;
1654       ++Index;
1655       continue;
1656     }
1657 
1658     // If the field looks like this:
1659     // struct { ... } A;
1660     QualType FieldType = F->getType();
1661     // In case of nested structs.
1662     while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1663       FieldType = ElabType->getNamedType();
1664 
1665     if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1666       const RecordDecl *RecDecl = RecType->getDecl();
1667       if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1668         if (Context.hasSameType(FieldType, AnonTy))
1669           break;
1670         ++Index;
1671         continue;
1672       }
1673     }
1674   }
1675 
1676   return Index;
1677 }
1678 
1679 unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
1680     unsigned ErrorDiagnostic) {
1681   if (ErrorOnTagTypeMismatch)
1682     return ErrorDiagnostic;
1683 
1684   switch (ErrorDiagnostic) {
1685   case diag::err_odr_variable_type_inconsistent:
1686     return diag::warn_odr_variable_type_inconsistent;
1687   case diag::err_odr_variable_multiple_def:
1688     return diag::warn_odr_variable_multiple_def;
1689   case diag::err_odr_function_type_inconsistent:
1690     return diag::warn_odr_function_type_inconsistent;
1691   case diag::err_odr_tag_type_inconsistent:
1692     return diag::warn_odr_tag_type_inconsistent;
1693   case diag::err_odr_field_type_inconsistent:
1694     return diag::warn_odr_field_type_inconsistent;
1695   case diag::err_odr_ivar_type_inconsistent:
1696     return diag::warn_odr_ivar_type_inconsistent;
1697   case diag::err_odr_objc_superclass_inconsistent:
1698     return diag::warn_odr_objc_superclass_inconsistent;
1699   case diag::err_odr_objc_method_result_type_inconsistent:
1700     return diag::warn_odr_objc_method_result_type_inconsistent;
1701   case diag::err_odr_objc_method_num_params_inconsistent:
1702     return diag::warn_odr_objc_method_num_params_inconsistent;
1703   case diag::err_odr_objc_method_param_type_inconsistent:
1704     return diag::warn_odr_objc_method_param_type_inconsistent;
1705   case diag::err_odr_objc_method_variadic_inconsistent:
1706     return diag::warn_odr_objc_method_variadic_inconsistent;
1707   case diag::err_odr_objc_property_type_inconsistent:
1708     return diag::warn_odr_objc_property_type_inconsistent;
1709   case diag::err_odr_objc_property_impl_kind_inconsistent:
1710     return diag::warn_odr_objc_property_impl_kind_inconsistent;
1711   case diag::err_odr_objc_synthesize_ivar_inconsistent:
1712     return diag::warn_odr_objc_synthesize_ivar_inconsistent;
1713   case diag::err_odr_different_num_template_parameters:
1714     return diag::warn_odr_different_num_template_parameters;
1715   case diag::err_odr_different_template_parameter_kind:
1716     return diag::warn_odr_different_template_parameter_kind;
1717   case diag::err_odr_parameter_pack_non_pack:
1718     return diag::warn_odr_parameter_pack_non_pack;
1719   case diag::err_odr_non_type_parameter_type_inconsistent:
1720     return diag::warn_odr_non_type_parameter_type_inconsistent;
1721   }
1722   llvm_unreachable("Diagnostic kind not handled in preceding switch");
1723 }
1724 
1725 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
1726 
1727   // Ensure that the implementation functions (all static functions in this TU)
1728   // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
1729   // because that will wreak havoc the internal state (DeclsToCheck and
1730   // VisitedDecls members) and can cause faulty behaviour.
1731   // In other words: Do not start a graph search from a new node with the
1732   // internal data of another search in progress.
1733   // FIXME: Better encapsulation and separation of internal and public
1734   // functionality.
1735   assert(DeclsToCheck.empty());
1736   assert(VisitedDecls.empty());
1737 
1738   if (!::IsStructurallyEquivalent(*this, D1, D2))
1739     return false;
1740 
1741   return !Finish();
1742 }
1743 
1744 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
1745   assert(DeclsToCheck.empty());
1746   assert(VisitedDecls.empty());
1747   if (!::IsStructurallyEquivalent(*this, T1, T2))
1748     return false;
1749 
1750   return !Finish();
1751 }
1752 
1753 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
1754   // Check for equivalent described template.
1755   TemplateDecl *Template1 = D1->getDescribedTemplate();
1756   TemplateDecl *Template2 = D2->getDescribedTemplate();
1757   if ((Template1 != nullptr) != (Template2 != nullptr))
1758     return false;
1759   if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
1760     return false;
1761 
1762   // FIXME: Move check for identifier names into this function.
1763 
1764   return true;
1765 }
1766 
1767 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
1768     Decl *D1, Decl *D2) {
1769   // FIXME: Switch on all declaration kinds. For now, we're just going to
1770   // check the obvious ones.
1771   if (auto *Record1 = dyn_cast<RecordDecl>(D1)) {
1772     if (auto *Record2 = dyn_cast<RecordDecl>(D2)) {
1773       // Check for equivalent structure names.
1774       IdentifierInfo *Name1 = Record1->getIdentifier();
1775       if (!Name1 && Record1->getTypedefNameForAnonDecl())
1776         Name1 = Record1->getTypedefNameForAnonDecl()->getIdentifier();
1777       IdentifierInfo *Name2 = Record2->getIdentifier();
1778       if (!Name2 && Record2->getTypedefNameForAnonDecl())
1779         Name2 = Record2->getTypedefNameForAnonDecl()->getIdentifier();
1780       if (!::IsStructurallyEquivalent(Name1, Name2) ||
1781           !::IsStructurallyEquivalent(*this, Record1, Record2))
1782         return false;
1783     } else {
1784       // Record/non-record mismatch.
1785       return false;
1786     }
1787   } else if (auto *Enum1 = dyn_cast<EnumDecl>(D1)) {
1788     if (auto *Enum2 = dyn_cast<EnumDecl>(D2)) {
1789       // Check for equivalent enum names.
1790       IdentifierInfo *Name1 = Enum1->getIdentifier();
1791       if (!Name1 && Enum1->getTypedefNameForAnonDecl())
1792         Name1 = Enum1->getTypedefNameForAnonDecl()->getIdentifier();
1793       IdentifierInfo *Name2 = Enum2->getIdentifier();
1794       if (!Name2 && Enum2->getTypedefNameForAnonDecl())
1795         Name2 = Enum2->getTypedefNameForAnonDecl()->getIdentifier();
1796       if (!::IsStructurallyEquivalent(Name1, Name2) ||
1797           !::IsStructurallyEquivalent(*this, Enum1, Enum2))
1798         return false;
1799     } else {
1800       // Enum/non-enum mismatch
1801       return false;
1802     }
1803   } else if (const auto *Typedef1 = dyn_cast<TypedefNameDecl>(D1)) {
1804     if (const auto *Typedef2 = dyn_cast<TypedefNameDecl>(D2)) {
1805       if (!::IsStructurallyEquivalent(Typedef1->getIdentifier(),
1806                                       Typedef2->getIdentifier()) ||
1807           !::IsStructurallyEquivalent(*this, Typedef1->getUnderlyingType(),
1808                                       Typedef2->getUnderlyingType()))
1809         return false;
1810     } else {
1811       // Typedef/non-typedef mismatch.
1812       return false;
1813     }
1814   } else if (auto *ClassTemplate1 = dyn_cast<ClassTemplateDecl>(D1)) {
1815     if (auto *ClassTemplate2 = dyn_cast<ClassTemplateDecl>(D2)) {
1816       if (!::IsStructurallyEquivalent(*this, ClassTemplate1,
1817                                       ClassTemplate2))
1818         return false;
1819     } else {
1820       // Class template/non-class-template mismatch.
1821       return false;
1822     }
1823   } else if (auto *FunctionTemplate1 = dyn_cast<FunctionTemplateDecl>(D1)) {
1824     if (auto *FunctionTemplate2 = dyn_cast<FunctionTemplateDecl>(D2)) {
1825       if (!::IsStructurallyEquivalent(*this, FunctionTemplate1,
1826                                       FunctionTemplate2))
1827         return false;
1828     } else {
1829       // Class template/non-class-template mismatch.
1830       return false;
1831     }
1832   } else if (auto *ConceptDecl1 = dyn_cast<ConceptDecl>(D1)) {
1833     if (auto *ConceptDecl2 = dyn_cast<ConceptDecl>(D2)) {
1834       if (!::IsStructurallyEquivalent(*this, ConceptDecl1, ConceptDecl2))
1835         return false;
1836     } else {
1837       // Concept/non-concept mismatch.
1838       return false;
1839     }
1840   } else if (auto *TTP1 = dyn_cast<TemplateTypeParmDecl>(D1)) {
1841     if (auto *TTP2 = dyn_cast<TemplateTypeParmDecl>(D2)) {
1842       if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1843         return false;
1844     } else {
1845       // Kind mismatch.
1846       return false;
1847     }
1848   } else if (auto *NTTP1 = dyn_cast<NonTypeTemplateParmDecl>(D1)) {
1849     if (auto *NTTP2 = dyn_cast<NonTypeTemplateParmDecl>(D2)) {
1850       if (!::IsStructurallyEquivalent(*this, NTTP1, NTTP2))
1851         return false;
1852     } else {
1853       // Kind mismatch.
1854       return false;
1855     }
1856   } else if (auto *TTP1 = dyn_cast<TemplateTemplateParmDecl>(D1)) {
1857     if (auto *TTP2 = dyn_cast<TemplateTemplateParmDecl>(D2)) {
1858       if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1859         return false;
1860     } else {
1861       // Kind mismatch.
1862       return false;
1863     }
1864   } else if (auto *MD1 = dyn_cast<CXXMethodDecl>(D1)) {
1865     if (auto *MD2 = dyn_cast<CXXMethodDecl>(D2)) {
1866       if (!::IsStructurallyEquivalent(*this, MD1, MD2))
1867         return false;
1868     } else {
1869       // Kind mismatch.
1870       return false;
1871     }
1872   } else if (FunctionDecl *FD1 = dyn_cast<FunctionDecl>(D1)) {
1873     if (FunctionDecl *FD2 = dyn_cast<FunctionDecl>(D2)) {
1874       if (FD1->isOverloadedOperator()) {
1875         if (!FD2->isOverloadedOperator())
1876           return false;
1877         if (FD1->getOverloadedOperator() != FD2->getOverloadedOperator())
1878           return false;
1879       }
1880       if (!::IsStructurallyEquivalent(FD1->getIdentifier(),
1881                                       FD2->getIdentifier()))
1882         return false;
1883       if (!::IsStructurallyEquivalent(*this, FD1, FD2))
1884         return false;
1885     } else {
1886       // Kind mismatch.
1887       return false;
1888     }
1889   } else if (FriendDecl *FrD1 = dyn_cast<FriendDecl>(D1)) {
1890     if (FriendDecl *FrD2 = dyn_cast<FriendDecl>(D2)) {
1891         if (!::IsStructurallyEquivalent(*this, FrD1, FrD2))
1892           return false;
1893     } else {
1894       // Kind mismatch.
1895       return false;
1896     }
1897   }
1898 
1899   return true;
1900 }
1901 
1902 bool StructuralEquivalenceContext::Finish() {
1903   while (!DeclsToCheck.empty()) {
1904     // Check the next declaration.
1905     std::pair<Decl *, Decl *> P = DeclsToCheck.front();
1906     DeclsToCheck.pop();
1907 
1908     Decl *D1 = P.first;
1909     Decl *D2 = P.second;
1910 
1911     bool Equivalent =
1912         CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
1913 
1914     if (!Equivalent) {
1915       // Note that these two declarations are not equivalent (and we already
1916       // know about it).
1917       NonEquivalentDecls.insert(P);
1918 
1919       return true;
1920     }
1921   }
1922 
1923   return false;
1924 }
1925