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