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