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