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