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