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   if (!Context.StrictTypeSpelling) {
254     // We aren't being strict about token-to-token equivalence of types,
255     // so map down to the canonical type.
256     T1 = Context.FromCtx.getCanonicalType(T1);
257     T2 = Context.ToCtx.getCanonicalType(T2);
258   }
259 
260   if (T1.getQualifiers() != T2.getQualifiers())
261     return false;
262 
263   Type::TypeClass TC = T1->getTypeClass();
264 
265   if (T1->getTypeClass() != T2->getTypeClass()) {
266     // Compare function types with prototypes vs. without prototypes as if
267     // both did not have prototypes.
268     if (T1->getTypeClass() == Type::FunctionProto &&
269         T2->getTypeClass() == Type::FunctionNoProto)
270       TC = Type::FunctionNoProto;
271     else if (T1->getTypeClass() == Type::FunctionNoProto &&
272              T2->getTypeClass() == Type::FunctionProto)
273       TC = Type::FunctionNoProto;
274     else
275       return false;
276   }
277 
278   switch (TC) {
279   case Type::Builtin:
280     // FIXME: Deal with Char_S/Char_U.
281     if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
282       return false;
283     break;
284 
285   case Type::Complex:
286     if (!IsStructurallyEquivalent(Context,
287                                   cast<ComplexType>(T1)->getElementType(),
288                                   cast<ComplexType>(T2)->getElementType()))
289       return false;
290     break;
291 
292   case Type::Adjusted:
293   case Type::Decayed:
294     if (!IsStructurallyEquivalent(Context,
295                                   cast<AdjustedType>(T1)->getOriginalType(),
296                                   cast<AdjustedType>(T2)->getOriginalType()))
297       return false;
298     break;
299 
300   case Type::Pointer:
301     if (!IsStructurallyEquivalent(Context,
302                                   cast<PointerType>(T1)->getPointeeType(),
303                                   cast<PointerType>(T2)->getPointeeType()))
304       return false;
305     break;
306 
307   case Type::BlockPointer:
308     if (!IsStructurallyEquivalent(Context,
309                                   cast<BlockPointerType>(T1)->getPointeeType(),
310                                   cast<BlockPointerType>(T2)->getPointeeType()))
311       return false;
312     break;
313 
314   case Type::LValueReference:
315   case Type::RValueReference: {
316     const auto *Ref1 = cast<ReferenceType>(T1);
317     const auto *Ref2 = cast<ReferenceType>(T2);
318     if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
319       return false;
320     if (Ref1->isInnerRef() != Ref2->isInnerRef())
321       return false;
322     if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
323                                   Ref2->getPointeeTypeAsWritten()))
324       return false;
325     break;
326   }
327 
328   case Type::MemberPointer: {
329     const auto *MemPtr1 = cast<MemberPointerType>(T1);
330     const auto *MemPtr2 = cast<MemberPointerType>(T2);
331     if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
332                                   MemPtr2->getPointeeType()))
333       return false;
334     if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
335                                   QualType(MemPtr2->getClass(), 0)))
336       return false;
337     break;
338   }
339 
340   case Type::ConstantArray: {
341     const auto *Array1 = cast<ConstantArrayType>(T1);
342     const auto *Array2 = cast<ConstantArrayType>(T2);
343     if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
344       return false;
345 
346     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
347       return false;
348     break;
349   }
350 
351   case Type::IncompleteArray:
352     if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
353                                        cast<ArrayType>(T2)))
354       return false;
355     break;
356 
357   case Type::VariableArray: {
358     const auto *Array1 = cast<VariableArrayType>(T1);
359     const auto *Array2 = cast<VariableArrayType>(T2);
360     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
361                                   Array2->getSizeExpr()))
362       return false;
363 
364     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
365       return false;
366 
367     break;
368   }
369 
370   case Type::DependentSizedArray: {
371     const auto *Array1 = cast<DependentSizedArrayType>(T1);
372     const auto *Array2 = cast<DependentSizedArrayType>(T2);
373     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
374                                   Array2->getSizeExpr()))
375       return false;
376 
377     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
378       return false;
379 
380     break;
381   }
382 
383   case Type::DependentAddressSpace: {
384     const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);
385     const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);
386     if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),
387                                   DepAddressSpace2->getAddrSpaceExpr()))
388       return false;
389     if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
390                                   DepAddressSpace2->getPointeeType()))
391       return false;
392 
393     break;
394   }
395 
396   case Type::DependentSizedExtVector: {
397     const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);
398     const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);
399     if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
400                                   Vec2->getSizeExpr()))
401       return false;
402     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
403                                   Vec2->getElementType()))
404       return false;
405     break;
406   }
407 
408   case Type::Vector:
409   case Type::ExtVector: {
410     const auto *Vec1 = cast<VectorType>(T1);
411     const auto *Vec2 = cast<VectorType>(T2);
412     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
413                                   Vec2->getElementType()))
414       return false;
415     if (Vec1->getNumElements() != Vec2->getNumElements())
416       return false;
417     if (Vec1->getVectorKind() != Vec2->getVectorKind())
418       return false;
419     break;
420   }
421 
422   case Type::FunctionProto: {
423     const auto *Proto1 = cast<FunctionProtoType>(T1);
424     const auto *Proto2 = cast<FunctionProtoType>(T2);
425     if (Proto1->getNumParams() != Proto2->getNumParams())
426       return false;
427     for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
428       if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
429                                     Proto2->getParamType(I)))
430         return false;
431     }
432     if (Proto1->isVariadic() != Proto2->isVariadic())
433       return false;
434     if (Proto1->getExceptionSpecType() != Proto2->getExceptionSpecType())
435       return false;
436     if (Proto1->getExceptionSpecType() == EST_Dynamic) {
437       if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
438         return false;
439       for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
440         if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
441                                       Proto2->getExceptionType(I)))
442           return false;
443       }
444     } else if (isComputedNoexcept(Proto1->getExceptionSpecType())) {
445       if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
446                                     Proto2->getNoexceptExpr()))
447         return false;
448     }
449     if (Proto1->getTypeQuals() != Proto2->getTypeQuals())
450       return false;
451 
452     // Fall through to check the bits common with FunctionNoProtoType.
453     LLVM_FALLTHROUGH;
454   }
455 
456   case Type::FunctionNoProto: {
457     const auto *Function1 = cast<FunctionType>(T1);
458     const auto *Function2 = cast<FunctionType>(T2);
459     if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
460                                   Function2->getReturnType()))
461       return false;
462     if (Function1->getExtInfo() != Function2->getExtInfo())
463       return false;
464     break;
465   }
466 
467   case Type::UnresolvedUsing:
468     if (!IsStructurallyEquivalent(Context,
469                                   cast<UnresolvedUsingType>(T1)->getDecl(),
470                                   cast<UnresolvedUsingType>(T2)->getDecl()))
471       return false;
472     break;
473 
474   case Type::Attributed:
475     if (!IsStructurallyEquivalent(Context,
476                                   cast<AttributedType>(T1)->getModifiedType(),
477                                   cast<AttributedType>(T2)->getModifiedType()))
478       return false;
479     if (!IsStructurallyEquivalent(
480             Context, cast<AttributedType>(T1)->getEquivalentType(),
481             cast<AttributedType>(T2)->getEquivalentType()))
482       return false;
483     break;
484 
485   case Type::Paren:
486     if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
487                                   cast<ParenType>(T2)->getInnerType()))
488       return false;
489     break;
490 
491   case Type::Typedef:
492     if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
493                                   cast<TypedefType>(T2)->getDecl()))
494       return false;
495     break;
496 
497   case Type::TypeOfExpr:
498     if (!IsStructurallyEquivalent(
499             Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
500             cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
501       return false;
502     break;
503 
504   case Type::TypeOf:
505     if (!IsStructurallyEquivalent(Context,
506                                   cast<TypeOfType>(T1)->getUnderlyingType(),
507                                   cast<TypeOfType>(T2)->getUnderlyingType()))
508       return false;
509     break;
510 
511   case Type::UnaryTransform:
512     if (!IsStructurallyEquivalent(
513             Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
514             cast<UnaryTransformType>(T2)->getUnderlyingType()))
515       return false;
516     break;
517 
518   case Type::Decltype:
519     if (!IsStructurallyEquivalent(Context,
520                                   cast<DecltypeType>(T1)->getUnderlyingExpr(),
521                                   cast<DecltypeType>(T2)->getUnderlyingExpr()))
522       return false;
523     break;
524 
525   case Type::Auto:
526     if (!IsStructurallyEquivalent(Context, cast<AutoType>(T1)->getDeducedType(),
527                                   cast<AutoType>(T2)->getDeducedType()))
528       return false;
529     break;
530 
531   case Type::DeducedTemplateSpecialization: {
532     const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
533     const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
534     if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
535                                   DT2->getTemplateName()))
536       return false;
537     if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
538                                   DT2->getDeducedType()))
539       return false;
540     break;
541   }
542 
543   case Type::Record:
544   case Type::Enum:
545     if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
546                                   cast<TagType>(T2)->getDecl()))
547       return false;
548     break;
549 
550   case Type::TemplateTypeParm: {
551     const auto *Parm1 = cast<TemplateTypeParmType>(T1);
552     const auto *Parm2 = cast<TemplateTypeParmType>(T2);
553     if (Parm1->getDepth() != Parm2->getDepth())
554       return false;
555     if (Parm1->getIndex() != Parm2->getIndex())
556       return false;
557     if (Parm1->isParameterPack() != Parm2->isParameterPack())
558       return false;
559 
560     // Names of template type parameters are never significant.
561     break;
562   }
563 
564   case Type::SubstTemplateTypeParm: {
565     const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
566     const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
567     if (!IsStructurallyEquivalent(Context,
568                                   QualType(Subst1->getReplacedParameter(), 0),
569                                   QualType(Subst2->getReplacedParameter(), 0)))
570       return false;
571     if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
572                                   Subst2->getReplacementType()))
573       return false;
574     break;
575   }
576 
577   case Type::SubstTemplateTypeParmPack: {
578     const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
579     const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
580     if (!IsStructurallyEquivalent(Context,
581                                   QualType(Subst1->getReplacedParameter(), 0),
582                                   QualType(Subst2->getReplacedParameter(), 0)))
583       return false;
584     if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
585                                   Subst2->getArgumentPack()))
586       return false;
587     break;
588   }
589 
590   case Type::TemplateSpecialization: {
591     const auto *Spec1 = cast<TemplateSpecializationType>(T1);
592     const auto *Spec2 = cast<TemplateSpecializationType>(T2);
593     if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
594                                   Spec2->getTemplateName()))
595       return false;
596     if (Spec1->getNumArgs() != Spec2->getNumArgs())
597       return false;
598     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
599       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
600                                     Spec2->getArg(I)))
601         return false;
602     }
603     break;
604   }
605 
606   case Type::Elaborated: {
607     const auto *Elab1 = cast<ElaboratedType>(T1);
608     const auto *Elab2 = cast<ElaboratedType>(T2);
609     // CHECKME: what if a keyword is ETK_None or ETK_typename ?
610     if (Elab1->getKeyword() != Elab2->getKeyword())
611       return false;
612     if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
613                                   Elab2->getQualifier()))
614       return false;
615     if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
616                                   Elab2->getNamedType()))
617       return false;
618     break;
619   }
620 
621   case Type::InjectedClassName: {
622     const auto *Inj1 = cast<InjectedClassNameType>(T1);
623     const auto *Inj2 = cast<InjectedClassNameType>(T2);
624     if (!IsStructurallyEquivalent(Context,
625                                   Inj1->getInjectedSpecializationType(),
626                                   Inj2->getInjectedSpecializationType()))
627       return false;
628     break;
629   }
630 
631   case Type::DependentName: {
632     const auto *Typename1 = cast<DependentNameType>(T1);
633     const auto *Typename2 = cast<DependentNameType>(T2);
634     if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
635                                   Typename2->getQualifier()))
636       return false;
637     if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
638                                   Typename2->getIdentifier()))
639       return false;
640 
641     break;
642   }
643 
644   case Type::DependentTemplateSpecialization: {
645     const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
646     const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
647     if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
648                                   Spec2->getQualifier()))
649       return false;
650     if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
651                                   Spec2->getIdentifier()))
652       return false;
653     if (Spec1->getNumArgs() != Spec2->getNumArgs())
654       return false;
655     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
656       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
657                                     Spec2->getArg(I)))
658         return false;
659     }
660     break;
661   }
662 
663   case Type::PackExpansion:
664     if (!IsStructurallyEquivalent(Context,
665                                   cast<PackExpansionType>(T1)->getPattern(),
666                                   cast<PackExpansionType>(T2)->getPattern()))
667       return false;
668     break;
669 
670   case Type::ObjCInterface: {
671     const auto *Iface1 = cast<ObjCInterfaceType>(T1);
672     const auto *Iface2 = cast<ObjCInterfaceType>(T2);
673     if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
674                                   Iface2->getDecl()))
675       return false;
676     break;
677   }
678 
679   case Type::ObjCTypeParam: {
680     const auto *Obj1 = cast<ObjCTypeParamType>(T1);
681     const auto *Obj2 = cast<ObjCTypeParamType>(T2);
682     if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
683       return false;
684 
685     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
686       return false;
687     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
688       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
689                                     Obj2->getProtocol(I)))
690         return false;
691     }
692     break;
693   }
694 
695   case Type::ObjCObject: {
696     const auto *Obj1 = cast<ObjCObjectType>(T1);
697     const auto *Obj2 = cast<ObjCObjectType>(T2);
698     if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
699                                   Obj2->getBaseType()))
700       return false;
701     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
702       return false;
703     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
704       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
705                                     Obj2->getProtocol(I)))
706         return false;
707     }
708     break;
709   }
710 
711   case Type::ObjCObjectPointer: {
712     const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
713     const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
714     if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
715                                   Ptr2->getPointeeType()))
716       return false;
717     break;
718   }
719 
720   case Type::Atomic:
721     if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
722                                   cast<AtomicType>(T2)->getValueType()))
723       return false;
724     break;
725 
726   case Type::Pipe:
727     if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
728                                   cast<PipeType>(T2)->getElementType()))
729       return false;
730     break;
731   } // end switch
732 
733   return true;
734 }
735 
736 /// Determine structural equivalence of two fields.
737 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
738                                      FieldDecl *Field1, FieldDecl *Field2) {
739   const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
740 
741   // For anonymous structs/unions, match up the anonymous struct/union type
742   // declarations directly, so that we don't go off searching for anonymous
743   // types
744   if (Field1->isAnonymousStructOrUnion() &&
745       Field2->isAnonymousStructOrUnion()) {
746     RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
747     RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
748     return IsStructurallyEquivalent(Context, D1, D2);
749   }
750 
751   // Check for equivalent field names.
752   IdentifierInfo *Name1 = Field1->getIdentifier();
753   IdentifierInfo *Name2 = Field2->getIdentifier();
754   if (!::IsStructurallyEquivalent(Name1, Name2)) {
755     if (Context.Complain) {
756       Context.Diag2(Owner2->getLocation(),
757                     Context.ErrorOnTagTypeMismatch
758                         ? diag::err_odr_tag_type_inconsistent
759                         : diag::warn_odr_tag_type_inconsistent)
760           << Context.ToCtx.getTypeDeclType(Owner2);
761       Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
762           << Field2->getDeclName();
763       Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
764           << Field1->getDeclName();
765     }
766     return false;
767   }
768 
769   if (!IsStructurallyEquivalent(Context, Field1->getType(),
770                                 Field2->getType())) {
771     if (Context.Complain) {
772       Context.Diag2(Owner2->getLocation(),
773                     Context.ErrorOnTagTypeMismatch
774                         ? diag::err_odr_tag_type_inconsistent
775                         : diag::warn_odr_tag_type_inconsistent)
776           << Context.ToCtx.getTypeDeclType(Owner2);
777       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
778           << Field2->getDeclName() << Field2->getType();
779       Context.Diag1(Field1->getLocation(), diag::note_odr_field)
780           << Field1->getDeclName() << Field1->getType();
781     }
782     return false;
783   }
784 
785   if (Field1->isBitField() != Field2->isBitField()) {
786     if (Context.Complain) {
787       Context.Diag2(Owner2->getLocation(),
788                     Context.ErrorOnTagTypeMismatch
789                         ? diag::err_odr_tag_type_inconsistent
790                         : diag::warn_odr_tag_type_inconsistent)
791           << Context.ToCtx.getTypeDeclType(Owner2);
792       if (Field1->isBitField()) {
793         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
794             << Field1->getDeclName() << Field1->getType()
795             << Field1->getBitWidthValue(Context.FromCtx);
796         Context.Diag2(Field2->getLocation(), diag::note_odr_not_bit_field)
797             << Field2->getDeclName();
798       } else {
799         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
800             << Field2->getDeclName() << Field2->getType()
801             << Field2->getBitWidthValue(Context.ToCtx);
802         Context.Diag1(Field1->getLocation(), diag::note_odr_not_bit_field)
803             << Field1->getDeclName();
804       }
805     }
806     return false;
807   }
808 
809   if (Field1->isBitField()) {
810     // Make sure that the bit-fields are the same length.
811     unsigned Bits1 = Field1->getBitWidthValue(Context.FromCtx);
812     unsigned Bits2 = Field2->getBitWidthValue(Context.ToCtx);
813 
814     if (Bits1 != Bits2) {
815       if (Context.Complain) {
816         Context.Diag2(Owner2->getLocation(),
817                       Context.ErrorOnTagTypeMismatch
818                           ? diag::err_odr_tag_type_inconsistent
819                           : diag::warn_odr_tag_type_inconsistent)
820             << Context.ToCtx.getTypeDeclType(Owner2);
821         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
822             << Field2->getDeclName() << Field2->getType() << Bits2;
823         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
824             << Field1->getDeclName() << Field1->getType() << Bits1;
825       }
826       return false;
827     }
828   }
829 
830   return true;
831 }
832 
833 /// Determine structural equivalence of two records.
834 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
835                                      RecordDecl *D1, RecordDecl *D2) {
836   if (D1->isUnion() != D2->isUnion()) {
837     if (Context.Complain) {
838       Context.Diag2(D2->getLocation(),
839                     Context.ErrorOnTagTypeMismatch
840                         ? diag::err_odr_tag_type_inconsistent
841                         : diag::warn_odr_tag_type_inconsistent)
842           << Context.ToCtx.getTypeDeclType(D2);
843       Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
844           << D1->getDeclName() << (unsigned)D1->getTagKind();
845     }
846     return false;
847   }
848 
849   if (D1->isAnonymousStructOrUnion() && D2->isAnonymousStructOrUnion()) {
850     // If both anonymous structs/unions are in a record context, make sure
851     // they occur in the same location in the context records.
852     if (Optional<unsigned> Index1 =
853             StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
854       if (Optional<unsigned> Index2 =
855               StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
856                   D2)) {
857         if (*Index1 != *Index2)
858           return false;
859       }
860     }
861   }
862 
863   // If both declarations are class template specializations, we know
864   // the ODR applies, so check the template and template arguments.
865   const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
866   const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
867   if (Spec1 && Spec2) {
868     // Check that the specialized templates are the same.
869     if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
870                                   Spec2->getSpecializedTemplate()))
871       return false;
872 
873     // Check that the template arguments are the same.
874     if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
875       return false;
876 
877     for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
878       if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
879                                     Spec2->getTemplateArgs().get(I)))
880         return false;
881   }
882   // If one is a class template specialization and the other is not, these
883   // structures are different.
884   else if (Spec1 || Spec2)
885     return false;
886 
887   // Compare the definitions of these two records. If either or both are
888   // incomplete, we assume that they are equivalent.
889   D1 = D1->getDefinition();
890   D2 = D2->getDefinition();
891   if (!D1 || !D2)
892     return true;
893 
894   if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
895     if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
896       if (D1CXX->hasExternalLexicalStorage() &&
897           !D1CXX->isCompleteDefinition()) {
898         D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
899       }
900 
901       if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
902         if (Context.Complain) {
903           Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
904               << Context.ToCtx.getTypeDeclType(D2);
905           Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
906               << D2CXX->getNumBases();
907           Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
908               << D1CXX->getNumBases();
909         }
910         return false;
911       }
912 
913       // Check the base classes.
914       for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
915                                               BaseEnd1 = D1CXX->bases_end(),
916                                               Base2 = D2CXX->bases_begin();
917            Base1 != BaseEnd1; ++Base1, ++Base2) {
918         if (!IsStructurallyEquivalent(Context, Base1->getType(),
919                                       Base2->getType())) {
920           if (Context.Complain) {
921             Context.Diag2(D2->getLocation(),
922                           diag::warn_odr_tag_type_inconsistent)
923                 << Context.ToCtx.getTypeDeclType(D2);
924             Context.Diag2(Base2->getLocStart(), diag::note_odr_base)
925                 << Base2->getType() << Base2->getSourceRange();
926             Context.Diag1(Base1->getLocStart(), diag::note_odr_base)
927                 << Base1->getType() << Base1->getSourceRange();
928           }
929           return false;
930         }
931 
932         // Check virtual vs. non-virtual inheritance mismatch.
933         if (Base1->isVirtual() != Base2->isVirtual()) {
934           if (Context.Complain) {
935             Context.Diag2(D2->getLocation(),
936                           diag::warn_odr_tag_type_inconsistent)
937                 << Context.ToCtx.getTypeDeclType(D2);
938             Context.Diag2(Base2->getLocStart(), diag::note_odr_virtual_base)
939                 << Base2->isVirtual() << Base2->getSourceRange();
940             Context.Diag1(Base1->getLocStart(), diag::note_odr_base)
941                 << Base1->isVirtual() << Base1->getSourceRange();
942           }
943           return false;
944         }
945       }
946 
947       // Check the friends for consistency.
948       CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
949               Friend2End = D2CXX->friend_end();
950       for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
951                    Friend1End = D1CXX->friend_end();
952            Friend1 != Friend1End; ++Friend1, ++Friend2) {
953         if (Friend2 == Friend2End) {
954           if (Context.Complain) {
955             Context.Diag2(D2->getLocation(),
956                           diag::warn_odr_tag_type_inconsistent)
957                     << Context.ToCtx.getTypeDeclType(D2CXX);
958             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
959             Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
960           }
961           return false;
962         }
963 
964         if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
965           if (Context.Complain) {
966             Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
967               << Context.ToCtx.getTypeDeclType(D2CXX);
968             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
969             Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
970           }
971           return false;
972         }
973       }
974 
975       if (Friend2 != Friend2End) {
976         if (Context.Complain) {
977           Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
978                   << Context.ToCtx.getTypeDeclType(D2);
979           Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
980           Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
981         }
982         return false;
983       }
984     } else if (D1CXX->getNumBases() > 0) {
985       if (Context.Complain) {
986         Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
987             << Context.ToCtx.getTypeDeclType(D2);
988         const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
989         Context.Diag1(Base1->getLocStart(), diag::note_odr_base)
990             << Base1->getType() << Base1->getSourceRange();
991         Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
992       }
993       return false;
994     }
995   }
996 
997   // Check the fields for consistency.
998   RecordDecl::field_iterator Field2 = D2->field_begin(),
999                              Field2End = D2->field_end();
1000   for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1001                                   Field1End = D1->field_end();
1002        Field1 != Field1End; ++Field1, ++Field2) {
1003     if (Field2 == Field2End) {
1004       if (Context.Complain) {
1005         Context.Diag2(D2->getLocation(),
1006                       Context.ErrorOnTagTypeMismatch
1007                           ? diag::err_odr_tag_type_inconsistent
1008                           : diag::warn_odr_tag_type_inconsistent)
1009             << Context.ToCtx.getTypeDeclType(D2);
1010         Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1011             << Field1->getDeclName() << Field1->getType();
1012         Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1013       }
1014       return false;
1015     }
1016 
1017     if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1018       return false;
1019   }
1020 
1021   if (Field2 != Field2End) {
1022     if (Context.Complain) {
1023       Context.Diag2(D2->getLocation(),
1024                     Context.ErrorOnTagTypeMismatch
1025                         ? diag::err_odr_tag_type_inconsistent
1026                         : diag::warn_odr_tag_type_inconsistent)
1027           << Context.ToCtx.getTypeDeclType(D2);
1028       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1029           << Field2->getDeclName() << Field2->getType();
1030       Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1031     }
1032     return false;
1033   }
1034 
1035   return true;
1036 }
1037 
1038 /// Determine structural equivalence of two enums.
1039 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1040                                      EnumDecl *D1, EnumDecl *D2) {
1041   EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1042                                 EC2End = D2->enumerator_end();
1043   for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1044                                      EC1End = D1->enumerator_end();
1045        EC1 != EC1End; ++EC1, ++EC2) {
1046     if (EC2 == EC2End) {
1047       if (Context.Complain) {
1048         Context.Diag2(D2->getLocation(),
1049                       Context.ErrorOnTagTypeMismatch
1050                           ? diag::err_odr_tag_type_inconsistent
1051                           : diag::warn_odr_tag_type_inconsistent)
1052             << Context.ToCtx.getTypeDeclType(D2);
1053         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1054             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1055         Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1056       }
1057       return false;
1058     }
1059 
1060     llvm::APSInt Val1 = EC1->getInitVal();
1061     llvm::APSInt Val2 = EC2->getInitVal();
1062     if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1063         !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1064       if (Context.Complain) {
1065         Context.Diag2(D2->getLocation(),
1066                       Context.ErrorOnTagTypeMismatch
1067                           ? diag::err_odr_tag_type_inconsistent
1068                           : diag::warn_odr_tag_type_inconsistent)
1069             << Context.ToCtx.getTypeDeclType(D2);
1070         Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1071             << EC2->getDeclName() << EC2->getInitVal().toString(10);
1072         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1073             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1074       }
1075       return false;
1076     }
1077   }
1078 
1079   if (EC2 != EC2End) {
1080     if (Context.Complain) {
1081       Context.Diag2(D2->getLocation(),
1082                     Context.ErrorOnTagTypeMismatch
1083                         ? diag::err_odr_tag_type_inconsistent
1084                         : diag::warn_odr_tag_type_inconsistent)
1085           << Context.ToCtx.getTypeDeclType(D2);
1086       Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1087           << EC2->getDeclName() << EC2->getInitVal().toString(10);
1088       Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1089     }
1090     return false;
1091   }
1092 
1093   return true;
1094 }
1095 
1096 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1097                                      TemplateParameterList *Params1,
1098                                      TemplateParameterList *Params2) {
1099   if (Params1->size() != Params2->size()) {
1100     if (Context.Complain) {
1101       Context.Diag2(Params2->getTemplateLoc(),
1102                     diag::err_odr_different_num_template_parameters)
1103           << Params1->size() << Params2->size();
1104       Context.Diag1(Params1->getTemplateLoc(),
1105                     diag::note_odr_template_parameter_list);
1106     }
1107     return false;
1108   }
1109 
1110   for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1111     if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1112       if (Context.Complain) {
1113         Context.Diag2(Params2->getParam(I)->getLocation(),
1114                       diag::err_odr_different_template_parameter_kind);
1115         Context.Diag1(Params1->getParam(I)->getLocation(),
1116                       diag::note_odr_template_parameter_here);
1117       }
1118       return false;
1119     }
1120 
1121     if (!Context.IsStructurallyEquivalent(Params1->getParam(I),
1122                                           Params2->getParam(I)))
1123       return false;
1124   }
1125 
1126   return true;
1127 }
1128 
1129 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1130                                      TemplateTypeParmDecl *D1,
1131                                      TemplateTypeParmDecl *D2) {
1132   if (D1->isParameterPack() != D2->isParameterPack()) {
1133     if (Context.Complain) {
1134       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1135           << D2->isParameterPack();
1136       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1137           << D1->isParameterPack();
1138     }
1139     return false;
1140   }
1141 
1142   return true;
1143 }
1144 
1145 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1146                                      NonTypeTemplateParmDecl *D1,
1147                                      NonTypeTemplateParmDecl *D2) {
1148   if (D1->isParameterPack() != D2->isParameterPack()) {
1149     if (Context.Complain) {
1150       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1151           << D2->isParameterPack();
1152       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1153           << D1->isParameterPack();
1154     }
1155     return false;
1156   }
1157 
1158   // Check types.
1159   if (!Context.IsStructurallyEquivalent(D1->getType(), D2->getType())) {
1160     if (Context.Complain) {
1161       Context.Diag2(D2->getLocation(),
1162                     diag::err_odr_non_type_parameter_type_inconsistent)
1163           << D2->getType() << D1->getType();
1164       Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1165           << D1->getType();
1166     }
1167     return false;
1168   }
1169 
1170   return true;
1171 }
1172 
1173 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1174                                      TemplateTemplateParmDecl *D1,
1175                                      TemplateTemplateParmDecl *D2) {
1176   if (D1->isParameterPack() != D2->isParameterPack()) {
1177     if (Context.Complain) {
1178       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1179           << D2->isParameterPack();
1180       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1181           << D1->isParameterPack();
1182     }
1183     return false;
1184   }
1185 
1186   // Check template parameter lists.
1187   return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1188                                   D2->getTemplateParameters());
1189 }
1190 
1191 static bool IsTemplateDeclCommonStructurallyEquivalent(
1192     StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1193   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1194     return false;
1195   if (!D1->getIdentifier()) // Special name
1196     if (D1->getNameAsString() != D2->getNameAsString())
1197       return false;
1198   return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1199                                   D2->getTemplateParameters());
1200 }
1201 
1202 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1203                                      ClassTemplateDecl *D1,
1204                                      ClassTemplateDecl *D2) {
1205   // Check template parameters.
1206   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1207     return false;
1208 
1209   // Check the templated declaration.
1210   return Context.IsStructurallyEquivalent(D1->getTemplatedDecl(),
1211                                           D2->getTemplatedDecl());
1212 }
1213 
1214 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1215                                      FunctionTemplateDecl *D1,
1216                                      FunctionTemplateDecl *D2) {
1217   // Check template parameters.
1218   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1219     return false;
1220 
1221   // Check the templated declaration.
1222   return Context.IsStructurallyEquivalent(D1->getTemplatedDecl()->getType(),
1223                                           D2->getTemplatedDecl()->getType());
1224 }
1225 
1226 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1227                                      FriendDecl *D1, FriendDecl *D2) {
1228   if ((D1->getFriendType() && D2->getFriendDecl()) ||
1229       (D1->getFriendDecl() && D2->getFriendType())) {
1230       return false;
1231   }
1232   if (D1->getFriendType() && D2->getFriendType())
1233     return IsStructurallyEquivalent(Context,
1234                                     D1->getFriendType()->getType(),
1235                                     D2->getFriendType()->getType());
1236   if (D1->getFriendDecl() && D2->getFriendDecl())
1237     return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1238                                     D2->getFriendDecl());
1239   return false;
1240 }
1241 
1242 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1243                                      FunctionDecl *D1, FunctionDecl *D2) {
1244   // FIXME: Consider checking for function attributes as well.
1245   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1246     return false;
1247 
1248   return true;
1249 }
1250 
1251 /// Determine structural equivalence of two declarations.
1252 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1253                                      Decl *D1, Decl *D2) {
1254   // FIXME: Check for known structural equivalences via a callback of some sort.
1255 
1256   // Check whether we already know that these two declarations are not
1257   // structurally equivalent.
1258   if (Context.NonEquivalentDecls.count(
1259           std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl())))
1260     return false;
1261 
1262   // Determine whether we've already produced a tentative equivalence for D1.
1263   Decl *&EquivToD1 = Context.TentativeEquivalences[D1->getCanonicalDecl()];
1264   if (EquivToD1)
1265     return EquivToD1 == D2->getCanonicalDecl();
1266 
1267   // Produce a tentative equivalence D1 <-> D2, which will be checked later.
1268   EquivToD1 = D2->getCanonicalDecl();
1269   Context.DeclsToCheck.push_back(D1->getCanonicalDecl());
1270   return true;
1271 }
1272 
1273 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1274                                                       unsigned DiagID) {
1275   assert(Complain && "Not allowed to complain");
1276   if (LastDiagFromC2)
1277     FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1278   LastDiagFromC2 = false;
1279   return FromCtx.getDiagnostics().Report(Loc, DiagID);
1280 }
1281 
1282 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1283                                                       unsigned DiagID) {
1284   assert(Complain && "Not allowed to complain");
1285   if (!LastDiagFromC2)
1286     ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1287   LastDiagFromC2 = true;
1288   return ToCtx.getDiagnostics().Report(Loc, DiagID);
1289 }
1290 
1291 Optional<unsigned>
1292 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1293   ASTContext &Context = Anon->getASTContext();
1294   QualType AnonTy = Context.getRecordType(Anon);
1295 
1296   const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1297   if (!Owner)
1298     return None;
1299 
1300   unsigned Index = 0;
1301   for (const auto *D : Owner->noload_decls()) {
1302     const auto *F = dyn_cast<FieldDecl>(D);
1303     if (!F)
1304       continue;
1305 
1306     if (F->isAnonymousStructOrUnion()) {
1307       if (Context.hasSameType(F->getType(), AnonTy))
1308         break;
1309       ++Index;
1310       continue;
1311     }
1312 
1313     // If the field looks like this:
1314     // struct { ... } A;
1315     QualType FieldType = F->getType();
1316     // In case of nested structs.
1317     while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1318       FieldType = ElabType->getNamedType();
1319 
1320     if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1321       const RecordDecl *RecDecl = RecType->getDecl();
1322       if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1323         if (Context.hasSameType(FieldType, AnonTy))
1324           break;
1325         ++Index;
1326         continue;
1327       }
1328     }
1329   }
1330 
1331   return Index;
1332 }
1333 
1334 bool StructuralEquivalenceContext::IsStructurallyEquivalent(Decl *D1,
1335                                                             Decl *D2) {
1336   if (!::IsStructurallyEquivalent(*this, D1, D2))
1337     return false;
1338 
1339   return !Finish();
1340 }
1341 
1342 bool StructuralEquivalenceContext::IsStructurallyEquivalent(QualType T1,
1343                                                             QualType T2) {
1344   if (!::IsStructurallyEquivalent(*this, T1, T2))
1345     return false;
1346 
1347   return !Finish();
1348 }
1349 
1350 bool StructuralEquivalenceContext::Finish() {
1351   while (!DeclsToCheck.empty()) {
1352     // Check the next declaration.
1353     Decl *D1 = DeclsToCheck.front();
1354     DeclsToCheck.pop_front();
1355 
1356     Decl *D2 = TentativeEquivalences[D1];
1357     assert(D2 && "Unrecorded tentative equivalence?");
1358 
1359     bool Equivalent = true;
1360 
1361     // FIXME: Switch on all declaration kinds. For now, we're just going to
1362     // check the obvious ones.
1363     if (auto *Record1 = dyn_cast<RecordDecl>(D1)) {
1364       if (auto *Record2 = dyn_cast<RecordDecl>(D2)) {
1365         // Check for equivalent structure names.
1366         IdentifierInfo *Name1 = Record1->getIdentifier();
1367         if (!Name1 && Record1->getTypedefNameForAnonDecl())
1368           Name1 = Record1->getTypedefNameForAnonDecl()->getIdentifier();
1369         IdentifierInfo *Name2 = Record2->getIdentifier();
1370         if (!Name2 && Record2->getTypedefNameForAnonDecl())
1371           Name2 = Record2->getTypedefNameForAnonDecl()->getIdentifier();
1372         if (!::IsStructurallyEquivalent(Name1, Name2) ||
1373             !::IsStructurallyEquivalent(*this, Record1, Record2))
1374           Equivalent = false;
1375       } else {
1376         // Record/non-record mismatch.
1377         Equivalent = false;
1378       }
1379     } else if (auto *Enum1 = dyn_cast<EnumDecl>(D1)) {
1380       if (auto *Enum2 = dyn_cast<EnumDecl>(D2)) {
1381         // Check for equivalent enum names.
1382         IdentifierInfo *Name1 = Enum1->getIdentifier();
1383         if (!Name1 && Enum1->getTypedefNameForAnonDecl())
1384           Name1 = Enum1->getTypedefNameForAnonDecl()->getIdentifier();
1385         IdentifierInfo *Name2 = Enum2->getIdentifier();
1386         if (!Name2 && Enum2->getTypedefNameForAnonDecl())
1387           Name2 = Enum2->getTypedefNameForAnonDecl()->getIdentifier();
1388         if (!::IsStructurallyEquivalent(Name1, Name2) ||
1389             !::IsStructurallyEquivalent(*this, Enum1, Enum2))
1390           Equivalent = false;
1391       } else {
1392         // Enum/non-enum mismatch
1393         Equivalent = false;
1394       }
1395     } else if (const auto *Typedef1 = dyn_cast<TypedefNameDecl>(D1)) {
1396       if (const auto *Typedef2 = dyn_cast<TypedefNameDecl>(D2)) {
1397         if (!::IsStructurallyEquivalent(Typedef1->getIdentifier(),
1398                                         Typedef2->getIdentifier()) ||
1399             !::IsStructurallyEquivalent(*this, Typedef1->getUnderlyingType(),
1400                                         Typedef2->getUnderlyingType()))
1401           Equivalent = false;
1402       } else {
1403         // Typedef/non-typedef mismatch.
1404         Equivalent = false;
1405       }
1406     } else if (auto *ClassTemplate1 = dyn_cast<ClassTemplateDecl>(D1)) {
1407       if (auto *ClassTemplate2 = dyn_cast<ClassTemplateDecl>(D2)) {
1408         if (!::IsStructurallyEquivalent(*this, ClassTemplate1,
1409                                         ClassTemplate2))
1410           Equivalent = false;
1411       } else {
1412         // Class template/non-class-template mismatch.
1413         Equivalent = false;
1414       }
1415     } else if (auto *FunctionTemplate1 = dyn_cast<FunctionTemplateDecl>(D1)) {
1416       if (auto *FunctionTemplate2 = dyn_cast<FunctionTemplateDecl>(D2)) {
1417         if (!::IsStructurallyEquivalent(*this, FunctionTemplate1,
1418                                         FunctionTemplate2))
1419           Equivalent = false;
1420       } else {
1421         // Class template/non-class-template mismatch.
1422         Equivalent = false;
1423       }
1424     } else if (auto *TTP1 = dyn_cast<TemplateTypeParmDecl>(D1)) {
1425       if (auto *TTP2 = dyn_cast<TemplateTypeParmDecl>(D2)) {
1426         if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1427           Equivalent = false;
1428       } else {
1429         // Kind mismatch.
1430         Equivalent = false;
1431       }
1432     } else if (auto *NTTP1 = dyn_cast<NonTypeTemplateParmDecl>(D1)) {
1433       if (auto *NTTP2 = dyn_cast<NonTypeTemplateParmDecl>(D2)) {
1434         if (!::IsStructurallyEquivalent(*this, NTTP1, NTTP2))
1435           Equivalent = false;
1436       } else {
1437         // Kind mismatch.
1438         Equivalent = false;
1439       }
1440     } else if (auto *TTP1 = dyn_cast<TemplateTemplateParmDecl>(D1)) {
1441       if (auto *TTP2 = dyn_cast<TemplateTemplateParmDecl>(D2)) {
1442         if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1443           Equivalent = false;
1444       } else {
1445         // Kind mismatch.
1446         Equivalent = false;
1447       }
1448     } else if (FunctionDecl *FD1 = dyn_cast<FunctionDecl>(D1)) {
1449       if (FunctionDecl *FD2 = dyn_cast<FunctionDecl>(D2)) {
1450         if (!::IsStructurallyEquivalent(FD1->getIdentifier(),
1451                                         FD2->getIdentifier()))
1452           Equivalent = false;
1453         if (!::IsStructurallyEquivalent(*this, FD1, FD2))
1454           Equivalent = false;
1455       } else {
1456         // Kind mismatch.
1457         Equivalent = false;
1458       }
1459     } else if (FriendDecl *FrD1 = dyn_cast<FriendDecl>(D1)) {
1460       if (FriendDecl *FrD2 = dyn_cast<FriendDecl>(D2)) {
1461           if (!::IsStructurallyEquivalent(*this, FrD1, FrD2))
1462             Equivalent = false;
1463       } else {
1464         // Kind mismatch.
1465         Equivalent = false;
1466       }
1467     }
1468 
1469     if (!Equivalent) {
1470       // Note that these two declarations are not equivalent (and we already
1471       // know about it).
1472       NonEquivalentDecls.insert(
1473           std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl()));
1474       return true;
1475     }
1476     // FIXME: Check other declaration kinds!
1477   }
1478 
1479   return false;
1480 }
1481