contrib/llvm/tools/clang/lib/AST/ASTStructuralEquivalence.cpp

   1 //===--- ASTStructuralEquivalence.cpp - -------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file implement StructuralEquivalenceContext class and helper functions
  11 //  for layout matching.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/AST/ASTStructuralEquivalence.h"
  16 #include "clang/AST/ASTContext.h"
  17 #include "clang/AST/ASTDiagnostic.h"
  18 #include "clang/AST/ASTImporter.h"
  19 #include "clang/AST/DeclCXX.h"
  20 #include "clang/AST/DeclObjC.h"
  21 #include "clang/AST/DeclVisitor.h"
  22 #include "clang/AST/StmtVisitor.h"
  23 #include "clang/AST/TypeVisitor.h"
  24 #include "clang/Basic/SourceManager.h"
  25
  26 namespace {
  27
  28 using namespace clang;
  29
  30 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
  31                                      QualType T1, QualType T2);
  32 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
  33                                      Decl *D1, Decl *D2);
  34 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
  35                                      const TemplateArgument &Arg1,
  36                                      const TemplateArgument &Arg2);
  37
  38 /// Determine structural equivalence of two expressions.
  39 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
  40                                      Expr *E1, Expr *E2) {
  41   if (!E1 || !E2)
  42     return E1 == E2;
  43
  44   // FIXME: Actually perform a structural comparison!
  45   return true;
  46 }
  47
  48 /// Determine whether two identifiers are equivalent.
  49 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
  50                                      const IdentifierInfo *Name2) {
  51   if (!Name1 || !Name2)
  52     return Name1 == Name2;
  53
  54   return Name1->getName() == Name2->getName();
  55 }
  56
  57 /// Determine whether two nested-name-specifiers are equivalent.
  58 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
  59                                      NestedNameSpecifier *NNS1,
  60                                      NestedNameSpecifier *NNS2) {
  61   if (NNS1->getKind() != NNS2->getKind())
  62     return false;
  63
  64   NestedNameSpecifier *Prefix1 = NNS1->getPrefix(),
  65                       *Prefix2 = NNS2->getPrefix();
  66   if ((bool)Prefix1 != (bool)Prefix2)
  67     return false;
  68
  69   if (Prefix1)
  70     if (!IsStructurallyEquivalent(Context, Prefix1, Prefix2))
  71       return false;
  72
  73   switch (NNS1->getKind()) {
  74   case NestedNameSpecifier::Identifier:
  75     return IsStructurallyEquivalent(NNS1->getAsIdentifier(),
  76                                     NNS2->getAsIdentifier());
  77   case NestedNameSpecifier::Namespace:
  78     return IsStructurallyEquivalent(Context, NNS1->getAsNamespace(),
  79                                     NNS2->getAsNamespace());
  80   case NestedNameSpecifier::NamespaceAlias:
  81     return IsStructurallyEquivalent(Context, NNS1->getAsNamespaceAlias(),
  82                                     NNS2->getAsNamespaceAlias());
  83   case NestedNameSpecifier::TypeSpec:
  84   case NestedNameSpecifier::TypeSpecWithTemplate:
  85     return IsStructurallyEquivalent(Context, QualType(NNS1->getAsType(), 0),
  86                                     QualType(NNS2->getAsType(), 0));
  87   case NestedNameSpecifier::Global:
  88     return true;
  89   case NestedNameSpecifier::Super:
  90     return IsStructurallyEquivalent(Context, NNS1->getAsRecordDecl(),
  91                                     NNS2->getAsRecordDecl());
  92   }
  93   return false;
  94 }
  95
  96 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
  97                                      const TemplateName &N1,
  98                                      const TemplateName &N2) {
  99   if (N1.getKind() != N2.getKind())
 100     return false;
 101   switch (N1.getKind()) {
 102   case TemplateName::Template:
 103     return IsStructurallyEquivalent(Context, N1.getAsTemplateDecl(),
 104                                     N2.getAsTemplateDecl());
 105
 106   case TemplateName::OverloadedTemplate: {
 107     OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),
 108                               *OS2 = N2.getAsOverloadedTemplate();
 109     OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),
 110                                         E1 = OS1->end(), E2 = OS2->end();
 111     for (; I1 != E1 && I2 != E2; ++I1, ++I2)
 112       if (!IsStructurallyEquivalent(Context, *I1, *I2))
 113         return false;
 114     return I1 == E1 && I2 == E2;
 115   }
 116
 117   case TemplateName::QualifiedTemplate: {
 118     QualifiedTemplateName *QN1 = N1.getAsQualifiedTemplateName(),
 119                           *QN2 = N2.getAsQualifiedTemplateName();
 120     return IsStructurallyEquivalent(Context, QN1->getDecl(), QN2->getDecl()) &&
 121            IsStructurallyEquivalent(Context, QN1->getQualifier(),
 122                                     QN2->getQualifier());
 123   }
 124
 125   case TemplateName::DependentTemplate: {
 126     DependentTemplateName *DN1 = N1.getAsDependentTemplateName(),
 127                           *DN2 = N2.getAsDependentTemplateName();
 128     if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
 129                                   DN2->getQualifier()))
 130       return false;
 131     if (DN1->isIdentifier() && DN2->isIdentifier())
 132       return IsStructurallyEquivalent(DN1->getIdentifier(),
 133                                       DN2->getIdentifier());
 134     else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
 135       return DN1->getOperator() == DN2->getOperator();
 136     return false;
 137   }
 138
 139   case TemplateName::SubstTemplateTemplateParm: {
 140     SubstTemplateTemplateParmStorage *TS1 = N1.getAsSubstTemplateTemplateParm(),
 141                                      *TS2 = N2.getAsSubstTemplateTemplateParm();
 142     return IsStructurallyEquivalent(Context, TS1->getParameter(),
 143                                     TS2->getParameter()) &&
 144            IsStructurallyEquivalent(Context, TS1->getReplacement(),
 145                                     TS2->getReplacement());
 146   }
 147   case TemplateName::SubstTemplateTemplateParmPack: {
 148     SubstTemplateTemplateParmPackStorage
 149         *P1 = N1.getAsSubstTemplateTemplateParmPack(),
 150         *P2 = N2.getAsSubstTemplateTemplateParmPack();
 151     return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
 152                                     P2->getArgumentPack()) &&
 153            IsStructurallyEquivalent(Context, P1->getParameterPack(),
 154                                     P2->getParameterPack());
 155   }
 156   }
 157   return false;
 158 }
 159
 160 /// Determine whether two template arguments are equivalent.
 161 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
 162                                      const TemplateArgument &Arg1,
 163                                      const TemplateArgument &Arg2) {
 164   if (Arg1.getKind() != Arg2.getKind())
 165     return false;
 166
 167   switch (Arg1.getKind()) {
 168   case TemplateArgument::Null:
 169     return true;
 170
 171   case TemplateArgument::Type:
 172     return Context.IsStructurallyEquivalent(Arg1.getAsType(), Arg2.getAsType());
 173
 174   case TemplateArgument::Integral:
 175     if (!Context.IsStructurallyEquivalent(Arg1.getIntegralType(),
 176                                           Arg2.getIntegralType()))
 177       return false;
 178
 179     return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
 180                                      Arg2.getAsIntegral());
 181
 182   case TemplateArgument::Declaration:
 183     return Context.IsStructurallyEquivalent(Arg1.getAsDecl(), Arg2.getAsDecl());
 184
 185   case TemplateArgument::NullPtr:
 186     return true; // FIXME: Is this correct?
 187
 188   case TemplateArgument::Template:
 189     return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
 190                                     Arg2.getAsTemplate());
 191
 192   case TemplateArgument::TemplateExpansion:
 193     return IsStructurallyEquivalent(Context,
 194                                     Arg1.getAsTemplateOrTemplatePattern(),
 195                                     Arg2.getAsTemplateOrTemplatePattern());
 196
 197   case TemplateArgument::Expression:
 198     return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
 199                                     Arg2.getAsExpr());
 200
 201   case TemplateArgument::Pack:
 202     if (Arg1.pack_size() != Arg2.pack_size())
 203       return false;
 204
 205     for (unsigned I = 0, N = Arg1.pack_size(); I != N; ++I)
 206       if (!IsStructurallyEquivalent(Context, Arg1.pack_begin()[I],
 207                                     Arg2.pack_begin()[I]))
 208         return false;
 209
 210     return true;
 211   }
 212
 213   llvm_unreachable("Invalid template argument kind");
 214 }
 215
 216 /// Determine structural equivalence for the common part of array
 217 /// types.
 218 static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
 219                                           const ArrayType *Array1,
 220                                           const ArrayType *Array2) {
 221   if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
 222                                 Array2->getElementType()))
 223     return false;
 224   if (Array1->getSizeModifier() != Array2->getSizeModifier())
 225     return false;
 226   if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
 227     return false;
 228
 229   return true;
 230 }
 231
 232 /// Determine structural equivalence of two types.
 233 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
 234                                      QualType T1, QualType T2) {
 235   if (T1.isNull() || T2.isNull())
 236     return T1.isNull() && T2.isNull();
 237
 238   if (!Context.StrictTypeSpelling) {
 239     // We aren't being strict about token-to-token equivalence of types,
 240     // so map down to the canonical type.
 241     T1 = Context.FromCtx.getCanonicalType(T1);
 242     T2 = Context.ToCtx.getCanonicalType(T2);
 243   }
 244
 245   if (T1.getQualifiers() != T2.getQualifiers())
 246     return false;
 247
 248   Type::TypeClass TC = T1->getTypeClass();
 249
 250   if (T1->getTypeClass() != T2->getTypeClass()) {
 251     // Compare function types with prototypes vs. without prototypes as if
 252     // both did not have prototypes.
 253     if (T1->getTypeClass() == Type::FunctionProto &&
 254         T2->getTypeClass() == Type::FunctionNoProto)
 255       TC = Type::FunctionNoProto;
 256     else if (T1->getTypeClass() == Type::FunctionNoProto &&
 257              T2->getTypeClass() == Type::FunctionProto)
 258       TC = Type::FunctionNoProto;
 259     else
 260       return false;
 261   }
 262
 263   switch (TC) {
 264   case Type::Builtin:
 265     // FIXME: Deal with Char_S/Char_U.
 266     if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
 267       return false;
 268     break;
 269
 270   case Type::Complex:
 271     if (!IsStructurallyEquivalent(Context,
 272                                   cast<ComplexType>(T1)->getElementType(),
 273                                   cast<ComplexType>(T2)->getElementType()))
 274       return false;
 275     break;
 276
 277   case Type::Adjusted:
 278   case Type::Decayed:
 279     if (!IsStructurallyEquivalent(Context,
 280                                   cast<AdjustedType>(T1)->getOriginalType(),
 281                                   cast<AdjustedType>(T2)->getOriginalType()))
 282       return false;
 283     break;
 284
 285   case Type::Pointer:
 286     if (!IsStructurallyEquivalent(Context,
 287                                   cast<PointerType>(T1)->getPointeeType(),
 288                                   cast<PointerType>(T2)->getPointeeType()))
 289       return false;
 290     break;
 291
 292   case Type::BlockPointer:
 293     if (!IsStructurallyEquivalent(Context,
 294                                   cast<BlockPointerType>(T1)->getPointeeType(),
 295                                   cast<BlockPointerType>(T2)->getPointeeType()))
 296       return false;
 297     break;
 298
 299   case Type::LValueReference:
 300   case Type::RValueReference: {
 301     const ReferenceType *Ref1 = cast<ReferenceType>(T1);
 302     const ReferenceType *Ref2 = cast<ReferenceType>(T2);
 303     if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
 304       return false;
 305     if (Ref1->isInnerRef() != Ref2->isInnerRef())
 306       return false;
 307     if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
 308                                   Ref2->getPointeeTypeAsWritten()))
 309       return false;
 310     break;
 311   }
 312
 313   case Type::MemberPointer: {
 314     const MemberPointerType *MemPtr1 = cast<MemberPointerType>(T1);
 315     const MemberPointerType *MemPtr2 = cast<MemberPointerType>(T2);
 316     if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
 317                                   MemPtr2->getPointeeType()))
 318       return false;
 319     if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
 320                                   QualType(MemPtr2->getClass(), 0)))
 321       return false;
 322     break;
 323   }
 324
 325   case Type::ConstantArray: {
 326     const ConstantArrayType *Array1 = cast<ConstantArrayType>(T1);
 327     const ConstantArrayType *Array2 = cast<ConstantArrayType>(T2);
 328     if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
 329       return false;
 330
 331     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
 332       return false;
 333     break;
 334   }
 335
 336   case Type::IncompleteArray:
 337     if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
 338                                        cast<ArrayType>(T2)))
 339       return false;
 340     break;
 341
 342   case Type::VariableArray: {
 343     const VariableArrayType *Array1 = cast<VariableArrayType>(T1);
 344     const VariableArrayType *Array2 = cast<VariableArrayType>(T2);
 345     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
 346                                   Array2->getSizeExpr()))
 347       return false;
 348
 349     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
 350       return false;
 351
 352     break;
 353   }
 354
 355   case Type::DependentSizedArray: {
 356     const DependentSizedArrayType *Array1 = cast<DependentSizedArrayType>(T1);
 357     const DependentSizedArrayType *Array2 = cast<DependentSizedArrayType>(T2);
 358     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
 359                                   Array2->getSizeExpr()))
 360       return false;
 361
 362     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
 363       return false;
 364
 365     break;
 366   }
 367
 368   case Type::DependentSizedExtVector: {
 369     const DependentSizedExtVectorType *Vec1 =
 370         cast<DependentSizedExtVectorType>(T1);
 371     const DependentSizedExtVectorType *Vec2 =
 372         cast<DependentSizedExtVectorType>(T2);
 373     if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
 374                                   Vec2->getSizeExpr()))
 375       return false;
 376     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
 377                                   Vec2->getElementType()))
 378       return false;
 379     break;
 380   }
 381
 382   case Type::Vector:
 383   case Type::ExtVector: {
 384     const VectorType *Vec1 = cast<VectorType>(T1);
 385     const VectorType *Vec2 = cast<VectorType>(T2);
 386     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
 387                                   Vec2->getElementType()))
 388       return false;
 389     if (Vec1->getNumElements() != Vec2->getNumElements())
 390       return false;
 391     if (Vec1->getVectorKind() != Vec2->getVectorKind())
 392       return false;
 393     break;
 394   }
 395
 396   case Type::FunctionProto: {
 397     const FunctionProtoType *Proto1 = cast<FunctionProtoType>(T1);
 398     const FunctionProtoType *Proto2 = cast<FunctionProtoType>(T2);
 399     if (Proto1->getNumParams() != Proto2->getNumParams())
 400       return false;
 401     for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
 402       if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
 403                                     Proto2->getParamType(I)))
 404         return false;
 405     }
 406     if (Proto1->isVariadic() != Proto2->isVariadic())
 407       return false;
 408     if (Proto1->getExceptionSpecType() != Proto2->getExceptionSpecType())
 409       return false;
 410     if (Proto1->getExceptionSpecType() == EST_Dynamic) {
 411       if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
 412         return false;
 413       for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
 414         if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
 415                                       Proto2->getExceptionType(I)))
 416           return false;
 417       }
 418     } else if (Proto1->getExceptionSpecType() == EST_ComputedNoexcept) {
 419       if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
 420                                     Proto2->getNoexceptExpr()))
 421         return false;
 422     }
 423     if (Proto1->getTypeQuals() != Proto2->getTypeQuals())
 424       return false;
 425
 426     // Fall through to check the bits common with FunctionNoProtoType.
 427     LLVM_FALLTHROUGH;
 428   }
 429
 430   case Type::FunctionNoProto: {
 431     const FunctionType *Function1 = cast<FunctionType>(T1);
 432     const FunctionType *Function2 = cast<FunctionType>(T2);
 433     if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
 434                                   Function2->getReturnType()))
 435       return false;
 436     if (Function1->getExtInfo() != Function2->getExtInfo())
 437       return false;
 438     break;
 439   }
 440
 441   case Type::UnresolvedUsing:
 442     if (!IsStructurallyEquivalent(Context,
 443                                   cast<UnresolvedUsingType>(T1)->getDecl(),
 444                                   cast<UnresolvedUsingType>(T2)->getDecl()))
 445       return false;
 446
 447     break;
 448
 449   case Type::Attributed:
 450     if (!IsStructurallyEquivalent(Context,
 451                                   cast<AttributedType>(T1)->getModifiedType(),
 452                                   cast<AttributedType>(T2)->getModifiedType()))
 453       return false;
 454     if (!IsStructurallyEquivalent(
 455             Context, cast<AttributedType>(T1)->getEquivalentType(),
 456             cast<AttributedType>(T2)->getEquivalentType()))
 457       return false;
 458     break;
 459
 460   case Type::Paren:
 461     if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
 462                                   cast<ParenType>(T2)->getInnerType()))
 463       return false;
 464     break;
 465
 466   case Type::Typedef:
 467     if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
 468                                   cast<TypedefType>(T2)->getDecl()))
 469       return false;
 470     break;
 471
 472   case Type::TypeOfExpr:
 473     if (!IsStructurallyEquivalent(
 474             Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
 475             cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
 476       return false;
 477     break;
 478
 479   case Type::TypeOf:
 480     if (!IsStructurallyEquivalent(Context,
 481                                   cast<TypeOfType>(T1)->getUnderlyingType(),
 482                                   cast<TypeOfType>(T2)->getUnderlyingType()))
 483       return false;
 484     break;
 485
 486   case Type::UnaryTransform:
 487     if (!IsStructurallyEquivalent(
 488             Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
 489             cast<UnaryTransformType>(T1)->getUnderlyingType()))
 490       return false;
 491     break;
 492
 493   case Type::Decltype:
 494     if (!IsStructurallyEquivalent(Context,
 495                                   cast<DecltypeType>(T1)->getUnderlyingExpr(),
 496                                   cast<DecltypeType>(T2)->getUnderlyingExpr()))
 497       return false;
 498     break;
 499
 500   case Type::Auto:
 501     if (!IsStructurallyEquivalent(Context, cast<AutoType>(T1)->getDeducedType(),
 502                                   cast<AutoType>(T2)->getDeducedType()))
 503       return false;
 504     break;
 505
 506   case Type::DeducedTemplateSpecialization: {
 507     auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
 508     auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
 509     if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
 510                                   DT2->getTemplateName()))
 511       return false;
 512     if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
 513                                   DT2->getDeducedType()))
 514       return false;
 515     break;
 516   }
 517
 518   case Type::Record:
 519   case Type::Enum:
 520     if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
 521                                   cast<TagType>(T2)->getDecl()))
 522       return false;
 523     break;
 524
 525   case Type::TemplateTypeParm: {
 526     const TemplateTypeParmType *Parm1 = cast<TemplateTypeParmType>(T1);
 527     const TemplateTypeParmType *Parm2 = cast<TemplateTypeParmType>(T2);
 528     if (Parm1->getDepth() != Parm2->getDepth())
 529       return false;
 530     if (Parm1->getIndex() != Parm2->getIndex())
 531       return false;
 532     if (Parm1->isParameterPack() != Parm2->isParameterPack())
 533       return false;
 534
 535     // Names of template type parameters are never significant.
 536     break;
 537   }
 538
 539   case Type::SubstTemplateTypeParm: {
 540     const SubstTemplateTypeParmType *Subst1 =
 541         cast<SubstTemplateTypeParmType>(T1);
 542     const SubstTemplateTypeParmType *Subst2 =
 543         cast<SubstTemplateTypeParmType>(T2);
 544     if (!IsStructurallyEquivalent(Context,
 545                                   QualType(Subst1->getReplacedParameter(), 0),
 546                                   QualType(Subst2->getReplacedParameter(), 0)))
 547       return false;
 548     if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
 549                                   Subst2->getReplacementType()))
 550       return false;
 551     break;
 552   }
 553
 554   case Type::SubstTemplateTypeParmPack: {
 555     const SubstTemplateTypeParmPackType *Subst1 =
 556         cast<SubstTemplateTypeParmPackType>(T1);
 557     const SubstTemplateTypeParmPackType *Subst2 =
 558         cast<SubstTemplateTypeParmPackType>(T2);
 559     if (!IsStructurallyEquivalent(Context,
 560                                   QualType(Subst1->getReplacedParameter(), 0),
 561                                   QualType(Subst2->getReplacedParameter(), 0)))
 562       return false;
 563     if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
 564                                   Subst2->getArgumentPack()))
 565       return false;
 566     break;
 567   }
 568   case Type::TemplateSpecialization: {
 569     const TemplateSpecializationType *Spec1 =
 570         cast<TemplateSpecializationType>(T1);
 571     const TemplateSpecializationType *Spec2 =
 572         cast<TemplateSpecializationType>(T2);
 573     if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
 574                                   Spec2->getTemplateName()))
 575       return false;
 576     if (Spec1->getNumArgs() != Spec2->getNumArgs())
 577       return false;
 578     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
 579       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
 580                                     Spec2->getArg(I)))
 581         return false;
 582     }
 583     break;
 584   }
 585
 586   case Type::Elaborated: {
 587     const ElaboratedType *Elab1 = cast<ElaboratedType>(T1);
 588     const ElaboratedType *Elab2 = cast<ElaboratedType>(T2);
 589     // CHECKME: what if a keyword is ETK_None or ETK_typename ?
 590     if (Elab1->getKeyword() != Elab2->getKeyword())
 591       return false;
 592     if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
 593                                   Elab2->getQualifier()))
 594       return false;
 595     if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
 596                                   Elab2->getNamedType()))
 597       return false;
 598     break;
 599   }
 600
 601   case Type::InjectedClassName: {
 602     const InjectedClassNameType *Inj1 = cast<InjectedClassNameType>(T1);
 603     const InjectedClassNameType *Inj2 = cast<InjectedClassNameType>(T2);
 604     if (!IsStructurallyEquivalent(Context,
 605                                   Inj1->getInjectedSpecializationType(),
 606                                   Inj2->getInjectedSpecializationType()))
 607       return false;
 608     break;
 609   }
 610
 611   case Type::DependentName: {
 612     const DependentNameType *Typename1 = cast<DependentNameType>(T1);
 613     const DependentNameType *Typename2 = cast<DependentNameType>(T2);
 614     if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
 615                                   Typename2->getQualifier()))
 616       return false;
 617     if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
 618                                   Typename2->getIdentifier()))
 619       return false;
 620
 621     break;
 622   }
 623
 624   case Type::DependentTemplateSpecialization: {
 625     const DependentTemplateSpecializationType *Spec1 =
 626         cast<DependentTemplateSpecializationType>(T1);
 627     const DependentTemplateSpecializationType *Spec2 =
 628         cast<DependentTemplateSpecializationType>(T2);
 629     if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
 630                                   Spec2->getQualifier()))
 631       return false;
 632     if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
 633                                   Spec2->getIdentifier()))
 634       return false;
 635     if (Spec1->getNumArgs() != Spec2->getNumArgs())
 636       return false;
 637     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
 638       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
 639                                     Spec2->getArg(I)))
 640         return false;
 641     }
 642     break;
 643   }
 644
 645   case Type::PackExpansion:
 646     if (!IsStructurallyEquivalent(Context,
 647                                   cast<PackExpansionType>(T1)->getPattern(),
 648                                   cast<PackExpansionType>(T2)->getPattern()))
 649       return false;
 650     break;
 651
 652   case Type::ObjCInterface: {
 653     const ObjCInterfaceType *Iface1 = cast<ObjCInterfaceType>(T1);
 654     const ObjCInterfaceType *Iface2 = cast<ObjCInterfaceType>(T2);
 655     if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
 656                                   Iface2->getDecl()))
 657       return false;
 658     break;
 659   }
 660
 661   case Type::ObjCTypeParam: {
 662     const ObjCTypeParamType *Obj1 = cast<ObjCTypeParamType>(T1);
 663     const ObjCTypeParamType *Obj2 = cast<ObjCTypeParamType>(T2);
 664     if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
 665       return false;
 666
 667     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
 668       return false;
 669     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
 670       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
 671                                     Obj2->getProtocol(I)))
 672         return false;
 673     }
 674     break;
 675   }
 676   case Type::ObjCObject: {
 677     const ObjCObjectType *Obj1 = cast<ObjCObjectType>(T1);
 678     const ObjCObjectType *Obj2 = cast<ObjCObjectType>(T2);
 679     if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
 680                                   Obj2->getBaseType()))
 681       return false;
 682     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
 683       return false;
 684     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
 685       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
 686                                     Obj2->getProtocol(I)))
 687         return false;
 688     }
 689     break;
 690   }
 691
 692   case Type::ObjCObjectPointer: {
 693     const ObjCObjectPointerType *Ptr1 = cast<ObjCObjectPointerType>(T1);
 694     const ObjCObjectPointerType *Ptr2 = cast<ObjCObjectPointerType>(T2);
 695     if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
 696                                   Ptr2->getPointeeType()))
 697       return false;
 698     break;
 699   }
 700
 701   case Type::Atomic: {
 702     if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
 703                                   cast<AtomicType>(T2)->getValueType()))
 704       return false;
 705     break;
 706   }
 707
 708   case Type::Pipe: {
 709     if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
 710                                   cast<PipeType>(T2)->getElementType()))
 711       return false;
 712     break;
 713   }
 714
 715   } // end switch
 716
 717   return true;
 718 }
 719
 720 /// Determine structural equivalence of two fields.
 721 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
 722                                      FieldDecl *Field1, FieldDecl *Field2) {
 723   RecordDecl *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
 724
 725   // For anonymous structs/unions, match up the anonymous struct/union type
 726   // declarations directly, so that we don't go off searching for anonymous
 727   // types
 728   if (Field1->isAnonymousStructOrUnion() &&
 729       Field2->isAnonymousStructOrUnion()) {
 730     RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
 731     RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
 732     return IsStructurallyEquivalent(Context, D1, D2);
 733   }
 734
 735   // Check for equivalent field names.
 736   IdentifierInfo *Name1 = Field1->getIdentifier();
 737   IdentifierInfo *Name2 = Field2->getIdentifier();
 738   if (!::IsStructurallyEquivalent(Name1, Name2)) {
 739     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.
 818 static 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.
 987 static 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
1044 static 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
1079 static 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
1095 static 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
1123 static 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
1141 static 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.
1155 static 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
1177 namespace clang {
1178
1179 DiagnosticBuilder 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
1188 DiagnosticBuilder 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
1197 Optional<unsigned>
1198 StructuralEquivalenceContext::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
1236 bool StructuralEquivalenceContext::IsStructurallyEquivalent(Decl *D1,
1237                                                             Decl *D2) {
1238   if (!::IsStructurallyEquivalent(*this, D1, D2))
1239     return false;
1240
1241   return !Finish();
1242 }
1243
1244 bool StructuralEquivalenceContext::IsStructurallyEquivalent(QualType T1,
1245                                                             QualType T2) {
1246   if (!::IsStructurallyEquivalent(*this, T1, T2))
1247     return false;
1248
1249   return !Finish();
1250 }
1251
1252 bool 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