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