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 //===----------------------------------------------------------------------===//
14 
15 #include "clang/AST/ASTStructuralEquivalence.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/ASTDiagnostic.h"
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/DeclBase.h"
20 #include "clang/AST/DeclCXX.h"
21 #include "clang/AST/DeclObjC.h"
22 #include "clang/AST/DeclTemplate.h"
23 #include "clang/AST/NestedNameSpecifier.h"
24 #include "clang/AST/TemplateBase.h"
25 #include "clang/AST/TemplateName.h"
26 #include "clang/AST/Type.h"
27 #include "clang/Basic/ExceptionSpecificationType.h"
28 #include "clang/Basic/IdentifierTable.h"
29 #include "clang/Basic/LLVM.h"
30 #include "clang/Basic/SourceLocation.h"
31 #include "llvm/ADT/APInt.h"
32 #include "llvm/ADT/APSInt.h"
33 #include "llvm/ADT/None.h"
34 #include "llvm/ADT/Optional.h"
35 #include "llvm/Support/Casting.h"
36 #include "llvm/Support/Compiler.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include <cassert>
39 #include <utility>
40 
41 using namespace clang;
42 
43 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
44                                      QualType T1, QualType T2);
45 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
46                                      Decl *D1, Decl *D2);
47 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
48                                      const TemplateArgument &Arg1,
49                                      const TemplateArgument &Arg2);
50 
51 /// Determine structural equivalence of two expressions.
52 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
53                                      Expr *E1, Expr *E2) {
54   if (!E1 || !E2)
55     return E1 == E2;
56 
57   // FIXME: Actually perform a structural comparison!
58   return true;
59 }
60 
61 /// Determine whether two identifiers are equivalent.
62 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
63                                      const IdentifierInfo *Name2) {
64   if (!Name1 || !Name2)
65     return Name1 == Name2;
66 
67   return Name1->getName() == Name2->getName();
68 }
69 
70 /// Determine whether two nested-name-specifiers are equivalent.
71 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
72                                      NestedNameSpecifier *NNS1,
73                                      NestedNameSpecifier *NNS2) {
74   if (NNS1->getKind() != NNS2->getKind())
75     return false;
76 
77   NestedNameSpecifier *Prefix1 = NNS1->getPrefix(),
78                       *Prefix2 = NNS2->getPrefix();
79   if ((bool)Prefix1 != (bool)Prefix2)
80     return false;
81 
82   if (Prefix1)
83     if (!IsStructurallyEquivalent(Context, Prefix1, Prefix2))
84       return false;
85 
86   switch (NNS1->getKind()) {
87   case NestedNameSpecifier::Identifier:
88     return IsStructurallyEquivalent(NNS1->getAsIdentifier(),
89                                     NNS2->getAsIdentifier());
90   case NestedNameSpecifier::Namespace:
91     return IsStructurallyEquivalent(Context, NNS1->getAsNamespace(),
92                                     NNS2->getAsNamespace());
93   case NestedNameSpecifier::NamespaceAlias:
94     return IsStructurallyEquivalent(Context, NNS1->getAsNamespaceAlias(),
95                                     NNS2->getAsNamespaceAlias());
96   case NestedNameSpecifier::TypeSpec:
97   case NestedNameSpecifier::TypeSpecWithTemplate:
98     return IsStructurallyEquivalent(Context, QualType(NNS1->getAsType(), 0),
99                                     QualType(NNS2->getAsType(), 0));
100   case NestedNameSpecifier::Global:
101     return true;
102   case NestedNameSpecifier::Super:
103     return IsStructurallyEquivalent(Context, NNS1->getAsRecordDecl(),
104                                     NNS2->getAsRecordDecl());
105   }
106   return false;
107 }
108 
109 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
110                                      const TemplateName &N1,
111                                      const TemplateName &N2) {
112   if (N1.getKind() != N2.getKind())
113     return false;
114   switch (N1.getKind()) {
115   case TemplateName::Template:
116     return IsStructurallyEquivalent(Context, N1.getAsTemplateDecl(),
117                                     N2.getAsTemplateDecl());
118 
119   case TemplateName::OverloadedTemplate: {
120     OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),
121                               *OS2 = N2.getAsOverloadedTemplate();
122     OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),
123                                         E1 = OS1->end(), E2 = OS2->end();
124     for (; I1 != E1 && I2 != E2; ++I1, ++I2)
125       if (!IsStructurallyEquivalent(Context, *I1, *I2))
126         return false;
127     return I1 == E1 && I2 == E2;
128   }
129 
130   case TemplateName::QualifiedTemplate: {
131     QualifiedTemplateName *QN1 = N1.getAsQualifiedTemplateName(),
132                           *QN2 = N2.getAsQualifiedTemplateName();
133     return IsStructurallyEquivalent(Context, QN1->getDecl(), QN2->getDecl()) &&
134            IsStructurallyEquivalent(Context, QN1->getQualifier(),
135                                     QN2->getQualifier());
136   }
137 
138   case TemplateName::DependentTemplate: {
139     DependentTemplateName *DN1 = N1.getAsDependentTemplateName(),
140                           *DN2 = N2.getAsDependentTemplateName();
141     if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
142                                   DN2->getQualifier()))
143       return false;
144     if (DN1->isIdentifier() && DN2->isIdentifier())
145       return IsStructurallyEquivalent(DN1->getIdentifier(),
146                                       DN2->getIdentifier());
147     else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
148       return DN1->getOperator() == DN2->getOperator();
149     return false;
150   }
151 
152   case TemplateName::SubstTemplateTemplateParm: {
153     SubstTemplateTemplateParmStorage *TS1 = N1.getAsSubstTemplateTemplateParm(),
154                                      *TS2 = N2.getAsSubstTemplateTemplateParm();
155     return IsStructurallyEquivalent(Context, TS1->getParameter(),
156                                     TS2->getParameter()) &&
157            IsStructurallyEquivalent(Context, TS1->getReplacement(),
158                                     TS2->getReplacement());
159   }
160 
161   case TemplateName::SubstTemplateTemplateParmPack: {
162     SubstTemplateTemplateParmPackStorage
163         *P1 = N1.getAsSubstTemplateTemplateParmPack(),
164         *P2 = N2.getAsSubstTemplateTemplateParmPack();
165     return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
166                                     P2->getArgumentPack()) &&
167            IsStructurallyEquivalent(Context, P1->getParameterPack(),
168                                     P2->getParameterPack());
169   }
170   }
171   return false;
172 }
173 
174 /// Determine whether two template arguments are equivalent.
175 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
176                                      const TemplateArgument &Arg1,
177                                      const TemplateArgument &Arg2) {
178   if (Arg1.getKind() != Arg2.getKind())
179     return false;
180 
181   switch (Arg1.getKind()) {
182   case TemplateArgument::Null:
183     return true;
184 
185   case TemplateArgument::Type:
186     return Context.IsStructurallyEquivalent(Arg1.getAsType(), Arg2.getAsType());
187 
188   case TemplateArgument::Integral:
189     if (!Context.IsStructurallyEquivalent(Arg1.getIntegralType(),
190                                           Arg2.getIntegralType()))
191       return false;
192 
193     return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
194                                      Arg2.getAsIntegral());
195 
196   case TemplateArgument::Declaration:
197     return Context.IsStructurallyEquivalent(Arg1.getAsDecl(), Arg2.getAsDecl());
198 
199   case TemplateArgument::NullPtr:
200     return true; // FIXME: Is this correct?
201 
202   case TemplateArgument::Template:
203     return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
204                                     Arg2.getAsTemplate());
205 
206   case TemplateArgument::TemplateExpansion:
207     return IsStructurallyEquivalent(Context,
208                                     Arg1.getAsTemplateOrTemplatePattern(),
209                                     Arg2.getAsTemplateOrTemplatePattern());
210 
211   case TemplateArgument::Expression:
212     return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
213                                     Arg2.getAsExpr());
214 
215   case TemplateArgument::Pack:
216     if (Arg1.pack_size() != Arg2.pack_size())
217       return false;
218 
219     for (unsigned I = 0, N = Arg1.pack_size(); I != N; ++I)
220       if (!IsStructurallyEquivalent(Context, Arg1.pack_begin()[I],
221                                     Arg2.pack_begin()[I]))
222         return false;
223 
224     return true;
225   }
226 
227   llvm_unreachable("Invalid template argument kind");
228 }
229 
230 /// Determine structural equivalence for the common part of array
231 /// types.
232 static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
233                                           const ArrayType *Array1,
234                                           const ArrayType *Array2) {
235   if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
236                                 Array2->getElementType()))
237     return false;
238   if (Array1->getSizeModifier() != Array2->getSizeModifier())
239     return false;
240   if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
241     return false;
242 
243   return true;
244 }
245 
246 /// Determine structural equivalence of two types.
247 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
248                                      QualType T1, QualType T2) {
249   if (T1.isNull() || T2.isNull())
250     return T1.isNull() && T2.isNull();
251 
252   if (!Context.StrictTypeSpelling) {
253     // We aren't being strict about token-to-token equivalence of types,
254     // so map down to the canonical type.
255     T1 = Context.FromCtx.getCanonicalType(T1);
256     T2 = Context.ToCtx.getCanonicalType(T2);
257   }
258 
259   if (T1.getQualifiers() != T2.getQualifiers())
260     return false;
261 
262   Type::TypeClass TC = T1->getTypeClass();
263 
264   if (T1->getTypeClass() != T2->getTypeClass()) {
265     // Compare function types with prototypes vs. without prototypes as if
266     // both did not have prototypes.
267     if (T1->getTypeClass() == Type::FunctionProto &&
268         T2->getTypeClass() == Type::FunctionNoProto)
269       TC = Type::FunctionNoProto;
270     else if (T1->getTypeClass() == Type::FunctionNoProto &&
271              T2->getTypeClass() == Type::FunctionProto)
272       TC = Type::FunctionNoProto;
273     else
274       return false;
275   }
276 
277   switch (TC) {
278   case Type::Builtin:
279     // FIXME: Deal with Char_S/Char_U.
280     if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
281       return false;
282     break;
283 
284   case Type::Complex:
285     if (!IsStructurallyEquivalent(Context,
286                                   cast<ComplexType>(T1)->getElementType(),
287                                   cast<ComplexType>(T2)->getElementType()))
288       return false;
289     break;
290 
291   case Type::Adjusted:
292   case Type::Decayed:
293     if (!IsStructurallyEquivalent(Context,
294                                   cast<AdjustedType>(T1)->getOriginalType(),
295                                   cast<AdjustedType>(T2)->getOriginalType()))
296       return false;
297     break;
298 
299   case Type::Pointer:
300     if (!IsStructurallyEquivalent(Context,
301                                   cast<PointerType>(T1)->getPointeeType(),
302                                   cast<PointerType>(T2)->getPointeeType()))
303       return false;
304     break;
305 
306   case Type::BlockPointer:
307     if (!IsStructurallyEquivalent(Context,
308                                   cast<BlockPointerType>(T1)->getPointeeType(),
309                                   cast<BlockPointerType>(T2)->getPointeeType()))
310       return false;
311     break;
312 
313   case Type::LValueReference:
314   case Type::RValueReference: {
315     const auto *Ref1 = cast<ReferenceType>(T1);
316     const auto *Ref2 = cast<ReferenceType>(T2);
317     if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
318       return false;
319     if (Ref1->isInnerRef() != Ref2->isInnerRef())
320       return false;
321     if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
322                                   Ref2->getPointeeTypeAsWritten()))
323       return false;
324     break;
325   }
326 
327   case Type::MemberPointer: {
328     const auto *MemPtr1 = cast<MemberPointerType>(T1);
329     const auto *MemPtr2 = cast<MemberPointerType>(T2);
330     if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
331                                   MemPtr2->getPointeeType()))
332       return false;
333     if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
334                                   QualType(MemPtr2->getClass(), 0)))
335       return false;
336     break;
337   }
338 
339   case Type::ConstantArray: {
340     const auto *Array1 = cast<ConstantArrayType>(T1);
341     const auto *Array2 = cast<ConstantArrayType>(T2);
342     if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
343       return false;
344 
345     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
346       return false;
347     break;
348   }
349 
350   case Type::IncompleteArray:
351     if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
352                                        cast<ArrayType>(T2)))
353       return false;
354     break;
355 
356   case Type::VariableArray: {
357     const auto *Array1 = cast<VariableArrayType>(T1);
358     const auto *Array2 = cast<VariableArrayType>(T2);
359     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
360                                   Array2->getSizeExpr()))
361       return false;
362 
363     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
364       return false;
365 
366     break;
367   }
368 
369   case Type::DependentSizedArray: {
370     const auto *Array1 = cast<DependentSizedArrayType>(T1);
371     const auto *Array2 = cast<DependentSizedArrayType>(T2);
372     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
373                                   Array2->getSizeExpr()))
374       return false;
375 
376     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
377       return false;
378 
379     break;
380   }
381 
382   case Type::DependentAddressSpace: {
383     const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);
384     const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);
385     if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),
386                                   DepAddressSpace2->getAddrSpaceExpr()))
387       return false;
388     if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
389                                   DepAddressSpace2->getPointeeType()))
390       return false;
391 
392     break;
393   }
394 
395   case Type::DependentSizedExtVector: {
396     const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);
397     const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);
398     if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
399                                   Vec2->getSizeExpr()))
400       return false;
401     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
402                                   Vec2->getElementType()))
403       return false;
404     break;
405   }
406 
407   case Type::Vector:
408   case Type::ExtVector: {
409     const auto *Vec1 = cast<VectorType>(T1);
410     const auto *Vec2 = cast<VectorType>(T2);
411     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
412                                   Vec2->getElementType()))
413       return false;
414     if (Vec1->getNumElements() != Vec2->getNumElements())
415       return false;
416     if (Vec1->getVectorKind() != Vec2->getVectorKind())
417       return false;
418     break;
419   }
420 
421   case Type::FunctionProto: {
422     const auto *Proto1 = cast<FunctionProtoType>(T1);
423     const auto *Proto2 = cast<FunctionProtoType>(T2);
424     if (Proto1->getNumParams() != Proto2->getNumParams())
425       return false;
426     for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
427       if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
428                                     Proto2->getParamType(I)))
429         return false;
430     }
431     if (Proto1->isVariadic() != Proto2->isVariadic())
432       return false;
433     if (Proto1->getExceptionSpecType() != Proto2->getExceptionSpecType())
434       return false;
435     if (Proto1->getExceptionSpecType() == EST_Dynamic) {
436       if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
437         return false;
438       for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
439         if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
440                                       Proto2->getExceptionType(I)))
441           return false;
442       }
443     } else if (Proto1->getExceptionSpecType() == EST_ComputedNoexcept) {
444       if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
445                                     Proto2->getNoexceptExpr()))
446         return false;
447     }
448     if (Proto1->getTypeQuals() != Proto2->getTypeQuals())
449       return false;
450 
451     // Fall through to check the bits common with FunctionNoProtoType.
452     LLVM_FALLTHROUGH;
453   }
454 
455   case Type::FunctionNoProto: {
456     const auto *Function1 = cast<FunctionType>(T1);
457     const auto *Function2 = cast<FunctionType>(T2);
458     if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
459                                   Function2->getReturnType()))
460       return false;
461     if (Function1->getExtInfo() != Function2->getExtInfo())
462       return false;
463     break;
464   }
465 
466   case Type::UnresolvedUsing:
467     if (!IsStructurallyEquivalent(Context,
468                                   cast<UnresolvedUsingType>(T1)->getDecl(),
469                                   cast<UnresolvedUsingType>(T2)->getDecl()))
470       return false;
471     break;
472 
473   case Type::Attributed:
474     if (!IsStructurallyEquivalent(Context,
475                                   cast<AttributedType>(T1)->getModifiedType(),
476                                   cast<AttributedType>(T2)->getModifiedType()))
477       return false;
478     if (!IsStructurallyEquivalent(
479             Context, cast<AttributedType>(T1)->getEquivalentType(),
480             cast<AttributedType>(T2)->getEquivalentType()))
481       return false;
482     break;
483 
484   case Type::Paren:
485     if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
486                                   cast<ParenType>(T2)->getInnerType()))
487       return false;
488     break;
489 
490   case Type::Typedef:
491     if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
492                                   cast<TypedefType>(T2)->getDecl()))
493       return false;
494     break;
495 
496   case Type::TypeOfExpr:
497     if (!IsStructurallyEquivalent(
498             Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
499             cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
500       return false;
501     break;
502 
503   case Type::TypeOf:
504     if (!IsStructurallyEquivalent(Context,
505                                   cast<TypeOfType>(T1)->getUnderlyingType(),
506                                   cast<TypeOfType>(T2)->getUnderlyingType()))
507       return false;
508     break;
509 
510   case Type::UnaryTransform:
511     if (!IsStructurallyEquivalent(
512             Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
513             cast<UnaryTransformType>(T2)->getUnderlyingType()))
514       return false;
515     break;
516 
517   case Type::Decltype:
518     if (!IsStructurallyEquivalent(Context,
519                                   cast<DecltypeType>(T1)->getUnderlyingExpr(),
520                                   cast<DecltypeType>(T2)->getUnderlyingExpr()))
521       return false;
522     break;
523 
524   case Type::Auto:
525     if (!IsStructurallyEquivalent(Context, cast<AutoType>(T1)->getDeducedType(),
526                                   cast<AutoType>(T2)->getDeducedType()))
527       return false;
528     break;
529 
530   case Type::DeducedTemplateSpecialization: {
531     const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
532     const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
533     if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
534                                   DT2->getTemplateName()))
535       return false;
536     if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
537                                   DT2->getDeducedType()))
538       return false;
539     break;
540   }
541 
542   case Type::Record:
543   case Type::Enum:
544     if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
545                                   cast<TagType>(T2)->getDecl()))
546       return false;
547     break;
548 
549   case Type::TemplateTypeParm: {
550     const auto *Parm1 = cast<TemplateTypeParmType>(T1);
551     const auto *Parm2 = cast<TemplateTypeParmType>(T2);
552     if (Parm1->getDepth() != Parm2->getDepth())
553       return false;
554     if (Parm1->getIndex() != Parm2->getIndex())
555       return false;
556     if (Parm1->isParameterPack() != Parm2->isParameterPack())
557       return false;
558 
559     // Names of template type parameters are never significant.
560     break;
561   }
562 
563   case Type::SubstTemplateTypeParm: {
564     const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
565     const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
566     if (!IsStructurallyEquivalent(Context,
567                                   QualType(Subst1->getReplacedParameter(), 0),
568                                   QualType(Subst2->getReplacedParameter(), 0)))
569       return false;
570     if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
571                                   Subst2->getReplacementType()))
572       return false;
573     break;
574   }
575 
576   case Type::SubstTemplateTypeParmPack: {
577     const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
578     const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
579     if (!IsStructurallyEquivalent(Context,
580                                   QualType(Subst1->getReplacedParameter(), 0),
581                                   QualType(Subst2->getReplacedParameter(), 0)))
582       return false;
583     if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
584                                   Subst2->getArgumentPack()))
585       return false;
586     break;
587   }
588 
589   case Type::TemplateSpecialization: {
590     const auto *Spec1 = cast<TemplateSpecializationType>(T1);
591     const auto *Spec2 = cast<TemplateSpecializationType>(T2);
592     if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
593                                   Spec2->getTemplateName()))
594       return false;
595     if (Spec1->getNumArgs() != Spec2->getNumArgs())
596       return false;
597     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
598       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
599                                     Spec2->getArg(I)))
600         return false;
601     }
602     break;
603   }
604 
605   case Type::Elaborated: {
606     const auto *Elab1 = cast<ElaboratedType>(T1);
607     const auto *Elab2 = cast<ElaboratedType>(T2);
608     // CHECKME: what if a keyword is ETK_None or ETK_typename ?
609     if (Elab1->getKeyword() != Elab2->getKeyword())
610       return false;
611     if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
612                                   Elab2->getQualifier()))
613       return false;
614     if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
615                                   Elab2->getNamedType()))
616       return false;
617     break;
618   }
619 
620   case Type::InjectedClassName: {
621     const auto *Inj1 = cast<InjectedClassNameType>(T1);
622     const auto *Inj2 = cast<InjectedClassNameType>(T2);
623     if (!IsStructurallyEquivalent(Context,
624                                   Inj1->getInjectedSpecializationType(),
625                                   Inj2->getInjectedSpecializationType()))
626       return false;
627     break;
628   }
629 
630   case Type::DependentName: {
631     const auto *Typename1 = cast<DependentNameType>(T1);
632     const auto *Typename2 = cast<DependentNameType>(T2);
633     if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
634                                   Typename2->getQualifier()))
635       return false;
636     if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
637                                   Typename2->getIdentifier()))
638       return false;
639 
640     break;
641   }
642 
643   case Type::DependentTemplateSpecialization: {
644     const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
645     const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
646     if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
647                                   Spec2->getQualifier()))
648       return false;
649     if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
650                                   Spec2->getIdentifier()))
651       return false;
652     if (Spec1->getNumArgs() != Spec2->getNumArgs())
653       return false;
654     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
655       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
656                                     Spec2->getArg(I)))
657         return false;
658     }
659     break;
660   }
661 
662   case Type::PackExpansion:
663     if (!IsStructurallyEquivalent(Context,
664                                   cast<PackExpansionType>(T1)->getPattern(),
665                                   cast<PackExpansionType>(T2)->getPattern()))
666       return false;
667     break;
668 
669   case Type::ObjCInterface: {
670     const auto *Iface1 = cast<ObjCInterfaceType>(T1);
671     const auto *Iface2 = cast<ObjCInterfaceType>(T2);
672     if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
673                                   Iface2->getDecl()))
674       return false;
675     break;
676   }
677 
678   case Type::ObjCTypeParam: {
679     const auto *Obj1 = cast<ObjCTypeParamType>(T1);
680     const auto *Obj2 = cast<ObjCTypeParamType>(T2);
681     if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
682       return false;
683 
684     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
685       return false;
686     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
687       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
688                                     Obj2->getProtocol(I)))
689         return false;
690     }
691     break;
692   }
693 
694   case Type::ObjCObject: {
695     const auto *Obj1 = cast<ObjCObjectType>(T1);
696     const auto *Obj2 = cast<ObjCObjectType>(T2);
697     if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
698                                   Obj2->getBaseType()))
699       return false;
700     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
701       return false;
702     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
703       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
704                                     Obj2->getProtocol(I)))
705         return false;
706     }
707     break;
708   }
709 
710   case Type::ObjCObjectPointer: {
711     const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
712     const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
713     if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
714                                   Ptr2->getPointeeType()))
715       return false;
716     break;
717   }
718 
719   case Type::Atomic:
720     if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
721                                   cast<AtomicType>(T2)->getValueType()))
722       return false;
723     break;
724 
725   case Type::Pipe:
726     if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
727                                   cast<PipeType>(T2)->getElementType()))
728       return false;
729     break;
730   } // end switch
731 
732   return true;
733 }
734 
735 /// Determine structural equivalence of two fields.
736 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
737                                      FieldDecl *Field1, FieldDecl *Field2) {
738   const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
739 
740   // For anonymous structs/unions, match up the anonymous struct/union type
741   // declarations directly, so that we don't go off searching for anonymous
742   // types
743   if (Field1->isAnonymousStructOrUnion() &&
744       Field2->isAnonymousStructOrUnion()) {
745     RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
746     RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
747     return IsStructurallyEquivalent(Context, D1, D2);
748   }
749 
750   // Check for equivalent field names.
751   IdentifierInfo *Name1 = Field1->getIdentifier();
752   IdentifierInfo *Name2 = Field2->getIdentifier();
753   if (!::IsStructurallyEquivalent(Name1, Name2)) {
754     if (Context.Complain) {
755       Context.Diag2(Owner2->getLocation(),
756                     Context.ErrorOnTagTypeMismatch
757                         ? diag::err_odr_tag_type_inconsistent
758                         : diag::warn_odr_tag_type_inconsistent)
759           << Context.ToCtx.getTypeDeclType(Owner2);
760       Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
761           << Field2->getDeclName();
762       Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
763           << Field1->getDeclName();
764     }
765     return false;
766   }
767 
768   if (!IsStructurallyEquivalent(Context, Field1->getType(),
769                                 Field2->getType())) {
770     if (Context.Complain) {
771       Context.Diag2(Owner2->getLocation(),
772                     Context.ErrorOnTagTypeMismatch
773                         ? diag::err_odr_tag_type_inconsistent
774                         : diag::warn_odr_tag_type_inconsistent)
775           << Context.ToCtx.getTypeDeclType(Owner2);
776       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
777           << Field2->getDeclName() << Field2->getType();
778       Context.Diag1(Field1->getLocation(), diag::note_odr_field)
779           << Field1->getDeclName() << Field1->getType();
780     }
781     return false;
782   }
783 
784   if (Field1->isBitField() != Field2->isBitField()) {
785     if (Context.Complain) {
786       Context.Diag2(Owner2->getLocation(),
787                     Context.ErrorOnTagTypeMismatch
788                         ? diag::err_odr_tag_type_inconsistent
789                         : diag::warn_odr_tag_type_inconsistent)
790           << Context.ToCtx.getTypeDeclType(Owner2);
791       if (Field1->isBitField()) {
792         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
793             << Field1->getDeclName() << Field1->getType()
794             << Field1->getBitWidthValue(Context.FromCtx);
795         Context.Diag2(Field2->getLocation(), diag::note_odr_not_bit_field)
796             << Field2->getDeclName();
797       } else {
798         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
799             << Field2->getDeclName() << Field2->getType()
800             << Field2->getBitWidthValue(Context.ToCtx);
801         Context.Diag1(Field1->getLocation(), diag::note_odr_not_bit_field)
802             << Field1->getDeclName();
803       }
804     }
805     return false;
806   }
807 
808   if (Field1->isBitField()) {
809     // Make sure that the bit-fields are the same length.
810     unsigned Bits1 = Field1->getBitWidthValue(Context.FromCtx);
811     unsigned Bits2 = Field2->getBitWidthValue(Context.ToCtx);
812 
813     if (Bits1 != Bits2) {
814       if (Context.Complain) {
815         Context.Diag2(Owner2->getLocation(),
816                       Context.ErrorOnTagTypeMismatch
817                           ? diag::err_odr_tag_type_inconsistent
818                           : diag::warn_odr_tag_type_inconsistent)
819             << Context.ToCtx.getTypeDeclType(Owner2);
820         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
821             << Field2->getDeclName() << Field2->getType() << Bits2;
822         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
823             << Field1->getDeclName() << Field1->getType() << Bits1;
824       }
825       return false;
826     }
827   }
828 
829   return true;
830 }
831 
832 /// Determine structural equivalence of two records.
833 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
834                                      RecordDecl *D1, RecordDecl *D2) {
835   if (D1->isUnion() != D2->isUnion()) {
836     if (Context.Complain) {
837       Context.Diag2(D2->getLocation(),
838                     Context.ErrorOnTagTypeMismatch
839                         ? diag::err_odr_tag_type_inconsistent
840                         : diag::warn_odr_tag_type_inconsistent)
841           << Context.ToCtx.getTypeDeclType(D2);
842       Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
843           << D1->getDeclName() << (unsigned)D1->getTagKind();
844     }
845     return false;
846   }
847 
848   if (D1->isAnonymousStructOrUnion() && D2->isAnonymousStructOrUnion()) {
849     // If both anonymous structs/unions are in a record context, make sure
850     // they occur in the same location in the context records.
851     if (Optional<unsigned> Index1 =
852             StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
853       if (Optional<unsigned> Index2 =
854               StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
855                   D2)) {
856         if (*Index1 != *Index2)
857           return false;
858       }
859     }
860   }
861 
862   // If both declarations are class template specializations, we know
863   // the ODR applies, so check the template and template arguments.
864   const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
865   const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
866   if (Spec1 && Spec2) {
867     // Check that the specialized templates are the same.
868     if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
869                                   Spec2->getSpecializedTemplate()))
870       return false;
871 
872     // Check that the template arguments are the same.
873     if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
874       return false;
875 
876     for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
877       if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
878                                     Spec2->getTemplateArgs().get(I)))
879         return false;
880   }
881   // If one is a class template specialization and the other is not, these
882   // structures are different.
883   else if (Spec1 || Spec2)
884     return false;
885 
886   // Compare the definitions of these two records. If either or both are
887   // incomplete, we assume that they are equivalent.
888   D1 = D1->getDefinition();
889   D2 = D2->getDefinition();
890   if (!D1 || !D2)
891     return true;
892 
893   if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
894     if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
895       if (D1CXX->hasExternalLexicalStorage() &&
896           !D1CXX->isCompleteDefinition()) {
897         D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
898       }
899 
900       if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
901         if (Context.Complain) {
902           Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
903               << Context.ToCtx.getTypeDeclType(D2);
904           Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
905               << D2CXX->getNumBases();
906           Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
907               << D1CXX->getNumBases();
908         }
909         return false;
910       }
911 
912       // Check the base classes.
913       for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
914                                               BaseEnd1 = D1CXX->bases_end(),
915                                               Base2 = D2CXX->bases_begin();
916            Base1 != BaseEnd1; ++Base1, ++Base2) {
917         if (!IsStructurallyEquivalent(Context, Base1->getType(),
918                                       Base2->getType())) {
919           if (Context.Complain) {
920             Context.Diag2(D2->getLocation(),
921                           diag::warn_odr_tag_type_inconsistent)
922                 << Context.ToCtx.getTypeDeclType(D2);
923             Context.Diag2(Base2->getLocStart(), diag::note_odr_base)
924                 << Base2->getType() << Base2->getSourceRange();
925             Context.Diag1(Base1->getLocStart(), diag::note_odr_base)
926                 << Base1->getType() << Base1->getSourceRange();
927           }
928           return false;
929         }
930 
931         // Check virtual vs. non-virtual inheritance mismatch.
932         if (Base1->isVirtual() != Base2->isVirtual()) {
933           if (Context.Complain) {
934             Context.Diag2(D2->getLocation(),
935                           diag::warn_odr_tag_type_inconsistent)
936                 << Context.ToCtx.getTypeDeclType(D2);
937             Context.Diag2(Base2->getLocStart(), diag::note_odr_virtual_base)
938                 << Base2->isVirtual() << Base2->getSourceRange();
939             Context.Diag1(Base1->getLocStart(), diag::note_odr_base)
940                 << Base1->isVirtual() << Base1->getSourceRange();
941           }
942           return false;
943         }
944       }
945     } else if (D1CXX->getNumBases() > 0) {
946       if (Context.Complain) {
947         Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
948             << Context.ToCtx.getTypeDeclType(D2);
949         const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
950         Context.Diag1(Base1->getLocStart(), diag::note_odr_base)
951             << Base1->getType() << Base1->getSourceRange();
952         Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
953       }
954       return false;
955     }
956   }
957 
958   // Check the fields for consistency.
959   RecordDecl::field_iterator Field2 = D2->field_begin(),
960                              Field2End = D2->field_end();
961   for (RecordDecl::field_iterator Field1 = D1->field_begin(),
962                                   Field1End = D1->field_end();
963        Field1 != Field1End; ++Field1, ++Field2) {
964     if (Field2 == Field2End) {
965       if (Context.Complain) {
966         Context.Diag2(D2->getLocation(),
967                       Context.ErrorOnTagTypeMismatch
968                           ? diag::err_odr_tag_type_inconsistent
969                           : diag::warn_odr_tag_type_inconsistent)
970             << Context.ToCtx.getTypeDeclType(D2);
971         Context.Diag1(Field1->getLocation(), diag::note_odr_field)
972             << Field1->getDeclName() << Field1->getType();
973         Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
974       }
975       return false;
976     }
977 
978     if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
979       return false;
980   }
981 
982   if (Field2 != Field2End) {
983     if (Context.Complain) {
984       Context.Diag2(D2->getLocation(),
985                     Context.ErrorOnTagTypeMismatch
986                         ? diag::err_odr_tag_type_inconsistent
987                         : diag::warn_odr_tag_type_inconsistent)
988           << Context.ToCtx.getTypeDeclType(D2);
989       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
990           << Field2->getDeclName() << Field2->getType();
991       Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
992     }
993     return false;
994   }
995 
996   return true;
997 }
998 
999 /// Determine structural equivalence of two enums.
1000 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1001                                      EnumDecl *D1, EnumDecl *D2) {
1002   EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1003                                 EC2End = D2->enumerator_end();
1004   for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1005                                      EC1End = D1->enumerator_end();
1006        EC1 != EC1End; ++EC1, ++EC2) {
1007     if (EC2 == EC2End) {
1008       if (Context.Complain) {
1009         Context.Diag2(D2->getLocation(),
1010                       Context.ErrorOnTagTypeMismatch
1011                           ? diag::err_odr_tag_type_inconsistent
1012                           : diag::warn_odr_tag_type_inconsistent)
1013             << Context.ToCtx.getTypeDeclType(D2);
1014         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1015             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1016         Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1017       }
1018       return false;
1019     }
1020 
1021     llvm::APSInt Val1 = EC1->getInitVal();
1022     llvm::APSInt Val2 = EC2->getInitVal();
1023     if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1024         !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1025       if (Context.Complain) {
1026         Context.Diag2(D2->getLocation(),
1027                       Context.ErrorOnTagTypeMismatch
1028                           ? diag::err_odr_tag_type_inconsistent
1029                           : diag::warn_odr_tag_type_inconsistent)
1030             << Context.ToCtx.getTypeDeclType(D2);
1031         Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1032             << EC2->getDeclName() << EC2->getInitVal().toString(10);
1033         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1034             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1035       }
1036       return false;
1037     }
1038   }
1039 
1040   if (EC2 != EC2End) {
1041     if (Context.Complain) {
1042       Context.Diag2(D2->getLocation(),
1043                     Context.ErrorOnTagTypeMismatch
1044                         ? diag::err_odr_tag_type_inconsistent
1045                         : diag::warn_odr_tag_type_inconsistent)
1046           << Context.ToCtx.getTypeDeclType(D2);
1047       Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1048           << EC2->getDeclName() << EC2->getInitVal().toString(10);
1049       Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1050     }
1051     return false;
1052   }
1053 
1054   return true;
1055 }
1056 
1057 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1058                                      TemplateParameterList *Params1,
1059                                      TemplateParameterList *Params2) {
1060   if (Params1->size() != Params2->size()) {
1061     if (Context.Complain) {
1062       Context.Diag2(Params2->getTemplateLoc(),
1063                     diag::err_odr_different_num_template_parameters)
1064           << Params1->size() << Params2->size();
1065       Context.Diag1(Params1->getTemplateLoc(),
1066                     diag::note_odr_template_parameter_list);
1067     }
1068     return false;
1069   }
1070 
1071   for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1072     if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1073       if (Context.Complain) {
1074         Context.Diag2(Params2->getParam(I)->getLocation(),
1075                       diag::err_odr_different_template_parameter_kind);
1076         Context.Diag1(Params1->getParam(I)->getLocation(),
1077                       diag::note_odr_template_parameter_here);
1078       }
1079       return false;
1080     }
1081 
1082     if (!Context.IsStructurallyEquivalent(Params1->getParam(I),
1083                                           Params2->getParam(I)))
1084       return false;
1085   }
1086 
1087   return true;
1088 }
1089 
1090 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1091                                      TemplateTypeParmDecl *D1,
1092                                      TemplateTypeParmDecl *D2) {
1093   if (D1->isParameterPack() != D2->isParameterPack()) {
1094     if (Context.Complain) {
1095       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1096           << D2->isParameterPack();
1097       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1098           << D1->isParameterPack();
1099     }
1100     return false;
1101   }
1102 
1103   return true;
1104 }
1105 
1106 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1107                                      NonTypeTemplateParmDecl *D1,
1108                                      NonTypeTemplateParmDecl *D2) {
1109   if (D1->isParameterPack() != D2->isParameterPack()) {
1110     if (Context.Complain) {
1111       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1112           << D2->isParameterPack();
1113       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1114           << D1->isParameterPack();
1115     }
1116     return false;
1117   }
1118 
1119   // Check types.
1120   if (!Context.IsStructurallyEquivalent(D1->getType(), D2->getType())) {
1121     if (Context.Complain) {
1122       Context.Diag2(D2->getLocation(),
1123                     diag::err_odr_non_type_parameter_type_inconsistent)
1124           << D2->getType() << D1->getType();
1125       Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1126           << D1->getType();
1127     }
1128     return false;
1129   }
1130 
1131   return true;
1132 }
1133 
1134 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1135                                      TemplateTemplateParmDecl *D1,
1136                                      TemplateTemplateParmDecl *D2) {
1137   if (D1->isParameterPack() != D2->isParameterPack()) {
1138     if (Context.Complain) {
1139       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1140           << D2->isParameterPack();
1141       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1142           << D1->isParameterPack();
1143     }
1144     return false;
1145   }
1146 
1147   // Check template parameter lists.
1148   return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1149                                   D2->getTemplateParameters());
1150 }
1151 
1152 static bool IsTemplateDeclCommonStructurallyEquivalent(
1153     StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1154   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1155     return false;
1156   if (!D1->getIdentifier()) // Special name
1157     if (D1->getNameAsString() != D2->getNameAsString())
1158       return false;
1159   return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1160                                   D2->getTemplateParameters());
1161 }
1162 
1163 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1164                                      ClassTemplateDecl *D1,
1165                                      ClassTemplateDecl *D2) {
1166   // Check template parameters.
1167   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1168     return false;
1169 
1170   // Check the templated declaration.
1171   return Context.IsStructurallyEquivalent(D1->getTemplatedDecl(),
1172                                           D2->getTemplatedDecl());
1173 }
1174 
1175 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1176                                      FunctionTemplateDecl *D1,
1177                                      FunctionTemplateDecl *D2) {
1178   // Check template parameters.
1179   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1180     return false;
1181 
1182   // Check the templated declaration.
1183   return Context.IsStructurallyEquivalent(D1->getTemplatedDecl()->getType(),
1184                                           D2->getTemplatedDecl()->getType());
1185 }
1186 
1187 /// Determine structural equivalence of two declarations.
1188 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1189                                      Decl *D1, Decl *D2) {
1190   // FIXME: Check for known structural equivalences via a callback of some sort.
1191 
1192   // Check whether we already know that these two declarations are not
1193   // structurally equivalent.
1194   if (Context.NonEquivalentDecls.count(
1195           std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl())))
1196     return false;
1197 
1198   // Determine whether we've already produced a tentative equivalence for D1.
1199   Decl *&EquivToD1 = Context.TentativeEquivalences[D1->getCanonicalDecl()];
1200   if (EquivToD1)
1201     return EquivToD1 == D2->getCanonicalDecl();
1202 
1203   // Produce a tentative equivalence D1 <-> D2, which will be checked later.
1204   EquivToD1 = D2->getCanonicalDecl();
1205   Context.DeclsToCheck.push_back(D1->getCanonicalDecl());
1206   return true;
1207 }
1208 
1209 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1210                                                       unsigned DiagID) {
1211   assert(Complain && "Not allowed to complain");
1212   if (LastDiagFromC2)
1213     FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1214   LastDiagFromC2 = false;
1215   return FromCtx.getDiagnostics().Report(Loc, DiagID);
1216 }
1217 
1218 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1219                                                       unsigned DiagID) {
1220   assert(Complain && "Not allowed to complain");
1221   if (!LastDiagFromC2)
1222     ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1223   LastDiagFromC2 = true;
1224   return ToCtx.getDiagnostics().Report(Loc, DiagID);
1225 }
1226 
1227 Optional<unsigned>
1228 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1229   ASTContext &Context = Anon->getASTContext();
1230   QualType AnonTy = Context.getRecordType(Anon);
1231 
1232   const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1233   if (!Owner)
1234     return None;
1235 
1236   unsigned Index = 0;
1237   for (const auto *D : Owner->noload_decls()) {
1238     const auto *F = dyn_cast<FieldDecl>(D);
1239     if (!F)
1240       continue;
1241 
1242     if (F->isAnonymousStructOrUnion()) {
1243       if (Context.hasSameType(F->getType(), AnonTy))
1244         break;
1245       ++Index;
1246       continue;
1247     }
1248 
1249     // If the field looks like this:
1250     // struct { ... } A;
1251     QualType FieldType = F->getType();
1252     // In case of nested structs.
1253     while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1254       FieldType = ElabType->getNamedType();
1255 
1256     if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1257       const RecordDecl *RecDecl = RecType->getDecl();
1258       if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1259         if (Context.hasSameType(FieldType, AnonTy))
1260           break;
1261         ++Index;
1262         continue;
1263       }
1264     }
1265   }
1266 
1267   return Index;
1268 }
1269 
1270 bool StructuralEquivalenceContext::IsStructurallyEquivalent(Decl *D1,
1271                                                             Decl *D2) {
1272   if (!::IsStructurallyEquivalent(*this, D1, D2))
1273     return false;
1274 
1275   return !Finish();
1276 }
1277 
1278 bool StructuralEquivalenceContext::IsStructurallyEquivalent(QualType T1,
1279                                                             QualType T2) {
1280   if (!::IsStructurallyEquivalent(*this, T1, T2))
1281     return false;
1282 
1283   return !Finish();
1284 }
1285 
1286 bool StructuralEquivalenceContext::Finish() {
1287   while (!DeclsToCheck.empty()) {
1288     // Check the next declaration.
1289     Decl *D1 = DeclsToCheck.front();
1290     DeclsToCheck.pop_front();
1291 
1292     Decl *D2 = TentativeEquivalences[D1];
1293     assert(D2 && "Unrecorded tentative equivalence?");
1294 
1295     bool Equivalent = true;
1296 
1297     // FIXME: Switch on all declaration kinds. For now, we're just going to
1298     // check the obvious ones.
1299     if (auto *Record1 = dyn_cast<RecordDecl>(D1)) {
1300       if (auto *Record2 = dyn_cast<RecordDecl>(D2)) {
1301         // Check for equivalent structure names.
1302         IdentifierInfo *Name1 = Record1->getIdentifier();
1303         if (!Name1 && Record1->getTypedefNameForAnonDecl())
1304           Name1 = Record1->getTypedefNameForAnonDecl()->getIdentifier();
1305         IdentifierInfo *Name2 = Record2->getIdentifier();
1306         if (!Name2 && Record2->getTypedefNameForAnonDecl())
1307           Name2 = Record2->getTypedefNameForAnonDecl()->getIdentifier();
1308         if (!::IsStructurallyEquivalent(Name1, Name2) ||
1309             !::IsStructurallyEquivalent(*this, Record1, Record2))
1310           Equivalent = false;
1311       } else {
1312         // Record/non-record mismatch.
1313         Equivalent = false;
1314       }
1315     } else if (auto *Enum1 = dyn_cast<EnumDecl>(D1)) {
1316       if (auto *Enum2 = dyn_cast<EnumDecl>(D2)) {
1317         // Check for equivalent enum names.
1318         IdentifierInfo *Name1 = Enum1->getIdentifier();
1319         if (!Name1 && Enum1->getTypedefNameForAnonDecl())
1320           Name1 = Enum1->getTypedefNameForAnonDecl()->getIdentifier();
1321         IdentifierInfo *Name2 = Enum2->getIdentifier();
1322         if (!Name2 && Enum2->getTypedefNameForAnonDecl())
1323           Name2 = Enum2->getTypedefNameForAnonDecl()->getIdentifier();
1324         if (!::IsStructurallyEquivalent(Name1, Name2) ||
1325             !::IsStructurallyEquivalent(*this, Enum1, Enum2))
1326           Equivalent = false;
1327       } else {
1328         // Enum/non-enum mismatch
1329         Equivalent = false;
1330       }
1331     } else if (const auto *Typedef1 = dyn_cast<TypedefNameDecl>(D1)) {
1332       if (const auto *Typedef2 = dyn_cast<TypedefNameDecl>(D2)) {
1333         if (!::IsStructurallyEquivalent(Typedef1->getIdentifier(),
1334                                         Typedef2->getIdentifier()) ||
1335             !::IsStructurallyEquivalent(*this, Typedef1->getUnderlyingType(),
1336                                         Typedef2->getUnderlyingType()))
1337           Equivalent = false;
1338       } else {
1339         // Typedef/non-typedef mismatch.
1340         Equivalent = false;
1341       }
1342     } else if (auto *ClassTemplate1 = dyn_cast<ClassTemplateDecl>(D1)) {
1343       if (auto *ClassTemplate2 = dyn_cast<ClassTemplateDecl>(D2)) {
1344         if (!::IsStructurallyEquivalent(*this, ClassTemplate1,
1345                                         ClassTemplate2))
1346           Equivalent = false;
1347       } else {
1348         // Class template/non-class-template mismatch.
1349         Equivalent = false;
1350       }
1351     } else if (auto *FunctionTemplate1 = dyn_cast<FunctionTemplateDecl>(D1)) {
1352       if (auto *FunctionTemplate2 = dyn_cast<FunctionTemplateDecl>(D2)) {
1353         if (!::IsStructurallyEquivalent(*this, FunctionTemplate1,
1354                                         FunctionTemplate2))
1355           Equivalent = false;
1356       } else {
1357         // Class template/non-class-template mismatch.
1358         Equivalent = false;
1359       }
1360     } else if (auto *TTP1 = dyn_cast<TemplateTypeParmDecl>(D1)) {
1361       if (auto *TTP2 = dyn_cast<TemplateTypeParmDecl>(D2)) {
1362         if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1363           Equivalent = false;
1364       } else {
1365         // Kind mismatch.
1366         Equivalent = false;
1367       }
1368     } else if (auto *NTTP1 = dyn_cast<NonTypeTemplateParmDecl>(D1)) {
1369       if (auto *NTTP2 = dyn_cast<NonTypeTemplateParmDecl>(D2)) {
1370         if (!::IsStructurallyEquivalent(*this, NTTP1, NTTP2))
1371           Equivalent = false;
1372       } else {
1373         // Kind mismatch.
1374         Equivalent = false;
1375       }
1376     } else if (auto *TTP1 = dyn_cast<TemplateTemplateParmDecl>(D1)) {
1377       if (auto *TTP2 = dyn_cast<TemplateTemplateParmDecl>(D2)) {
1378         if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1379           Equivalent = false;
1380       } else {
1381         // Kind mismatch.
1382         Equivalent = false;
1383       }
1384     }
1385 
1386     if (!Equivalent) {
1387       // Note that these two declarations are not equivalent (and we already
1388       // know about it).
1389       NonEquivalentDecls.insert(
1390           std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl()));
1391       return true;
1392     }
1393     // FIXME: Check other declaration kinds!
1394   }
1395 
1396   return false;
1397 }
1398