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