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

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