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