brintos / llvm-project-archived public Read only

1//===- ASTStructuralEquivalence.cpp ---------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9//  This file implement StructuralEquivalenceContext class and helper functions10//  for layout matching.11//12// The structural equivalence check could have been implemented as a parallel13// BFS on a pair of graphs.  That must have been the original approach at the14// beginning.15// Let's consider this simple BFS algorithm from the `s` source:16// ```17// void bfs(Graph G, int s)18// {19//   Queue<Integer> queue = new Queue<Integer>();20//   marked[s] = true; // Mark the source21//   queue.enqueue(s); // and put it on the queue.22//   while (!q.isEmpty()) {23//     int v = queue.dequeue(); // Remove next vertex from the queue.24//     for (int w : G.adj(v))25//       if (!marked[w]) // For every unmarked adjacent vertex,26//       {27//         marked[w] = true;28//         queue.enqueue(w);29//       }30//   }31// }32// ```33// Indeed, it has it's queue, which holds pairs of nodes, one from each graph,34// this is the `DeclsToCheck` member. `VisitedDecls` plays the role of the35// marking (`marked`) functionality above, we use it to check whether we've36// already seen a pair of nodes.37//38// We put in the elements into the queue only in the toplevel decl check39// function:40// ```41// static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,42//                                      Decl *D1, Decl *D2);43// ```44// The `while` loop where we iterate over the children is implemented in45// `Finish()`.  And `Finish` is called only from the two **member** functions46// which check the equivalency of two Decls or two Types. ASTImporter (and47// other clients) call only these functions.48//49// The `static` implementation functions are called from `Finish`, these push50// the children nodes to the queue via `static bool51// IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1,52// Decl *D2)`.  So far so good, this is almost like the BFS.  However, if we53// let a static implementation function to call `Finish` via another **member**54// function that means we end up with two nested while loops each of them55// working on the same queue. This is wrong and nobody can reason about it's56// doing. Thus, static implementation functions must not call the **member**57// functions.58//59//===----------------------------------------------------------------------===//60 61#include "clang/AST/ASTStructuralEquivalence.h"62#include "clang/AST/ASTContext.h"63#include "clang/AST/ASTDiagnostic.h"64#include "clang/AST/Attr.h"65#include "clang/AST/Decl.h"66#include "clang/AST/DeclBase.h"67#include "clang/AST/DeclCXX.h"68#include "clang/AST/DeclFriend.h"69#include "clang/AST/DeclObjC.h"70#include "clang/AST/DeclOpenACC.h"71#include "clang/AST/DeclOpenMP.h"72#include "clang/AST/DeclTemplate.h"73#include "clang/AST/ExprCXX.h"74#include "clang/AST/ExprConcepts.h"75#include "clang/AST/ExprObjC.h"76#include "clang/AST/ExprOpenMP.h"77#include "clang/AST/NestedNameSpecifier.h"78#include "clang/AST/StmtObjC.h"79#include "clang/AST/StmtOpenACC.h"80#include "clang/AST/StmtOpenMP.h"81#include "clang/AST/StmtSYCL.h"82#include "clang/AST/TemplateBase.h"83#include "clang/AST/TemplateName.h"84#include "clang/AST/Type.h"85#include "clang/Basic/ExceptionSpecificationType.h"86#include "clang/Basic/IdentifierTable.h"87#include "clang/Basic/LLVM.h"88#include "clang/Basic/SourceLocation.h"89#include "llvm/ADT/APInt.h"90#include "llvm/ADT/APSInt.h"91#include "llvm/ADT/StringExtras.h"92#include "llvm/Support/Compiler.h"93#include "llvm/Support/ErrorHandling.h"94#include <cassert>95#include <optional>96#include <utility>97 98using namespace clang;99 100static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,101                                     QualType T1, QualType T2);102static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,103                                     Decl *D1, Decl *D2);104static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,105                                     const Stmt *S1, const Stmt *S2);106static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,107                                     const TemplateArgument &Arg1,108                                     const TemplateArgument &Arg2);109static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,110                                     const TemplateArgumentLoc &Arg1,111                                     const TemplateArgumentLoc &Arg2);112static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,113                                     NestedNameSpecifier NNS1,114                                     NestedNameSpecifier NNS2);115static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,116                                     const IdentifierInfo *Name2);117 118static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,119                                     const DeclarationName Name1,120                                     const DeclarationName Name2) {121  if (Name1.getNameKind() != Name2.getNameKind())122    return false;123 124  switch (Name1.getNameKind()) {125 126  case DeclarationName::Identifier:127    return IsStructurallyEquivalent(Name1.getAsIdentifierInfo(),128                                    Name2.getAsIdentifierInfo());129 130  case DeclarationName::CXXConstructorName:131  case DeclarationName::CXXDestructorName:132  case DeclarationName::CXXConversionFunctionName:133    return IsStructurallyEquivalent(Context, Name1.getCXXNameType(),134                                    Name2.getCXXNameType());135 136  case DeclarationName::CXXDeductionGuideName: {137    if (!IsStructurallyEquivalent(138            Context, Name1.getCXXDeductionGuideTemplate()->getDeclName(),139            Name2.getCXXDeductionGuideTemplate()->getDeclName()))140      return false;141    return IsStructurallyEquivalent(Context,142                                    Name1.getCXXDeductionGuideTemplate(),143                                    Name2.getCXXDeductionGuideTemplate());144  }145 146  case DeclarationName::CXXOperatorName:147    return Name1.getCXXOverloadedOperator() == Name2.getCXXOverloadedOperator();148 149  case DeclarationName::CXXLiteralOperatorName:150    return IsStructurallyEquivalent(Name1.getCXXLiteralIdentifier(),151                                    Name2.getCXXLiteralIdentifier());152 153  case DeclarationName::CXXUsingDirective:154    return true; // FIXME When do we consider two using directives equal?155 156  case DeclarationName::ObjCZeroArgSelector:157  case DeclarationName::ObjCOneArgSelector:158  case DeclarationName::ObjCMultiArgSelector:159    return true; // FIXME160  }161 162  llvm_unreachable("Unhandled kind of DeclarationName");163  return true;164}165 166namespace {167/// Encapsulates Stmt comparison logic.168class StmtComparer {169  StructuralEquivalenceContext &Context;170 171  // IsStmtEquivalent overloads. Each overload compares a specific statement172  // and only has to compare the data that is specific to the specific statement173  // class. Should only be called from TraverseStmt.174 175  bool IsStmtEquivalent(const AddrLabelExpr *E1, const AddrLabelExpr *E2) {176    return IsStructurallyEquivalent(Context, E1->getLabel(), E2->getLabel());177  }178 179  bool IsStmtEquivalent(const AtomicExpr *E1, const AtomicExpr *E2) {180    return E1->getOp() == E2->getOp();181  }182 183  bool IsStmtEquivalent(const BinaryOperator *E1, const BinaryOperator *E2) {184    return E1->getOpcode() == E2->getOpcode();185  }186 187  bool IsStmtEquivalent(const CallExpr *E1, const CallExpr *E2) {188    // FIXME: IsStructurallyEquivalent requires non-const Decls.189    Decl *Callee1 = const_cast<Decl *>(E1->getCalleeDecl());190    Decl *Callee2 = const_cast<Decl *>(E2->getCalleeDecl());191 192    // Compare whether both calls know their callee.193    if (static_cast<bool>(Callee1) != static_cast<bool>(Callee2))194      return false;195 196    // Both calls have no callee, so nothing to do.197    if (!static_cast<bool>(Callee1))198      return true;199 200    assert(Callee2);201    return IsStructurallyEquivalent(Context, Callee1, Callee2);202  }203 204  bool IsStmtEquivalent(const CharacterLiteral *E1,205                        const CharacterLiteral *E2) {206    return E1->getValue() == E2->getValue() && E1->getKind() == E2->getKind();207  }208 209  bool IsStmtEquivalent(const ChooseExpr *E1, const ChooseExpr *E2) {210    return true; // Semantics only depend on children.211  }212 213  bool IsStmtEquivalent(const CompoundStmt *E1, const CompoundStmt *E2) {214    // Number of children is actually checked by the generic children comparison215    // code, but a CompoundStmt is one of the few statements where the number of216    // children frequently differs and the number of statements is also always217    // precomputed. Directly comparing the number of children here is thus218    // just an optimization.219    return E1->size() == E2->size();220  }221 222  bool IsStmtEquivalent(const DeclRefExpr *DRE1, const DeclRefExpr *DRE2) {223    const ValueDecl *Decl1 = DRE1->getDecl();224    const ValueDecl *Decl2 = DRE2->getDecl();225    if (!Decl1 || !Decl2)226      return false;227    return IsStructurallyEquivalent(Context, const_cast<ValueDecl *>(Decl1),228                                    const_cast<ValueDecl *>(Decl2));229  }230 231  bool IsStmtEquivalent(const DependentScopeDeclRefExpr *DE1,232                        const DependentScopeDeclRefExpr *DE2) {233    if (!IsStructurallyEquivalent(Context, DE1->getDeclName(),234                                  DE2->getDeclName()))235      return false;236    return IsStructurallyEquivalent(Context, DE1->getQualifier(),237                                    DE2->getQualifier());238  }239 240  bool IsStmtEquivalent(const Expr *E1, const Expr *E2) {241    return IsStructurallyEquivalent(Context, E1->getType(), E2->getType());242  }243 244  bool IsStmtEquivalent(const ExpressionTraitExpr *E1,245                        const ExpressionTraitExpr *E2) {246    return E1->getTrait() == E2->getTrait() && E1->getValue() == E2->getValue();247  }248 249  bool IsStmtEquivalent(const FloatingLiteral *E1, const FloatingLiteral *E2) {250    return E1->isExact() == E2->isExact() && E1->getValue() == E2->getValue();251  }252 253  bool IsStmtEquivalent(const GenericSelectionExpr *E1,254                        const GenericSelectionExpr *E2) {255    for (auto Pair : zip_longest(E1->getAssocTypeSourceInfos(),256                                 E2->getAssocTypeSourceInfos())) {257      std::optional<TypeSourceInfo *> Child1 = std::get<0>(Pair);258      std::optional<TypeSourceInfo *> Child2 = std::get<1>(Pair);259      // Skip this case if there are a different number of associated types.260      if (!Child1 || !Child2)261        return false;262 263      if (!IsStructurallyEquivalent(Context, (*Child1)->getType(),264                                    (*Child2)->getType()))265        return false;266    }267 268    return true;269  }270 271  bool IsStmtEquivalent(const ImplicitCastExpr *CastE1,272                        const ImplicitCastExpr *CastE2) {273    return IsStructurallyEquivalent(Context, CastE1->getType(),274                                    CastE2->getType());275  }276 277  bool IsStmtEquivalent(const IntegerLiteral *E1, const IntegerLiteral *E2) {278    return E1->getValue() == E2->getValue();279  }280 281  bool IsStmtEquivalent(const MemberExpr *E1, const MemberExpr *E2) {282    return IsStructurallyEquivalent(Context, E1->getFoundDecl(),283                                    E2->getFoundDecl());284  }285 286  bool IsStmtEquivalent(const ObjCStringLiteral *E1,287                        const ObjCStringLiteral *E2) {288    // Just wraps a StringLiteral child.289    return true;290  }291 292  bool IsStmtEquivalent(const Stmt *S1, const Stmt *S2) { return true; }293 294  bool IsStmtEquivalent(const GotoStmt *S1, const GotoStmt *S2) {295    LabelDecl *L1 = S1->getLabel();296    LabelDecl *L2 = S2->getLabel();297    if (!L1 || !L2)298      return L1 == L2;299 300    IdentifierInfo *Name1 = L1->getIdentifier();301    IdentifierInfo *Name2 = L2->getIdentifier();302    return ::IsStructurallyEquivalent(Name1, Name2);303  }304 305  bool IsStmtEquivalent(const SourceLocExpr *E1, const SourceLocExpr *E2) {306    return E1->getIdentKind() == E2->getIdentKind();307  }308 309  bool IsStmtEquivalent(const StmtExpr *E1, const StmtExpr *E2) {310    return E1->getTemplateDepth() == E2->getTemplateDepth();311  }312 313  bool IsStmtEquivalent(const StringLiteral *E1, const StringLiteral *E2) {314    return E1->getBytes() == E2->getBytes();315  }316 317  bool IsStmtEquivalent(const SubstNonTypeTemplateParmExpr *E1,318                        const SubstNonTypeTemplateParmExpr *E2) {319    if (!IsStructurallyEquivalent(Context, E1->getAssociatedDecl(),320                                  E2->getAssociatedDecl()))321      return false;322    if (E1->getIndex() != E2->getIndex())323      return false;324    if (E1->getPackIndex() != E2->getPackIndex())325      return false;326    return true;327  }328 329  bool IsStmtEquivalent(const SubstNonTypeTemplateParmPackExpr *E1,330                        const SubstNonTypeTemplateParmPackExpr *E2) {331    return IsStructurallyEquivalent(Context, E1->getArgumentPack(),332                                    E2->getArgumentPack());333  }334 335  bool IsStmtEquivalent(const TypeTraitExpr *E1, const TypeTraitExpr *E2) {336    if (E1->getTrait() != E2->getTrait())337      return false;338 339    for (auto Pair : zip_longest(E1->getArgs(), E2->getArgs())) {340      std::optional<TypeSourceInfo *> Child1 = std::get<0>(Pair);341      std::optional<TypeSourceInfo *> Child2 = std::get<1>(Pair);342      // Different number of args.343      if (!Child1 || !Child2)344        return false;345 346      if (!IsStructurallyEquivalent(Context, (*Child1)->getType(),347                                    (*Child2)->getType()))348        return false;349    }350    return true;351  }352 353  bool IsStmtEquivalent(const CXXDependentScopeMemberExpr *E1,354                        const CXXDependentScopeMemberExpr *E2) {355    if (!IsStructurallyEquivalent(Context, E1->getMember(), E2->getMember())) {356      return false;357    }358    return IsStructurallyEquivalent(Context, E1->getBaseType(),359                                    E2->getBaseType());360  }361 362  bool IsStmtEquivalent(const UnaryExprOrTypeTraitExpr *E1,363                        const UnaryExprOrTypeTraitExpr *E2) {364    if (E1->getKind() != E2->getKind())365      return false;366    return IsStructurallyEquivalent(Context, E1->getTypeOfArgument(),367                                    E2->getTypeOfArgument());368  }369 370  bool IsStmtEquivalent(const UnaryOperator *E1, const UnaryOperator *E2) {371    return E1->getOpcode() == E2->getOpcode();372  }373 374  bool IsStmtEquivalent(const VAArgExpr *E1, const VAArgExpr *E2) {375    // Semantics only depend on children.376    return true;377  }378 379  bool IsStmtEquivalent(const OverloadExpr *E1, const OverloadExpr *E2) {380    if (!IsStructurallyEquivalent(Context, E1->getName(), E2->getName()))381      return false;382 383    if (static_cast<bool>(E1->getQualifier()) !=384        static_cast<bool>(E2->getQualifier()))385      return false;386    if (E1->getQualifier() &&387        !IsStructurallyEquivalent(Context, E1->getQualifier(),388                                  E2->getQualifier()))389      return false;390 391    if (E1->getNumTemplateArgs() != E2->getNumTemplateArgs())392      return false;393    const TemplateArgumentLoc *Args1 = E1->getTemplateArgs();394    const TemplateArgumentLoc *Args2 = E2->getTemplateArgs();395    for (unsigned int ArgI = 0, ArgN = E1->getNumTemplateArgs(); ArgI < ArgN;396         ++ArgI)397      if (!IsStructurallyEquivalent(Context, Args1[ArgI], Args2[ArgI]))398        return false;399 400    return true;401  }402 403  bool IsStmtEquivalent(const CXXBoolLiteralExpr *E1, const CXXBoolLiteralExpr *E2) {404    return E1->getValue() == E2->getValue();405  }406 407  /// End point of the traversal chain.408  bool TraverseStmt(const Stmt *S1, const Stmt *S2) { return true; }409 410  // Create traversal methods that traverse the class hierarchy and return411  // the accumulated result of the comparison. Each TraverseStmt overload412  // calls the TraverseStmt overload of the parent class. For example,413  // the TraverseStmt overload for 'BinaryOperator' calls the TraverseStmt414  // overload of 'Expr' which then calls the overload for 'Stmt'.415#define STMT(CLASS, PARENT)                                                    \416  bool TraverseStmt(const CLASS *S1, const CLASS *S2) {                        \417    if (!TraverseStmt(static_cast<const PARENT *>(S1),                         \418                      static_cast<const PARENT *>(S2)))                        \419      return false;                                                            \420    return IsStmtEquivalent(S1, S2);                                           \421  }422#include "clang/AST/StmtNodes.inc"423 424public:425  StmtComparer(StructuralEquivalenceContext &C) : Context(C) {}426 427  /// Determine whether two statements are equivalent. The statements have to428  /// be of the same kind. The children of the statements and their properties429  /// are not compared by this function.430  bool IsEquivalent(const Stmt *S1, const Stmt *S2) {431    if (S1->getStmtClass() != S2->getStmtClass())432      return false;433 434    // Each TraverseStmt walks the class hierarchy from the leaf class to435    // the root class 'Stmt' (e.g. 'BinaryOperator' -> 'Expr' -> 'Stmt'). Cast436    // the Stmt we have here to its specific subclass so that we call the437    // overload that walks the whole class hierarchy from leaf to root (e.g.,438    // cast to 'BinaryOperator' so that 'Expr' and 'Stmt' is traversed).439    switch (S1->getStmtClass()) {440    case Stmt::NoStmtClass:441      llvm_unreachable("Can't traverse NoStmtClass");442#define STMT(CLASS, PARENT)                                                    \443  case Stmt::StmtClass::CLASS##Class:                                          \444    return TraverseStmt(static_cast<const CLASS *>(S1),                        \445                        static_cast<const CLASS *>(S2));446#define ABSTRACT_STMT(S)447#include "clang/AST/StmtNodes.inc"448    }449    llvm_unreachable("Invalid statement kind");450  }451};452} // namespace453 454static bool455CheckStructurallyEquivalentAttributes(StructuralEquivalenceContext &Context,456                                      const Decl *D1, const Decl *D2,457                                      const Decl *PrimaryDecl = nullptr) {458  // If either declaration has an attribute on it, we treat the declarations459  // as not being structurally equivalent unless both declarations are implicit460  // (ones generated by the compiler like __NSConstantString_tag).461  //462  // FIXME: this should be handled on a case-by-case basis via tablegen in463  // Attr.td. There are multiple cases to consider: one declaration with the464  // attribute, another without it; different attribute syntax|spellings for465  // the same semantic attribute, differences in attribute arguments, order466  // in which attributes are applied, how to merge attributes if the types are467  // structurally equivalent, etc.468  const Attr *D1Attr = nullptr, *D2Attr = nullptr;469  if (D1->hasAttrs())470    D1Attr = *D1->getAttrs().begin();471  if (D2->hasAttrs())472    D2Attr = *D2->getAttrs().begin();473  if ((D1Attr || D2Attr) && !D1->isImplicit() && !D2->isImplicit()) {474    const auto *DiagnoseDecl = cast<TypeDecl>(PrimaryDecl ? PrimaryDecl : D2);475    Context.Diag2(DiagnoseDecl->getLocation(),476                  diag::warn_odr_tag_type_with_attributes)477        << Context.ToCtx.getTypeDeclType(DiagnoseDecl)478        << (PrimaryDecl != nullptr);479    if (D1Attr)480      Context.Diag1(D1Attr->getLoc(), diag::note_odr_attr_here) << D1Attr;481    if (D2Attr)482      Context.Diag1(D2Attr->getLoc(), diag::note_odr_attr_here) << D2Attr;483  }484 485  // The above diagnostic is a warning which defaults to an error. If treated486  // as a warning, we'll go ahead and allow any attribute differences to be487  // undefined behavior and the user gets what they get in terms of behavior.488  return true;489}490 491static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,492                                     const UnaryOperator *E1,493                                     const CXXOperatorCallExpr *E2) {494  return UnaryOperator::getOverloadedOperator(E1->getOpcode()) ==495             E2->getOperator() &&496         IsStructurallyEquivalent(Context, E1->getSubExpr(), E2->getArg(0));497}498 499static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,500                                     const CXXOperatorCallExpr *E1,501                                     const UnaryOperator *E2) {502  return E1->getOperator() ==503             UnaryOperator::getOverloadedOperator(E2->getOpcode()) &&504         IsStructurallyEquivalent(Context, E1->getArg(0), E2->getSubExpr());505}506 507static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,508                                     const BinaryOperator *E1,509                                     const CXXOperatorCallExpr *E2) {510  return BinaryOperator::getOverloadedOperator(E1->getOpcode()) ==511             E2->getOperator() &&512         IsStructurallyEquivalent(Context, E1->getLHS(), E2->getArg(0)) &&513         IsStructurallyEquivalent(Context, E1->getRHS(), E2->getArg(1));514}515 516static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,517                                     const CXXOperatorCallExpr *E1,518                                     const BinaryOperator *E2) {519  return E1->getOperator() ==520             BinaryOperator::getOverloadedOperator(E2->getOpcode()) &&521         IsStructurallyEquivalent(Context, E1->getArg(0), E2->getLHS()) &&522         IsStructurallyEquivalent(Context, E1->getArg(1), E2->getRHS());523}524 525/// Determine structural equivalence of two statements.526static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,527                                     const Stmt *S1, const Stmt *S2) {528  if (!S1 || !S2)529    return S1 == S2;530 531  // Check for statements with similar syntax but different AST.532  // A UnaryOperator node is more lightweight than a CXXOperatorCallExpr node.533  // The more heavyweight node is only created if the definition-time name534  // lookup had any results. The lookup results are stored CXXOperatorCallExpr535  // only. The lookup results can be different in a "From" and "To" AST even if536  // the compared structure is otherwise equivalent. For this reason we must537  // treat a similar unary/binary operator node and CXXOperatorCall node as538  // equivalent.539  if (const auto *E2CXXOperatorCall = dyn_cast<CXXOperatorCallExpr>(S2)) {540    if (const auto *E1Unary = dyn_cast<UnaryOperator>(S1))541      return IsStructurallyEquivalent(Context, E1Unary, E2CXXOperatorCall);542    if (const auto *E1Binary = dyn_cast<BinaryOperator>(S1))543      return IsStructurallyEquivalent(Context, E1Binary, E2CXXOperatorCall);544  }545  if (const auto *E1CXXOperatorCall = dyn_cast<CXXOperatorCallExpr>(S1)) {546    if (const auto *E2Unary = dyn_cast<UnaryOperator>(S2))547      return IsStructurallyEquivalent(Context, E1CXXOperatorCall, E2Unary);548    if (const auto *E2Binary = dyn_cast<BinaryOperator>(S2))549      return IsStructurallyEquivalent(Context, E1CXXOperatorCall, E2Binary);550  }551 552  // Compare the statements itself.553  StmtComparer Comparer(Context);554  if (!Comparer.IsEquivalent(S1, S2))555    return false;556 557  // Iterate over the children of both statements and also compare them.558  for (auto Pair : zip_longest(S1->children(), S2->children())) {559    std::optional<const Stmt *> Child1 = std::get<0>(Pair);560    std::optional<const Stmt *> Child2 = std::get<1>(Pair);561    // One of the statements has a different amount of children than the other,562    // so the statements can't be equivalent.563    if (!Child1 || !Child2)564      return false;565    if (!IsStructurallyEquivalent(Context, *Child1, *Child2))566      return false;567  }568  return true;569}570 571/// Determine whether two identifiers are equivalent.572static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,573                                     const IdentifierInfo *Name2) {574  if (!Name1 || !Name2)575    return Name1 == Name2;576 577  return Name1->getName() == Name2->getName();578}579 580/// Determine whether two nested-name-specifiers are equivalent.581static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,582                                     NestedNameSpecifier NNS1,583                                     NestedNameSpecifier NNS2) {584  auto Kind = NNS1.getKind();585  if (Kind != NNS2.getKind())586    return false;587  switch (Kind) {588  case NestedNameSpecifier::Kind::Null:589  case NestedNameSpecifier::Kind::Global:590    return true;591  case NestedNameSpecifier::Kind::Namespace: {592    auto [Namespace1, Prefix1] = NNS1.getAsNamespaceAndPrefix();593    auto [Namespace2, Prefix2] = NNS2.getAsNamespaceAndPrefix();594    if (!IsStructurallyEquivalent(Context,595                                  const_cast<NamespaceBaseDecl *>(Namespace1),596                                  const_cast<NamespaceBaseDecl *>(Namespace2)))597      return false;598    return IsStructurallyEquivalent(Context, Prefix1, Prefix2);599  }600  case NestedNameSpecifier::Kind::Type:601    return IsStructurallyEquivalent(Context, QualType(NNS1.getAsType(), 0),602                                    QualType(NNS2.getAsType(), 0));603  case NestedNameSpecifier::Kind::MicrosoftSuper:604    return IsStructurallyEquivalent(Context, NNS1.getAsMicrosoftSuper(),605                                    NNS2.getAsMicrosoftSuper());606  }607  return false;608}609 610static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,611                                     const DependentTemplateStorage &S1,612                                     const DependentTemplateStorage &S2) {613  if (!IsStructurallyEquivalent(Context, S1.getQualifier(), S2.getQualifier()))614    return false;615 616  IdentifierOrOverloadedOperator IO1 = S1.getName(), IO2 = S2.getName();617  const IdentifierInfo *II1 = IO1.getIdentifier(), *II2 = IO2.getIdentifier();618  if (!II1 || !II2)619    return IO1.getOperator() == IO2.getOperator();620  return IsStructurallyEquivalent(II1, II2);621}622 623static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,624                                     const TemplateName &N1,625                                     const TemplateName &N2) {626  TemplateDecl *TemplateDeclN1 = N1.getAsTemplateDecl();627  TemplateDecl *TemplateDeclN2 = N2.getAsTemplateDecl();628  if (TemplateDeclN1 && TemplateDeclN2) {629    if (!IsStructurallyEquivalent(Context, TemplateDeclN1, TemplateDeclN2))630      return false;631    // If the kind is different we compare only the template decl.632    if (N1.getKind() != N2.getKind())633      return true;634  } else if (TemplateDeclN1 || TemplateDeclN2)635    return false;636  else if (N1.getKind() != N2.getKind())637    return false;638 639  // Check for special case incompatibilities.640  switch (N1.getKind()) {641 642  case TemplateName::OverloadedTemplate: {643    OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),644                              *OS2 = N2.getAsOverloadedTemplate();645    OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),646                                        E1 = OS1->end(), E2 = OS2->end();647    for (; I1 != E1 && I2 != E2; ++I1, ++I2)648      if (!IsStructurallyEquivalent(Context, *I1, *I2))649        return false;650    return I1 == E1 && I2 == E2;651  }652 653  case TemplateName::AssumedTemplate: {654    AssumedTemplateStorage *TN1 = N1.getAsAssumedTemplateName(),655                           *TN2 = N1.getAsAssumedTemplateName();656    return TN1->getDeclName() == TN2->getDeclName();657  }658 659  case TemplateName::DependentTemplate:660    return IsStructurallyEquivalent(Context, *N1.getAsDependentTemplateName(),661                                    *N2.getAsDependentTemplateName());662 663  case TemplateName::SubstTemplateTemplateParmPack: {664    SubstTemplateTemplateParmPackStorage665        *P1 = N1.getAsSubstTemplateTemplateParmPack(),666        *P2 = N2.getAsSubstTemplateTemplateParmPack();667    return IsStructurallyEquivalent(Context, P1->getArgumentPack(),668                                    P2->getArgumentPack()) &&669           IsStructurallyEquivalent(Context, P1->getAssociatedDecl(),670                                    P2->getAssociatedDecl()) &&671           P1->getIndex() == P2->getIndex();672  }673 674   case TemplateName::Template:675   case TemplateName::QualifiedTemplate:676   case TemplateName::SubstTemplateTemplateParm:677   case TemplateName::UsingTemplate:678     // It is sufficient to check value of getAsTemplateDecl.679     break;680 681   case TemplateName::DeducedTemplate:682     // FIXME: We can't reach here.683     llvm_unreachable("unimplemented");684  }685 686  return true;687}688 689static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,690                                     ArrayRef<TemplateArgument> Args1,691                                     ArrayRef<TemplateArgument> Args2);692 693/// Determine whether two template arguments are equivalent.694static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,695                                     const TemplateArgument &Arg1,696                                     const TemplateArgument &Arg2) {697  if (Arg1.getKind() != Arg2.getKind())698    return false;699 700  switch (Arg1.getKind()) {701  case TemplateArgument::Null:702    return true;703 704  case TemplateArgument::Type:705    return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());706 707  case TemplateArgument::Integral:708    if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),709                                          Arg2.getIntegralType()))710      return false;711 712    return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),713                                     Arg2.getAsIntegral());714 715  case TemplateArgument::Declaration:716    return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());717 718  case TemplateArgument::NullPtr:719    return true; // FIXME: Is this correct?720 721  case TemplateArgument::Template:722    return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),723                                    Arg2.getAsTemplate());724 725  case TemplateArgument::TemplateExpansion:726    return IsStructurallyEquivalent(Context,727                                    Arg1.getAsTemplateOrTemplatePattern(),728                                    Arg2.getAsTemplateOrTemplatePattern());729 730  case TemplateArgument::Expression:731    return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),732                                    Arg2.getAsExpr());733 734  case TemplateArgument::StructuralValue:735    return Arg1.structurallyEquals(Arg2);736 737  case TemplateArgument::Pack:738    return IsStructurallyEquivalent(Context, Arg1.pack_elements(),739                                    Arg2.pack_elements());740  }741 742  llvm_unreachable("Invalid template argument kind");743}744 745/// Determine structural equivalence of two template argument lists.746static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,747                                     ArrayRef<TemplateArgument> Args1,748                                     ArrayRef<TemplateArgument> Args2) {749  if (Args1.size() != Args2.size())750    return false;751  for (unsigned I = 0, N = Args1.size(); I != N; ++I) {752    if (!IsStructurallyEquivalent(Context, Args1[I], Args2[I]))753      return false;754  }755  return true;756}757 758/// Determine whether two template argument locations are equivalent.759static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,760                                     const TemplateArgumentLoc &Arg1,761                                     const TemplateArgumentLoc &Arg2) {762  return IsStructurallyEquivalent(Context, Arg1.getArgument(),763                                  Arg2.getArgument());764}765 766/// Determine structural equivalence for the common part of array767/// types.768static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,769                                          const ArrayType *Array1,770                                          const ArrayType *Array2) {771  if (!IsStructurallyEquivalent(Context, Array1->getElementType(),772                                Array2->getElementType()))773    return false;774  if (Array1->getSizeModifier() != Array2->getSizeModifier())775    return false;776  if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())777    return false;778 779  return true;780}781 782/// Determine structural equivalence based on the ExtInfo of functions. This783/// is inspired by ASTContext::mergeFunctionTypes(), we compare calling784/// conventions bits but must not compare some other bits.785static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,786                                     FunctionType::ExtInfo EI1,787                                     FunctionType::ExtInfo EI2) {788  // Compatible functions must have compatible calling conventions.789  if (EI1.getCC() != EI2.getCC())790    return false;791 792  // Regparm is part of the calling convention.793  if (EI1.getHasRegParm() != EI2.getHasRegParm())794    return false;795  if (EI1.getRegParm() != EI2.getRegParm())796    return false;797 798  if (EI1.getProducesResult() != EI2.getProducesResult())799    return false;800  if (EI1.getNoCallerSavedRegs() != EI2.getNoCallerSavedRegs())801    return false;802  if (EI1.getNoCfCheck() != EI2.getNoCfCheck())803    return false;804 805  return true;806}807 808/// Check the equivalence of exception specifications.809static bool IsEquivalentExceptionSpec(StructuralEquivalenceContext &Context,810                                      const FunctionProtoType *Proto1,811                                      const FunctionProtoType *Proto2) {812 813  auto Spec1 = Proto1->getExceptionSpecType();814  auto Spec2 = Proto2->getExceptionSpecType();815 816  if (isUnresolvedExceptionSpec(Spec1) || isUnresolvedExceptionSpec(Spec2))817    return true;818 819  if (Spec1 != Spec2)820    return false;821  if (Spec1 == EST_Dynamic) {822    if (Proto1->getNumExceptions() != Proto2->getNumExceptions())823      return false;824    for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {825      if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),826                                    Proto2->getExceptionType(I)))827        return false;828    }829  } else if (isComputedNoexcept(Spec1)) {830    if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),831                                  Proto2->getNoexceptExpr()))832      return false;833  }834 835  return true;836}837 838/// Determine structural equivalence of two types.839static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,840                                     QualType T1, QualType T2) {841  if (T1.isNull() || T2.isNull())842    return T1.isNull() && T2.isNull();843 844  QualType OrigT1 = T1;845  QualType OrigT2 = T2;846 847  if (!Context.StrictTypeSpelling) {848    // We aren't being strict about token-to-token equivalence of types,849    // so map down to the canonical type.850    T1 = Context.FromCtx.getCanonicalType(T1);851    T2 = Context.ToCtx.getCanonicalType(T2);852  }853 854  if (T1.getQualifiers() != T2.getQualifiers())855    return false;856 857  Type::TypeClass TC = T1->getTypeClass();858 859  if (T1->getTypeClass() != T2->getTypeClass()) {860    // Compare function types with prototypes vs. without prototypes as if861    // both did not have prototypes.862    if (T1->getTypeClass() == Type::FunctionProto &&863        T2->getTypeClass() == Type::FunctionNoProto)864      TC = Type::FunctionNoProto;865    else if (T1->getTypeClass() == Type::FunctionNoProto &&866             T2->getTypeClass() == Type::FunctionProto)867      TC = Type::FunctionNoProto;868    else if (Context.LangOpts.C23 && !Context.StrictTypeSpelling &&869             (T1->getTypeClass() == Type::Enum ||870              T2->getTypeClass() == Type::Enum)) {871      // In C23, if not being strict about token equivalence, we need to handle872      // the case where one type is an enumeration and the other type is an873      // integral type.874      //875      // C23 6.7.3.3p16: The enumerated type is compatible with the underlying876      // type of the enumeration.877      //878      // Treat the enumeration as its underlying type and use the builtin type879      // class comparison.880      if (T1->getTypeClass() == Type::Enum) {881        T1 = cast<EnumType>(T1)->getDecl()->getIntegerType();882        assert(T2->isBuiltinType() && !T1.isNull()); // Sanity check883      } else if (T2->getTypeClass() == Type::Enum) {884        T2 = cast<EnumType>(T2)->getDecl()->getIntegerType();885        assert(T1->isBuiltinType() && !T2.isNull()); // Sanity check886      }887      TC = Type::Builtin;888    } else889      return false;890  }891 892  switch (TC) {893  case Type::Builtin:894    // FIXME: Deal with Char_S/Char_U.895    if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())896      return false;897    break;898 899  case Type::Complex:900    if (!IsStructurallyEquivalent(Context,901                                  cast<ComplexType>(T1)->getElementType(),902                                  cast<ComplexType>(T2)->getElementType()))903      return false;904    break;905 906  case Type::Adjusted:907  case Type::Decayed:908  case Type::ArrayParameter:909    if (!IsStructurallyEquivalent(Context,910                                  cast<AdjustedType>(T1)->getOriginalType(),911                                  cast<AdjustedType>(T2)->getOriginalType()))912      return false;913    break;914 915  case Type::Pointer:916    if (!IsStructurallyEquivalent(Context,917                                  cast<PointerType>(T1)->getPointeeType(),918                                  cast<PointerType>(T2)->getPointeeType()))919      return false;920    break;921 922  case Type::BlockPointer:923    if (!IsStructurallyEquivalent(Context,924                                  cast<BlockPointerType>(T1)->getPointeeType(),925                                  cast<BlockPointerType>(T2)->getPointeeType()))926      return false;927    break;928 929  case Type::LValueReference:930  case Type::RValueReference: {931    const auto *Ref1 = cast<ReferenceType>(T1);932    const auto *Ref2 = cast<ReferenceType>(T2);933    if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())934      return false;935    if (Ref1->isInnerRef() != Ref2->isInnerRef())936      return false;937    if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),938                                  Ref2->getPointeeTypeAsWritten()))939      return false;940    break;941  }942 943  case Type::MemberPointer: {944    const auto *MemPtr1 = cast<MemberPointerType>(T1);945    const auto *MemPtr2 = cast<MemberPointerType>(T2);946    if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),947                                  MemPtr2->getPointeeType()))948      return false;949    if (!IsStructurallyEquivalent(Context, MemPtr1->getQualifier(),950                                  MemPtr2->getQualifier()))951      return false;952    CXXRecordDecl *D1 = MemPtr1->getMostRecentCXXRecordDecl(),953                  *D2 = MemPtr2->getMostRecentCXXRecordDecl();954    if (D1 == D2)955      break;956    if (!D1 || !D2 || !IsStructurallyEquivalent(Context, D1, D2))957      return false;958    break;959  }960 961  case Type::ConstantArray: {962    const auto *Array1 = cast<ConstantArrayType>(T1);963    const auto *Array2 = cast<ConstantArrayType>(T2);964    if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))965      return false;966 967    if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))968      return false;969    break;970  }971 972  case Type::IncompleteArray:973    if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),974                                       cast<ArrayType>(T2)))975      return false;976    break;977 978  case Type::VariableArray: {979    const auto *Array1 = cast<VariableArrayType>(T1);980    const auto *Array2 = cast<VariableArrayType>(T2);981    if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),982                                  Array2->getSizeExpr()))983      return false;984 985    if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))986      return false;987 988    break;989  }990 991  case Type::DependentSizedArray: {992    const auto *Array1 = cast<DependentSizedArrayType>(T1);993    const auto *Array2 = cast<DependentSizedArrayType>(T2);994    if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),995                                  Array2->getSizeExpr()))996      return false;997 998    if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))999      return false;1000 1001    break;1002  }1003 1004  case Type::DependentAddressSpace: {1005    const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);1006    const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);1007    if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),1008                                  DepAddressSpace2->getAddrSpaceExpr()))1009      return false;1010    if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),1011                                  DepAddressSpace2->getPointeeType()))1012      return false;1013 1014    break;1015  }1016 1017  case Type::DependentSizedExtVector: {1018    const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);1019    const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);1020    if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),1021                                  Vec2->getSizeExpr()))1022      return false;1023    if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),1024                                  Vec2->getElementType()))1025      return false;1026    break;1027  }1028 1029  case Type::DependentVector: {1030    const auto *Vec1 = cast<DependentVectorType>(T1);1031    const auto *Vec2 = cast<DependentVectorType>(T2);1032    if (Vec1->getVectorKind() != Vec2->getVectorKind())1033      return false;1034    if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),1035                                  Vec2->getSizeExpr()))1036      return false;1037    if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),1038                                  Vec2->getElementType()))1039      return false;1040    break;1041  }1042 1043  case Type::Vector:1044  case Type::ExtVector: {1045    const auto *Vec1 = cast<VectorType>(T1);1046    const auto *Vec2 = cast<VectorType>(T2);1047    if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),1048                                  Vec2->getElementType()))1049      return false;1050    if (Vec1->getNumElements() != Vec2->getNumElements())1051      return false;1052    if (Vec1->getVectorKind() != Vec2->getVectorKind())1053      return false;1054    break;1055  }1056 1057  case Type::DependentSizedMatrix: {1058    const DependentSizedMatrixType *Mat1 = cast<DependentSizedMatrixType>(T1);1059    const DependentSizedMatrixType *Mat2 = cast<DependentSizedMatrixType>(T2);1060    // The element types, row and column expressions must be structurally1061    // equivalent.1062    if (!IsStructurallyEquivalent(Context, Mat1->getRowExpr(),1063                                  Mat2->getRowExpr()) ||1064        !IsStructurallyEquivalent(Context, Mat1->getColumnExpr(),1065                                  Mat2->getColumnExpr()) ||1066        !IsStructurallyEquivalent(Context, Mat1->getElementType(),1067                                  Mat2->getElementType()))1068      return false;1069    break;1070  }1071 1072  case Type::ConstantMatrix: {1073    const ConstantMatrixType *Mat1 = cast<ConstantMatrixType>(T1);1074    const ConstantMatrixType *Mat2 = cast<ConstantMatrixType>(T2);1075    // The element types must be structurally equivalent and the number of rows1076    // and columns must match.1077    if (!IsStructurallyEquivalent(Context, Mat1->getElementType(),1078                                  Mat2->getElementType()) ||1079        Mat1->getNumRows() != Mat2->getNumRows() ||1080        Mat1->getNumColumns() != Mat2->getNumColumns())1081      return false;1082    break;1083  }1084 1085  case Type::FunctionProto: {1086    const auto *Proto1 = cast<FunctionProtoType>(T1);1087    const auto *Proto2 = cast<FunctionProtoType>(T2);1088 1089    if (Proto1->getNumParams() != Proto2->getNumParams())1090      return false;1091    for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {1092      if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),1093                                    Proto2->getParamType(I)))1094        return false;1095    }1096    if (Proto1->isVariadic() != Proto2->isVariadic())1097      return false;1098 1099    if (Proto1->getMethodQuals() != Proto2->getMethodQuals())1100      return false;1101 1102    // Check exceptions, this information is lost in canonical type.1103    const auto *OrigProto1 =1104        cast<FunctionProtoType>(OrigT1.getDesugaredType(Context.FromCtx));1105    const auto *OrigProto2 =1106        cast<FunctionProtoType>(OrigT2.getDesugaredType(Context.ToCtx));1107    if (!IsEquivalentExceptionSpec(Context, OrigProto1, OrigProto2))1108      return false;1109 1110    // Fall through to check the bits common with FunctionNoProtoType.1111    [[fallthrough]];1112  }1113 1114  case Type::FunctionNoProto: {1115    const auto *Function1 = cast<FunctionType>(T1);1116    const auto *Function2 = cast<FunctionType>(T2);1117    if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),1118                                  Function2->getReturnType()))1119      return false;1120    if (!IsStructurallyEquivalent(Context, Function1->getExtInfo(),1121                                  Function2->getExtInfo()))1122      return false;1123    break;1124  }1125 1126  case Type::UnresolvedUsing:1127    if (!IsStructurallyEquivalent(Context,1128                                  cast<UnresolvedUsingType>(T1)->getDecl(),1129                                  cast<UnresolvedUsingType>(T2)->getDecl()))1130      return false;1131    break;1132 1133  case Type::Attributed:1134    if (!IsStructurallyEquivalent(Context,1135                                  cast<AttributedType>(T1)->getModifiedType(),1136                                  cast<AttributedType>(T2)->getModifiedType()))1137      return false;1138    if (!IsStructurallyEquivalent(1139            Context, cast<AttributedType>(T1)->getEquivalentType(),1140            cast<AttributedType>(T2)->getEquivalentType()))1141      return false;1142    break;1143 1144  case Type::CountAttributed:1145    if (!IsStructurallyEquivalent(Context,1146                                  cast<CountAttributedType>(T1)->desugar(),1147                                  cast<CountAttributedType>(T2)->desugar()))1148      return false;1149    break;1150 1151  case Type::BTFTagAttributed:1152    if (!IsStructurallyEquivalent(1153            Context, cast<BTFTagAttributedType>(T1)->getWrappedType(),1154            cast<BTFTagAttributedType>(T2)->getWrappedType()))1155      return false;1156    break;1157 1158  case Type::HLSLAttributedResource:1159    if (!IsStructurallyEquivalent(1160            Context, cast<HLSLAttributedResourceType>(T1)->getWrappedType(),1161            cast<HLSLAttributedResourceType>(T2)->getWrappedType()))1162      return false;1163    if (!IsStructurallyEquivalent(1164            Context, cast<HLSLAttributedResourceType>(T1)->getContainedType(),1165            cast<HLSLAttributedResourceType>(T2)->getContainedType()))1166      return false;1167    if (cast<HLSLAttributedResourceType>(T1)->getAttrs() !=1168        cast<HLSLAttributedResourceType>(T2)->getAttrs())1169      return false;1170    break;1171 1172  case Type::HLSLInlineSpirv:1173    if (cast<HLSLInlineSpirvType>(T1)->getOpcode() !=1174            cast<HLSLInlineSpirvType>(T2)->getOpcode() ||1175        cast<HLSLInlineSpirvType>(T1)->getSize() !=1176            cast<HLSLInlineSpirvType>(T2)->getSize() ||1177        cast<HLSLInlineSpirvType>(T1)->getAlignment() !=1178            cast<HLSLInlineSpirvType>(T2)->getAlignment())1179      return false;1180    for (size_t I = 0; I < cast<HLSLInlineSpirvType>(T1)->getOperands().size();1181         I++) {1182      if (cast<HLSLInlineSpirvType>(T1)->getOperands()[I] !=1183          cast<HLSLInlineSpirvType>(T2)->getOperands()[I]) {1184        return false;1185      }1186    }1187    break;1188 1189  case Type::Paren:1190    if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),1191                                  cast<ParenType>(T2)->getInnerType()))1192      return false;1193    break;1194 1195  case Type::MacroQualified:1196    if (!IsStructurallyEquivalent(1197            Context, cast<MacroQualifiedType>(T1)->getUnderlyingType(),1198            cast<MacroQualifiedType>(T2)->getUnderlyingType()))1199      return false;1200    break;1201 1202  case Type::Using: {1203    auto *U1 = cast<UsingType>(T1), *U2 = cast<UsingType>(T2);1204    if (U1->getKeyword() != U2->getKeyword())1205      return false;1206    if (!IsStructurallyEquivalent(Context, U1->getQualifier(),1207                                  U2->getQualifier()))1208      return false;1209    if (!IsStructurallyEquivalent(Context, U1->getDecl(), U2->getDecl()))1210      return false;1211    if (!IsStructurallyEquivalent(Context, U1->desugar(), U2->desugar()))1212      return false;1213    break;1214  }1215  case Type::Typedef: {1216    auto *U1 = cast<TypedefType>(T1), *U2 = cast<TypedefType>(T2);1217    if (U1->getKeyword() != U2->getKeyword())1218      return false;1219    if (!IsStructurallyEquivalent(Context, U1->getQualifier(),1220                                  U2->getQualifier()))1221      return false;1222    if (!IsStructurallyEquivalent(Context, U1->getDecl(), U2->getDecl()))1223      return false;1224    if (U1->typeMatchesDecl() != U2->typeMatchesDecl())1225      return false;1226    if (!U1->typeMatchesDecl() &&1227        !IsStructurallyEquivalent(Context, U1->desugar(), U2->desugar()))1228      return false;1229    break;1230  }1231 1232  case Type::TypeOfExpr:1233    if (!IsStructurallyEquivalent(1234            Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),1235            cast<TypeOfExprType>(T2)->getUnderlyingExpr()))1236      return false;1237    break;1238 1239  case Type::TypeOf:1240    if (!IsStructurallyEquivalent(Context,1241                                  cast<TypeOfType>(T1)->getUnmodifiedType(),1242                                  cast<TypeOfType>(T2)->getUnmodifiedType()))1243      return false;1244    break;1245 1246  case Type::UnaryTransform:1247    if (!IsStructurallyEquivalent(1248            Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),1249            cast<UnaryTransformType>(T2)->getUnderlyingType()))1250      return false;1251    break;1252 1253  case Type::Decltype:1254    if (!IsStructurallyEquivalent(Context,1255                                  cast<DecltypeType>(T1)->getUnderlyingExpr(),1256                                  cast<DecltypeType>(T2)->getUnderlyingExpr()))1257      return false;1258    break;1259 1260  case Type::Auto: {1261    auto *Auto1 = cast<AutoType>(T1);1262    auto *Auto2 = cast<AutoType>(T2);1263    if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),1264                                  Auto2->getDeducedType()))1265      return false;1266    if (Auto1->isConstrained() != Auto2->isConstrained())1267      return false;1268    if (Auto1->isConstrained()) {1269      if (Auto1->getTypeConstraintConcept() !=1270          Auto2->getTypeConstraintConcept())1271        return false;1272      if (!IsStructurallyEquivalent(Context,1273                                    Auto1->getTypeConstraintArguments(),1274                                    Auto2->getTypeConstraintArguments()))1275        return false;1276    }1277    break;1278  }1279 1280  case Type::DeducedTemplateSpecialization: {1281    const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);1282    const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);1283    if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),1284                                  DT2->getTemplateName()))1285      return false;1286    if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),1287                                  DT2->getDeducedType()))1288      return false;1289    break;1290  }1291 1292  case Type::Record:1293  case Type::Enum:1294  case Type::InjectedClassName: {1295    const auto *TT1 = cast<TagType>(T1), *TT2 = cast<TagType>(T2);1296    if (TT1->getKeyword() != TT2->getKeyword())1297      return false;1298    if (TT1->isTagOwned() != TT2->isTagOwned())1299      return false;1300    if (!IsStructurallyEquivalent(Context, TT1->getQualifier(),1301                                  TT2->getQualifier()))1302      return false;1303    if (!IsStructurallyEquivalent(Context, TT1->getDecl(), TT2->getDecl()))1304      return false;1305    break;1306  }1307 1308  case Type::TemplateTypeParm: {1309    const auto *Parm1 = cast<TemplateTypeParmType>(T1);1310    const auto *Parm2 = cast<TemplateTypeParmType>(T2);1311    if (!Context.IgnoreTemplateParmDepth &&1312        Parm1->getDepth() != Parm2->getDepth())1313      return false;1314    if (Parm1->getIndex() != Parm2->getIndex())1315      return false;1316    if (Parm1->isParameterPack() != Parm2->isParameterPack())1317      return false;1318 1319    // Names of template type parameters are never significant.1320    break;1321  }1322 1323  case Type::SubstTemplateTypeParm: {1324    const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);1325    const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);1326    if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),1327                                  Subst2->getReplacementType()))1328      return false;1329    if (!IsStructurallyEquivalent(Context, Subst1->getAssociatedDecl(),1330                                  Subst2->getAssociatedDecl()))1331      return false;1332    if (Subst1->getIndex() != Subst2->getIndex())1333      return false;1334    if (Subst1->getPackIndex() != Subst2->getPackIndex())1335      return false;1336    break;1337  }1338 1339  case Type::SubstBuiltinTemplatePack: {1340    const auto *Subst1 = cast<SubstBuiltinTemplatePackType>(T1);1341    const auto *Subst2 = cast<SubstBuiltinTemplatePackType>(T2);1342    if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),1343                                  Subst2->getArgumentPack()))1344      return false;1345    break;1346  }1347  case Type::SubstTemplateTypeParmPack: {1348    const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);1349    const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);1350    if (!IsStructurallyEquivalent(Context, Subst1->getAssociatedDecl(),1351                                  Subst2->getAssociatedDecl()))1352      return false;1353    if (Subst1->getIndex() != Subst2->getIndex())1354      return false;1355    if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),1356                                  Subst2->getArgumentPack()))1357      return false;1358    break;1359  }1360 1361  case Type::TemplateSpecialization: {1362    const auto *Spec1 = cast<TemplateSpecializationType>(T1);1363    const auto *Spec2 = cast<TemplateSpecializationType>(T2);1364    if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),1365                                  Spec2->getTemplateName()))1366      return false;1367    if (!IsStructurallyEquivalent(Context, Spec1->template_arguments(),1368                                  Spec2->template_arguments()))1369      return false;1370    break;1371  }1372 1373  case Type::DependentName: {1374    const auto *Typename1 = cast<DependentNameType>(T1);1375    const auto *Typename2 = cast<DependentNameType>(T2);1376    if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),1377                                  Typename2->getQualifier()))1378      return false;1379    if (!IsStructurallyEquivalent(Typename1->getIdentifier(),1380                                  Typename2->getIdentifier()))1381      return false;1382 1383    break;1384  }1385 1386  case Type::PackExpansion:1387    if (!IsStructurallyEquivalent(Context,1388                                  cast<PackExpansionType>(T1)->getPattern(),1389                                  cast<PackExpansionType>(T2)->getPattern()))1390      return false;1391    break;1392 1393  case Type::PackIndexing:1394    if (!IsStructurallyEquivalent(Context,1395                                  cast<PackIndexingType>(T1)->getPattern(),1396                                  cast<PackIndexingType>(T2)->getPattern()))1397      if (!IsStructurallyEquivalent(Context,1398                                    cast<PackIndexingType>(T1)->getIndexExpr(),1399                                    cast<PackIndexingType>(T2)->getIndexExpr()))1400        return false;1401    break;1402 1403  case Type::ObjCInterface: {1404    const auto *Iface1 = cast<ObjCInterfaceType>(T1);1405    const auto *Iface2 = cast<ObjCInterfaceType>(T2);1406    if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),1407                                  Iface2->getDecl()))1408      return false;1409    break;1410  }1411 1412  case Type::ObjCTypeParam: {1413    const auto *Obj1 = cast<ObjCTypeParamType>(T1);1414    const auto *Obj2 = cast<ObjCTypeParamType>(T2);1415    if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))1416      return false;1417 1418    if (Obj1->getNumProtocols() != Obj2->getNumProtocols())1419      return false;1420    for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {1421      if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),1422                                    Obj2->getProtocol(I)))1423        return false;1424    }1425    break;1426  }1427 1428  case Type::ObjCObject: {1429    const auto *Obj1 = cast<ObjCObjectType>(T1);1430    const auto *Obj2 = cast<ObjCObjectType>(T2);1431    if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),1432                                  Obj2->getBaseType()))1433      return false;1434    if (Obj1->getNumProtocols() != Obj2->getNumProtocols())1435      return false;1436    for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {1437      if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),1438                                    Obj2->getProtocol(I)))1439        return false;1440    }1441    break;1442  }1443 1444  case Type::ObjCObjectPointer: {1445    const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);1446    const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);1447    if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),1448                                  Ptr2->getPointeeType()))1449      return false;1450    break;1451  }1452 1453  case Type::Atomic:1454    if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),1455                                  cast<AtomicType>(T2)->getValueType()))1456      return false;1457    break;1458 1459  case Type::Pipe:1460    if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),1461                                  cast<PipeType>(T2)->getElementType()))1462      return false;1463    break;1464  case Type::BitInt: {1465    const auto *Int1 = cast<BitIntType>(T1);1466    const auto *Int2 = cast<BitIntType>(T2);1467 1468    if (Int1->isUnsigned() != Int2->isUnsigned() ||1469        Int1->getNumBits() != Int2->getNumBits())1470      return false;1471    break;1472  }1473  case Type::DependentBitInt: {1474    const auto *Int1 = cast<DependentBitIntType>(T1);1475    const auto *Int2 = cast<DependentBitIntType>(T2);1476 1477    if (Int1->isUnsigned() != Int2->isUnsigned() ||1478        !IsStructurallyEquivalent(Context, Int1->getNumBitsExpr(),1479                                  Int2->getNumBitsExpr()))1480      return false;1481    break;1482  }1483  case Type::PredefinedSugar: {1484    const auto *TP1 = cast<PredefinedSugarType>(T1);1485    const auto *TP2 = cast<PredefinedSugarType>(T2);1486    if (TP1->getKind() != TP2->getKind())1487      return false;1488    break;1489  }1490  } // end switch1491 1492  return true;1493}1494 1495static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,1496                                     VarDecl *D1, VarDecl *D2) {1497  IdentifierInfo *Name1 = D1->getIdentifier();1498  IdentifierInfo *Name2 = D2->getIdentifier();1499  if (!::IsStructurallyEquivalent(Name1, Name2))1500    return false;1501 1502  if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))1503    return false;1504 1505  // Compare storage class and initializer only if none or both are a1506  // definition. Like a forward-declaration matches a class definition, variable1507  // declarations that are not definitions should match with the definitions.1508  if (D1->isThisDeclarationADefinition() != D2->isThisDeclarationADefinition())1509    return true;1510 1511  if (D1->getStorageClass() != D2->getStorageClass())1512    return false;1513 1514  return IsStructurallyEquivalent(Context, D1->getInit(), D2->getInit());1515}1516 1517static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,1518                                     FieldDecl *Field1, FieldDecl *Field2,1519                                     QualType Owner2Type) {1520  const auto *Owner2 = cast<Decl>(Field2->getDeclContext());1521 1522  // In C23 mode, check for structural equivalence of attributes on the fields.1523  // FIXME: Should this happen in C++ as well?1524  if (Context.LangOpts.C23 &&1525      !CheckStructurallyEquivalentAttributes(Context, Field1, Field2, Owner2))1526    return false;1527 1528  // For anonymous structs/unions, match up the anonymous struct/union type1529  // declarations directly, so that we don't go off searching for anonymous1530  // types1531  if (Field1->isAnonymousStructOrUnion() &&1532      Field2->isAnonymousStructOrUnion()) {1533    RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();1534    RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();1535    return IsStructurallyEquivalent(Context, D1, D2);1536  }1537 1538  // Check for equivalent field names.1539  IdentifierInfo *Name1 = Field1->getIdentifier();1540  IdentifierInfo *Name2 = Field2->getIdentifier();1541  if (!::IsStructurallyEquivalent(Name1, Name2)) {1542    if (Context.Complain) {1543      Context.Diag2(1544          Owner2->getLocation(),1545          Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))1546          << Owner2Type << (&Context.FromCtx != &Context.ToCtx);1547      Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)1548          << Field2->getDeclName();1549      Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)1550          << Field1->getDeclName();1551    }1552    return false;1553  }1554 1555  if (!IsStructurallyEquivalent(Context, Field1->getType(),1556                                Field2->getType())) {1557    if (Context.Complain) {1558      Context.Diag2(1559          Owner2->getLocation(),1560          Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))1561          << Owner2Type << (&Context.FromCtx != &Context.ToCtx);1562      Context.Diag2(Field2->getLocation(), diag::note_odr_field)1563          << Field2->getDeclName() << Field2->getType();1564      Context.Diag1(Field1->getLocation(), diag::note_odr_field)1565          << Field1->getDeclName() << Field1->getType();1566    }1567    return false;1568  }1569 1570  if ((Field1->isBitField() || Field2->isBitField()) &&1571      !IsStructurallyEquivalent(Context, Field1->getBitWidth(),1572                                Field2->getBitWidth())) {1573    // Two bit-fields can be structurally unequivalent but still be okay for1574    // the purposes of C where they simply need to have the same values, not1575    // the same token sequences.1576    bool Diagnose = true;1577    if (Context.LangOpts.C23 && Field1->isBitField() && Field2->isBitField())1578      Diagnose = Field1->getBitWidthValue() != Field2->getBitWidthValue();1579 1580    if (Diagnose && Context.Complain) {1581      auto DiagNote = [&](const FieldDecl *FD,1582                          DiagnosticBuilder (1583                              StructuralEquivalenceContext::*Diag)(1584                              SourceLocation, unsigned)) {1585        if (FD->isBitField()) {1586          (Context.*Diag)(FD->getLocation(), diag::note_odr_field_bit_width)1587              << FD->getDeclName() << FD->getBitWidthValue();1588        } else {1589          (Context.*Diag)(FD->getLocation(), diag::note_odr_field_not_bit_field)1590              << FD->getDeclName();1591        }1592      };1593 1594      Context.Diag2(1595          Owner2->getLocation(),1596          Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))1597          << Owner2Type << (&Context.FromCtx != &Context.ToCtx);1598      DiagNote(Field2, &StructuralEquivalenceContext::Diag2);1599      DiagNote(Field1, &StructuralEquivalenceContext::Diag1);1600    }1601    return false;1602  }1603 1604  return true;1605}1606 1607/// Determine structural equivalence of two fields.1608static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,1609                                     FieldDecl *Field1, FieldDecl *Field2) {1610  const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());1611  return IsStructurallyEquivalent(Context, Field1, Field2,1612                                  Context.ToCtx.getCanonicalTagType(Owner2));1613}1614 1615/// Determine structural equivalence of two methods.1616static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,1617                                     CXXMethodDecl *Method1,1618                                     CXXMethodDecl *Method2) {1619  if (!Method1 && !Method2)1620    return true;1621  if (!Method1 || !Method2)1622    return false;1623 1624  bool PropertiesEqual =1625      Method1->getDeclKind() == Method2->getDeclKind() &&1626      Method1->getRefQualifier() == Method2->getRefQualifier() &&1627      Method1->getAccess() == Method2->getAccess() &&1628      Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&1629      Method1->isStatic() == Method2->isStatic() &&1630      Method1->isImplicitObjectMemberFunction() ==1631          Method2->isImplicitObjectMemberFunction() &&1632      Method1->isConst() == Method2->isConst() &&1633      Method1->isVolatile() == Method2->isVolatile() &&1634      Method1->isVirtual() == Method2->isVirtual() &&1635      Method1->isPureVirtual() == Method2->isPureVirtual() &&1636      Method1->isDefaulted() == Method2->isDefaulted() &&1637      Method1->isDeleted() == Method2->isDeleted();1638  if (!PropertiesEqual)1639    return false;1640  // FIXME: Check for 'final'.1641 1642  if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {1643    auto *Constructor2 = cast<CXXConstructorDecl>(Method2);1644    if (!Constructor1->getExplicitSpecifier().isEquivalent(1645            Constructor2->getExplicitSpecifier()))1646      return false;1647  }1648 1649  if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {1650    auto *Conversion2 = cast<CXXConversionDecl>(Method2);1651    if (!Conversion1->getExplicitSpecifier().isEquivalent(1652            Conversion2->getExplicitSpecifier()))1653      return false;1654    if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),1655                                  Conversion2->getConversionType()))1656      return false;1657  }1658 1659  const IdentifierInfo *Name1 = Method1->getIdentifier();1660  const IdentifierInfo *Name2 = Method2->getIdentifier();1661  if (!::IsStructurallyEquivalent(Name1, Name2)) {1662    return false;1663    // TODO: Names do not match, add warning like at check for FieldDecl.1664  }1665 1666  // Check the prototypes.1667  if (!::IsStructurallyEquivalent(Context,1668                                  Method1->getType(), Method2->getType()))1669    return false;1670 1671  return true;1672}1673 1674/// Determine structural equivalence of two lambda classes.1675static bool1676IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,1677                                CXXRecordDecl *D1, CXXRecordDecl *D2) {1678  assert(D1->isLambda() && D2->isLambda() &&1679         "Must be called on lambda classes");1680  if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(),1681                                D2->getLambdaCallOperator()))1682    return false;1683 1684  return true;1685}1686 1687/// Determine if context of a class is equivalent.1688static bool1689IsRecordContextStructurallyEquivalent(StructuralEquivalenceContext &Context,1690                                      RecordDecl *D1, RecordDecl *D2) {1691  // The context should be completely equal, including anonymous and inline1692  // namespaces.1693  // We compare objects as part of full translation units, not subtrees of1694  // translation units.1695  DeclContext *DC1 = D1->getDeclContext()->getNonTransparentContext();1696  DeclContext *DC2 = D2->getDeclContext()->getNonTransparentContext();1697  while (true) {1698    // Special case: We allow a struct defined in a function to be equivalent1699    // with a similar struct defined outside of a function.1700    if ((DC1->isFunctionOrMethod() && DC2->isTranslationUnit()) ||1701        (DC2->isFunctionOrMethod() && DC1->isTranslationUnit()))1702      return true;1703 1704    if (DC1->getDeclKind() != DC2->getDeclKind())1705      return false;1706    if (DC1->isTranslationUnit())1707      break;1708    if (DC1->isInlineNamespace() != DC2->isInlineNamespace())1709      return false;1710    if (const auto *ND1 = dyn_cast<NamedDecl>(DC1)) {1711      const auto *ND2 = cast<NamedDecl>(DC2);1712      if (!DC1->isInlineNamespace() &&1713          !IsStructurallyEquivalent(ND1->getIdentifier(), ND2->getIdentifier()))1714        return false;1715    }1716 1717    if (auto *D1Spec = dyn_cast<ClassTemplateSpecializationDecl>(DC1)) {1718      auto *D2Spec = dyn_cast<ClassTemplateSpecializationDecl>(DC2);1719      if (!IsStructurallyEquivalent(Context, D1Spec, D2Spec))1720        return false;1721    }1722 1723    DC1 = DC1->getParent()->getNonTransparentContext();1724    DC2 = DC2->getParent()->getNonTransparentContext();1725  }1726 1727  return true;1728}1729 1730static bool NameIsStructurallyEquivalent(const TagDecl &D1, const TagDecl &D2) {1731  auto GetName = [](const TagDecl &D) -> const IdentifierInfo * {1732    if (const IdentifierInfo *Name = D.getIdentifier())1733      return Name;1734    if (const TypedefNameDecl *TypedefName = D.getTypedefNameForAnonDecl())1735      return TypedefName->getIdentifier();1736    return nullptr;1737  };1738  return IsStructurallyEquivalent(GetName(D1), GetName(D2));1739}1740 1741/// Determine structural equivalence of two records.1742static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,1743                                     RecordDecl *D1, RecordDecl *D2) {1744  // C23 6.2.7p1:1745  // ... Moreover, two complete structure, union, or enumerated types declared1746  // with the same tag are compatible if members satisfy the following1747  // requirements:1748  //  - there shall be a one-to-one correspondence between their members such1749  //    that each pair of corresponding members are declared with compatible1750  //    types;1751  //  - if one member of the pair is declared with an alignment specifier, the1752  //    other is declared with an equivalent alignment specifier;1753  //  - and, if one member of the pair is declared with a name, the other is1754  //    declared with the same name.1755  // For two structures, corresponding members shall be declared in the same1756  // order. For two unions declared in the same translation unit, corresponding1757  // members shall be declared in the same order. For two structures or unions,1758  // corresponding bit-fields shall have the same widths. ... For determining1759  // type compatibility, anonymous structures and unions are considered a1760  // regular member of the containing structure or union type, and the type of1761  // an anonymous structure or union is considered compatible to the type of1762  // another anonymous structure or union, respectively, if their members1763  // fulfill the preceding requirements. ... Otherwise, the structure, union,1764  // or enumerated types are incompatible.1765  if (!NameIsStructurallyEquivalent(*D1, *D2))1766    return false;1767 1768  if (D1->isUnion() != D2->isUnion()) {1769    if (Context.Complain) {1770      Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(1771                                           diag::err_odr_tag_type_inconsistent))1772          << Context.ToCtx.getCanonicalTagType(D2)1773          << (&Context.FromCtx != &Context.ToCtx);1774      Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)1775          << D1->getDeclName() << (unsigned)D1->getTagKind();1776    }1777    return false;1778  }1779 1780  if (!D1->getDeclName() && !D2->getDeclName()) {1781    // If both anonymous structs/unions are in a record context, make sure1782    // they occur in the same location in the context records.1783    if (UnsignedOrNone Index1 =1784            StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {1785      if (UnsignedOrNone Index2 =1786              StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(1787                  D2)) {1788        if (*Index1 != *Index2)1789          return false;1790      }1791    }1792  }1793 1794  // In C23 mode, check for structural equivalence of attributes on the record1795  // itself. FIXME: Should this happen in C++ as well?1796  if (Context.LangOpts.C23 &&1797      !CheckStructurallyEquivalentAttributes(Context, D1, D2))1798    return false;1799 1800  // If the records occur in different context (namespace), these should be1801  // different. This is specially important if the definition of one or both1802  // records is missing. In C23, different contexts do not make for a different1803  // structural type (a local struct definition can be a valid redefinition of1804  // a file scope struct definition).1805  if (!Context.LangOpts.C23 &&1806      !IsRecordContextStructurallyEquivalent(Context, D1, D2))1807    return false;1808 1809  // If both declarations are class template specializations, we know1810  // the ODR applies, so check the template and template arguments.1811  const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);1812  const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);1813  if (Spec1 && Spec2) {1814    // Check that the specialized templates are the same.1815    if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),1816                                  Spec2->getSpecializedTemplate()))1817      return false;1818 1819    // Check that the template arguments are the same.1820    if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())1821      return false;1822 1823    for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)1824      if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),1825                                    Spec2->getTemplateArgs().get(I)))1826        return false;1827  }1828  // If one is a class template specialization and the other is not, these1829  // structures are different.1830  else if (Spec1 || Spec2)1831    return false;1832 1833  // Compare the definitions of these two records. If either or both are1834  // incomplete (i.e. it is a forward decl), we assume that they are1835  // equivalent. except in C23 mode.1836  D1 = D1->getDefinition();1837  D2 = D2->getDefinition();1838  if (!D1 || !D2)1839    return !Context.LangOpts.C23;1840 1841  // If any of the records has external storage and we do a minimal check (or1842  // AST import) we assume they are equivalent. (If we didn't have this1843  // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger1844  // another AST import which in turn would call the structural equivalency1845  // check again and finally we'd have an improper result.)1846  if (Context.EqKind == StructuralEquivalenceKind::Minimal)1847    if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())1848      return true;1849 1850  // If one definition is currently being defined, we do not compare for1851  // equality and we assume that the decls are equal.1852  if (D1->isBeingDefined() || D2->isBeingDefined())1853    return true;1854 1855  if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {1856    if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {1857      if (D1CXX->hasExternalLexicalStorage() &&1858          !D1CXX->isCompleteDefinition()) {1859        D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);1860      }1861 1862      if (D1CXX->isLambda() != D2CXX->isLambda())1863        return false;1864      if (D1CXX->isLambda()) {1865        if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))1866          return false;1867      }1868 1869      if (D1CXX->getNumBases() != D2CXX->getNumBases()) {1870        if (Context.Complain) {1871          Context.Diag2(D2->getLocation(),1872                        Context.getApplicableDiagnostic(1873                            diag::err_odr_tag_type_inconsistent))1874              << Context.ToCtx.getCanonicalTagType(D2)1875              << (&Context.FromCtx != &Context.ToCtx);1876          Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)1877              << D2CXX->getNumBases();1878          Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)1879              << D1CXX->getNumBases();1880        }1881        return false;1882      }1883 1884      // Check the base classes.1885      for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),1886                                              BaseEnd1 = D1CXX->bases_end(),1887                                              Base2 = D2CXX->bases_begin();1888           Base1 != BaseEnd1; ++Base1, ++Base2) {1889        if (!IsStructurallyEquivalent(Context, Base1->getType(),1890                                      Base2->getType())) {1891          if (Context.Complain) {1892            Context.Diag2(D2->getLocation(),1893                          Context.getApplicableDiagnostic(1894                              diag::err_odr_tag_type_inconsistent))1895                << Context.ToCtx.getCanonicalTagType(D2)1896                << (&Context.FromCtx != &Context.ToCtx);1897            Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)1898                << Base2->getType() << Base2->getSourceRange();1899            Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)1900                << Base1->getType() << Base1->getSourceRange();1901          }1902          return false;1903        }1904 1905        // Check virtual vs. non-virtual inheritance mismatch.1906        if (Base1->isVirtual() != Base2->isVirtual()) {1907          if (Context.Complain) {1908            Context.Diag2(D2->getLocation(),1909                          Context.getApplicableDiagnostic(1910                              diag::err_odr_tag_type_inconsistent))1911                << Context.ToCtx.getCanonicalTagType(D2)1912                << (&Context.FromCtx != &Context.ToCtx);1913            Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)1914                << Base2->isVirtual() << Base2->getSourceRange();1915            Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)1916                << Base1->isVirtual() << Base1->getSourceRange();1917          }1918          return false;1919        }1920      }1921 1922      // Check the friends for consistency.1923      CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),1924                                     Friend2End = D2CXX->friend_end();1925      for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),1926                                          Friend1End = D1CXX->friend_end();1927           Friend1 != Friend1End; ++Friend1, ++Friend2) {1928        if (Friend2 == Friend2End) {1929          if (Context.Complain) {1930            Context.Diag2(D2->getLocation(),1931                          Context.getApplicableDiagnostic(1932                              diag::err_odr_tag_type_inconsistent))1933                << Context.ToCtx.getCanonicalTagType(D2CXX)1934                << (&Context.FromCtx != &Context.ToCtx);1935            Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);1936            Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);1937          }1938          return false;1939        }1940 1941        if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {1942          if (Context.Complain) {1943            Context.Diag2(D2->getLocation(),1944                          Context.getApplicableDiagnostic(1945                              diag::err_odr_tag_type_inconsistent))1946                << Context.ToCtx.getCanonicalTagType(D2CXX)1947                << (&Context.FromCtx != &Context.ToCtx);1948            Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);1949            Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);1950          }1951          return false;1952        }1953      }1954 1955      if (Friend2 != Friend2End) {1956        if (Context.Complain) {1957          Context.Diag2(D2->getLocation(),1958                        Context.getApplicableDiagnostic(1959                            diag::err_odr_tag_type_inconsistent))1960              << Context.ToCtx.getCanonicalTagType(D2)1961              << (&Context.FromCtx != &Context.ToCtx);1962          Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);1963          Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);1964        }1965        return false;1966      }1967    } else if (D1CXX->getNumBases() > 0) {1968      if (Context.Complain) {1969        Context.Diag2(D2->getLocation(),1970                      Context.getApplicableDiagnostic(1971                          diag::err_odr_tag_type_inconsistent))1972            << Context.ToCtx.getCanonicalTagType(D2)1973            << (&Context.FromCtx != &Context.ToCtx);1974        const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();1975        Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)1976            << Base1->getType() << Base1->getSourceRange();1977        Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);1978      }1979      return false;1980    }1981  }1982 1983  // Check the fields for consistency.1984  CanQualType D2Type = Context.ToCtx.getCanonicalTagType(D2);1985  RecordDecl::field_iterator Field2 = D2->field_begin(),1986                             Field2End = D2->field_end();1987  for (RecordDecl::field_iterator Field1 = D1->field_begin(),1988                                  Field1End = D1->field_end();1989       Field1 != Field1End; ++Field1, ++Field2) {1990    if (Field2 == Field2End) {1991      if (Context.Complain) {1992        Context.Diag2(D2->getLocation(),1993                      Context.getApplicableDiagnostic(1994                          diag::err_odr_tag_type_inconsistent))1995            << Context.ToCtx.getCanonicalTagType(D2)1996            << (&Context.FromCtx != &Context.ToCtx);1997        Context.Diag1(Field1->getLocation(), diag::note_odr_field)1998            << Field1->getDeclName() << Field1->getType();1999        Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);2000      }2001      return false;2002    }2003 2004    if (!IsStructurallyEquivalent(Context, *Field1, *Field2, D2Type))2005      return false;2006  }2007 2008  if (Field2 != Field2End) {2009    if (Context.Complain) {2010      Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(2011                                           diag::err_odr_tag_type_inconsistent))2012          << Context.ToCtx.getCanonicalTagType(D2)2013          << (&Context.FromCtx != &Context.ToCtx);2014      Context.Diag2(Field2->getLocation(), diag::note_odr_field)2015          << Field2->getDeclName() << Field2->getType();2016      Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);2017    }2018    return false;2019  }2020 2021  return true;2022}2023 2024static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2025                                     EnumConstantDecl *D1,2026                                     EnumConstantDecl *D2) {2027  const llvm::APSInt &FromVal = D1->getInitVal();2028  const llvm::APSInt &ToVal = D2->getInitVal();2029  if (FromVal.isSigned() != ToVal.isSigned())2030    return false;2031  if (FromVal.getBitWidth() != ToVal.getBitWidth())2032    return false;2033  if (FromVal != ToVal)2034    return false;2035 2036  if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))2037    return false;2038 2039  // Init expressions are the most expensive check, so do them last.2040  return IsStructurallyEquivalent(Context, D1->getInitExpr(),2041                                  D2->getInitExpr());2042}2043 2044/// Determine structural equivalence of two enums.2045static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2046                                     EnumDecl *D1, EnumDecl *D2) {2047  if (!NameIsStructurallyEquivalent(*D1, *D2)) {2048    return false;2049  }2050 2051  // Compare the definitions of these two enums. If either or both are2052  // incomplete (i.e. forward declared), we assume that they are equivalent.2053  // In C23, the order of the enumerations does not matter, only the names and2054  // values do.2055  D1 = D1->getDefinition();2056  D2 = D2->getDefinition();2057  if (!D1 || !D2)2058    return true;2059 2060  if (Context.LangOpts.C23 &&2061      !CheckStructurallyEquivalentAttributes(Context, D1, D2))2062    return false;2063 2064  // In C23, if one enumeration has a fixed underlying type, the other shall2065  // have a compatible fixed underlying type (6.2.7).2066  if (Context.LangOpts.C23) {2067    if (D1->isFixed() != D2->isFixed()) {2068      if (Context.Complain) {2069        Context.Diag2(D2->getLocation(),2070                      Context.getApplicableDiagnostic(2071                          diag::err_odr_tag_type_inconsistent))2072            << Context.ToCtx.getCanonicalTagType(D2)2073            << (&Context.FromCtx != &Context.ToCtx);2074        Context.Diag1(D1->getLocation(),2075                      D1->isFixed()2076                          ? diag::note_odr_fixed_underlying_type2077                          : diag::note_odr_missing_fixed_underlying_type)2078            << D1;2079        Context.Diag2(D2->getLocation(),2080                      D2->isFixed()2081                          ? diag::note_odr_fixed_underlying_type2082                          : diag::note_odr_missing_fixed_underlying_type)2083            << D2;2084      }2085      return false;2086    }2087    if (D1->isFixed()) {2088      assert(D2->isFixed() && "enums expected to have fixed underlying types");2089      if (!IsStructurallyEquivalent(Context, D1->getIntegerType(),2090                                    D2->getIntegerType())) {2091        if (Context.Complain) {2092          Context.Diag2(D2->getLocation(),2093                        Context.getApplicableDiagnostic(2094                            diag::err_odr_tag_type_inconsistent))2095              << Context.ToCtx.getCanonicalTagType(D2)2096              << (&Context.FromCtx != &Context.ToCtx);2097          Context.Diag2(D2->getLocation(),2098                        diag::note_odr_incompatible_fixed_underlying_type)2099              << D2 << D2->getIntegerType() << D1->getIntegerType();2100        }2101        return false;2102      }2103    }2104  }2105 2106  llvm::SmallVector<const EnumConstantDecl *, 8> D1Enums, D2Enums;2107  auto CopyEnumerators =2108      [](auto &&Range, llvm::SmallVectorImpl<const EnumConstantDecl *> &Cont) {2109        for (const EnumConstantDecl *ECD : Range)2110          Cont.push_back(ECD);2111      };2112  CopyEnumerators(D1->enumerators(), D1Enums);2113  CopyEnumerators(D2->enumerators(), D2Enums);2114 2115  // In C23 mode, the order of the enumerations does not matter, so sort them2116  // by name to get them both into a consistent ordering.2117  if (Context.LangOpts.C23) {2118    auto Sorter = [](const EnumConstantDecl *LHS, const EnumConstantDecl *RHS) {2119      return LHS->getName() < RHS->getName();2120    };2121    llvm::sort(D1Enums, Sorter);2122    llvm::sort(D2Enums, Sorter);2123  }2124 2125  auto EC2 = D2Enums.begin(), EC2End = D2Enums.end();2126  for (auto EC1 = D1Enums.begin(), EC1End = D1Enums.end(); EC1 != EC1End;2127       ++EC1, ++EC2) {2128    if (EC2 == EC2End) {2129      if (Context.Complain) {2130        Context.Diag2(D2->getLocation(),2131                      Context.getApplicableDiagnostic(2132                          diag::err_odr_tag_type_inconsistent))2133            << Context.ToCtx.getCanonicalTagType(D2)2134            << (&Context.FromCtx != &Context.ToCtx);2135        Context.Diag1((*EC1)->getLocation(), diag::note_odr_enumerator)2136            << (*EC1)->getDeclName() << toString((*EC1)->getInitVal(), 10);2137        Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);2138      }2139      return false;2140    }2141 2142    llvm::APSInt Val1 = (*EC1)->getInitVal();2143    llvm::APSInt Val2 = (*EC2)->getInitVal();2144    if (!llvm::APSInt::isSameValue(Val1, Val2) ||2145        !IsStructurallyEquivalent((*EC1)->getIdentifier(),2146                                  (*EC2)->getIdentifier())) {2147      if (Context.Complain) {2148        Context.Diag2(D2->getLocation(),2149                      Context.getApplicableDiagnostic(2150                          diag::err_odr_tag_type_inconsistent))2151            << Context.ToCtx.getCanonicalTagType(D2)2152            << (&Context.FromCtx != &Context.ToCtx);2153        Context.Diag2((*EC2)->getLocation(), diag::note_odr_enumerator)2154            << (*EC2)->getDeclName() << toString((*EC2)->getInitVal(), 10);2155        Context.Diag1((*EC1)->getLocation(), diag::note_odr_enumerator)2156            << (*EC1)->getDeclName() << toString((*EC1)->getInitVal(), 10);2157      }2158      return false;2159    }2160    if (Context.LangOpts.C23 &&2161        !CheckStructurallyEquivalentAttributes(Context, *EC1, *EC2, D2))2162      return false;2163  }2164 2165  if (EC2 != EC2End) {2166    if (Context.Complain) {2167      Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(2168                                           diag::err_odr_tag_type_inconsistent))2169          << Context.ToCtx.getCanonicalTagType(D2)2170          << (&Context.FromCtx != &Context.ToCtx);2171      Context.Diag2((*EC2)->getLocation(), diag::note_odr_enumerator)2172          << (*EC2)->getDeclName() << toString((*EC2)->getInitVal(), 10);2173      Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);2174    }2175    return false;2176  }2177 2178  return true;2179}2180 2181static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2182                                     TemplateParameterList *Params1,2183                                     TemplateParameterList *Params2) {2184  if (Params1->size() != Params2->size()) {2185    if (Context.Complain) {2186      Context.Diag2(Params2->getTemplateLoc(),2187                    Context.getApplicableDiagnostic(2188                        diag::err_odr_different_num_template_parameters))2189          << Params1->size() << Params2->size();2190      Context.Diag1(Params1->getTemplateLoc(),2191                    diag::note_odr_template_parameter_list);2192    }2193    return false;2194  }2195 2196  for (unsigned I = 0, N = Params1->size(); I != N; ++I) {2197    if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {2198      if (Context.Complain) {2199        Context.Diag2(Params2->getParam(I)->getLocation(),2200                      Context.getApplicableDiagnostic(2201                          diag::err_odr_different_template_parameter_kind));2202        Context.Diag1(Params1->getParam(I)->getLocation(),2203                      diag::note_odr_template_parameter_here);2204      }2205      return false;2206    }2207 2208    if (!IsStructurallyEquivalent(Context, Params1->getParam(I),2209                                  Params2->getParam(I)))2210      return false;2211  }2212 2213  return true;2214}2215 2216static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2217                                     TemplateTypeParmDecl *D1,2218                                     TemplateTypeParmDecl *D2) {2219  if (D1->isParameterPack() != D2->isParameterPack()) {2220    if (Context.Complain) {2221      Context.Diag2(D2->getLocation(),2222                    Context.getApplicableDiagnostic(2223                        diag::err_odr_parameter_pack_non_pack))2224          << D2->isParameterPack();2225      Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)2226          << D1->isParameterPack();2227    }2228    return false;2229  }2230 2231  return true;2232}2233 2234static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2235                                     NonTypeTemplateParmDecl *D1,2236                                     NonTypeTemplateParmDecl *D2) {2237  if (D1->isParameterPack() != D2->isParameterPack()) {2238    if (Context.Complain) {2239      Context.Diag2(D2->getLocation(),2240                    Context.getApplicableDiagnostic(2241                        diag::err_odr_parameter_pack_non_pack))2242          << D2->isParameterPack();2243      Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)2244          << D1->isParameterPack();2245    }2246    return false;2247  }2248  if (!Context.IgnoreTemplateParmDepth && D1->getDepth() != D2->getDepth())2249    return false;2250  if (D1->getIndex() != D2->getIndex())2251    return false;2252  // Check types.2253  if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {2254    if (Context.Complain) {2255      Context.Diag2(D2->getLocation(),2256                    Context.getApplicableDiagnostic(2257                        diag::err_odr_non_type_parameter_type_inconsistent))2258          << D2->getType() << D1->getType();2259      Context.Diag1(D1->getLocation(), diag::note_odr_value_here)2260          << D1->getType();2261    }2262    return false;2263  }2264 2265  return true;2266}2267 2268static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2269                                     TemplateTemplateParmDecl *D1,2270                                     TemplateTemplateParmDecl *D2) {2271  if (D1->isParameterPack() != D2->isParameterPack()) {2272    if (Context.Complain) {2273      Context.Diag2(D2->getLocation(),2274                    Context.getApplicableDiagnostic(2275                        diag::err_odr_parameter_pack_non_pack))2276          << D2->isParameterPack();2277      Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)2278          << D1->isParameterPack();2279    }2280    return false;2281  }2282 2283  // Check template parameter lists.2284  return D1->templateParameterKind() == D2->templateParameterKind() &&2285         IsStructurallyEquivalent(Context, D1->getTemplateParameters(),2286                                  D2->getTemplateParameters());2287}2288 2289static bool IsTemplateDeclCommonStructurallyEquivalent(2290    StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {2291  if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))2292    return false;2293  if (!D1->getIdentifier()) // Special name2294    if (D1->getNameAsString() != D2->getNameAsString())2295      return false;2296  return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),2297                                  D2->getTemplateParameters());2298}2299 2300static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2301                                     ClassTemplateDecl *D1,2302                                     ClassTemplateDecl *D2) {2303  // Check template parameters.2304  if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))2305    return false;2306 2307  // Check the templated declaration.2308  return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),2309                                  D2->getTemplatedDecl());2310}2311 2312static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2313                                     FunctionTemplateDecl *D1,2314                                     FunctionTemplateDecl *D2) {2315  // Check template parameters.2316  if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))2317    return false;2318 2319  // Check the templated declaration.2320  return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),2321                                  D2->getTemplatedDecl()->getType());2322}2323 2324static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2325                                     TypeAliasTemplateDecl *D1,2326                                     TypeAliasTemplateDecl *D2) {2327  // Check template parameters.2328  if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))2329    return false;2330 2331  // Check the templated declaration.2332  return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),2333                                  D2->getTemplatedDecl());2334}2335 2336static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2337                                     ConceptDecl *D1,2338                                     ConceptDecl *D2) {2339  // Check template parameters.2340  if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))2341    return false;2342 2343  // Check the constraint expression.2344  return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),2345                                  D2->getConstraintExpr());2346}2347 2348static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2349                                     FriendDecl *D1, FriendDecl *D2) {2350  if ((D1->getFriendType() && D2->getFriendDecl()) ||2351      (D1->getFriendDecl() && D2->getFriendType())) {2352      return false;2353  }2354  if (D1->getFriendType() && D2->getFriendType())2355    return IsStructurallyEquivalent(Context,2356                                    D1->getFriendType()->getType(),2357                                    D2->getFriendType()->getType());2358  if (D1->getFriendDecl() && D2->getFriendDecl())2359    return IsStructurallyEquivalent(Context, D1->getFriendDecl(),2360                                    D2->getFriendDecl());2361  return false;2362}2363 2364static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2365                                     TypedefNameDecl *D1, TypedefNameDecl *D2) {2366  if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))2367    return false;2368 2369  return IsStructurallyEquivalent(Context, D1->getUnderlyingType(),2370                                  D2->getUnderlyingType());2371}2372 2373static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2374                                     FunctionDecl *D1, FunctionDecl *D2) {2375  if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))2376    return false;2377 2378  if (D1->isOverloadedOperator()) {2379    if (!D2->isOverloadedOperator())2380      return false;2381    if (D1->getOverloadedOperator() != D2->getOverloadedOperator())2382      return false;2383  }2384 2385  // FIXME: Consider checking for function attributes as well.2386  if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))2387    return false;2388 2389  return true;2390}2391 2392static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2393                                     ObjCIvarDecl *D1, ObjCIvarDecl *D2,2394                                     QualType Owner2Type) {2395  if (D1->getAccessControl() != D2->getAccessControl())2396    return false;2397 2398  return IsStructurallyEquivalent(Context, cast<FieldDecl>(D1),2399                                  cast<FieldDecl>(D2), Owner2Type);2400}2401 2402static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2403                                     ObjCIvarDecl *D1, ObjCIvarDecl *D2) {2404  QualType Owner2Type =2405      Context.ToCtx.getObjCInterfaceType(D2->getContainingInterface());2406  return IsStructurallyEquivalent(Context, D1, D2, Owner2Type);2407}2408 2409static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2410                                     ObjCMethodDecl *Method1,2411                                     ObjCMethodDecl *Method2) {2412  bool PropertiesEqual =2413      Method1->isInstanceMethod() == Method2->isInstanceMethod() &&2414      Method1->isVariadic() == Method2->isVariadic() &&2415      Method1->isDirectMethod() == Method2->isDirectMethod();2416  if (!PropertiesEqual)2417    return false;2418 2419  // Compare selector slot names.2420  Selector Selector1 = Method1->getSelector(),2421           Selector2 = Method2->getSelector();2422  unsigned NumArgs = Selector1.getNumArgs();2423  if (NumArgs != Selector2.getNumArgs())2424    return false;2425  // Compare all selector slots. For selectors with arguments it means all arg2426  // slots. And if there are no arguments, compare the first-and-only slot.2427  unsigned SlotsToCheck = NumArgs > 0 ? NumArgs : 1;2428  for (unsigned I = 0; I < SlotsToCheck; ++I) {2429    if (!IsStructurallyEquivalent(Selector1.getIdentifierInfoForSlot(I),2430                                  Selector2.getIdentifierInfoForSlot(I)))2431      return false;2432  }2433 2434  // Compare types.2435  if (!IsStructurallyEquivalent(Context, Method1->getReturnType(),2436                                Method2->getReturnType()))2437    return false;2438  assert(2439      Method1->param_size() == Method2->param_size() &&2440      "Same number of arguments should be already enforced in Selector checks");2441  for (ObjCMethodDecl::param_type_iterator2442           ParamT1 = Method1->param_type_begin(),2443           ParamT1End = Method1->param_type_end(),2444           ParamT2 = Method2->param_type_begin(),2445           ParamT2End = Method2->param_type_end();2446       (ParamT1 != ParamT1End) && (ParamT2 != ParamT2End);2447       ++ParamT1, ++ParamT2) {2448    if (!IsStructurallyEquivalent(Context, *ParamT1, *ParamT2))2449      return false;2450  }2451 2452  return true;2453}2454 2455static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2456                                     ObjCCategoryDecl *D1,2457                                     ObjCCategoryDecl *D2) {2458  if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))2459    return false;2460 2461  const ObjCInterfaceDecl *Intf1 = D1->getClassInterface(),2462                          *Intf2 = D2->getClassInterface();2463  if ((!Intf1 || !Intf2) && (Intf1 != Intf2))2464    return false;2465 2466  if (Intf1 &&2467      !IsStructurallyEquivalent(Intf1->getIdentifier(), Intf2->getIdentifier()))2468    return false;2469 2470  // Compare protocols.2471  ObjCCategoryDecl::protocol_iterator Protocol2 = D2->protocol_begin(),2472                                      Protocol2End = D2->protocol_end();2473  for (ObjCCategoryDecl::protocol_iterator Protocol1 = D1->protocol_begin(),2474                                           Protocol1End = D1->protocol_end();2475       Protocol1 != Protocol1End; ++Protocol1, ++Protocol2) {2476    if (Protocol2 == Protocol2End)2477      return false;2478    if (!IsStructurallyEquivalent((*Protocol1)->getIdentifier(),2479                                  (*Protocol2)->getIdentifier()))2480      return false;2481  }2482  if (Protocol2 != Protocol2End)2483    return false;2484 2485  // Compare ivars.2486  QualType D2Type =2487      Intf2 ? Context.ToCtx.getObjCInterfaceType(Intf2) : QualType();2488  ObjCCategoryDecl::ivar_iterator Ivar2 = D2->ivar_begin(),2489                                  Ivar2End = D2->ivar_end();2490  for (ObjCCategoryDecl::ivar_iterator Ivar1 = D1->ivar_begin(),2491                                       Ivar1End = D1->ivar_end();2492       Ivar1 != Ivar1End; ++Ivar1, ++Ivar2) {2493    if (Ivar2 == Ivar2End)2494      return false;2495    if (!IsStructurallyEquivalent(Context, *Ivar1, *Ivar2, D2Type))2496      return false;2497  }2498  if (Ivar2 != Ivar2End)2499    return false;2500 2501  // Compare methods.2502  ObjCCategoryDecl::method_iterator Method2 = D2->meth_begin(),2503                                    Method2End = D2->meth_end();2504  for (ObjCCategoryDecl::method_iterator Method1 = D1->meth_begin(),2505                                         Method1End = D1->meth_end();2506       Method1 != Method1End; ++Method1, ++Method2) {2507    if (Method2 == Method2End)2508      return false;2509    if (!IsStructurallyEquivalent(Context, *Method1, *Method2))2510      return false;2511  }2512  if (Method2 != Method2End)2513    return false;2514 2515  return true;2516}2517 2518/// Determine structural equivalence of two declarations.2519static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,2520                                     Decl *D1, Decl *D2) {2521  // FIXME: Check for known structural equivalences via a callback of some sort.2522 2523  D1 = D1->getCanonicalDecl();2524  D2 = D2->getCanonicalDecl();2525  std::pair<Decl *, Decl *> P{D1, D2};2526 2527  // Check whether we already know that these two declarations are not2528  // structurally equivalent.2529  if (Context.NonEquivalentDecls.count(2530          std::make_tuple(D1, D2, Context.IgnoreTemplateParmDepth)))2531    return false;2532 2533  // Check if a check for these declarations is already pending.2534  // If yes D1 and D2 will be checked later (from DeclsToCheck),2535  // or these are already checked (and equivalent).2536  bool Inserted = Context.VisitedDecls.insert(P).second;2537  if (!Inserted)2538    return true;2539 2540  Context.DeclsToCheck.push(P);2541 2542  return true;2543}2544 2545DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,2546                                                      unsigned DiagID) {2547  assert(Complain && "Not allowed to complain");2548  if (LastDiagFromC2)2549    FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());2550  LastDiagFromC2 = false;2551  return FromCtx.getDiagnostics().Report(Loc, DiagID);2552}2553 2554DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,2555                                                      unsigned DiagID) {2556  assert(Complain && "Not allowed to complain");2557  if (!LastDiagFromC2)2558    ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());2559  LastDiagFromC2 = true;2560  return ToCtx.getDiagnostics().Report(Loc, DiagID);2561}2562 2563UnsignedOrNone2564StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {2565  ASTContext &Context = Anon->getASTContext();2566  CanQualType AnonTy = Context.getCanonicalTagType(Anon);2567 2568  const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());2569  if (!Owner)2570    return std::nullopt;2571 2572  unsigned Index = 0;2573  for (const auto *D : Owner->noload_decls()) {2574    const auto *F = dyn_cast<FieldDecl>(D);2575    if (!F)2576      continue;2577 2578    if (F->isAnonymousStructOrUnion()) {2579      if (Context.hasSameType(F->getType(), AnonTy))2580        break;2581      ++Index;2582      continue;2583    }2584 2585    // If the field looks like this:2586    // struct { ... } A;2587    QualType FieldType = F->getType();2588    if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {2589      const RecordDecl *RecDecl = RecType->getDecl();2590      if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {2591        if (Context.hasSameType(FieldType, AnonTy))2592          break;2593        ++Index;2594        continue;2595      }2596    }2597  }2598 2599  return Index;2600}2601 2602unsigned StructuralEquivalenceContext::getApplicableDiagnostic(2603    unsigned ErrorDiagnostic) {2604  if (ErrorOnTagTypeMismatch)2605    return ErrorDiagnostic;2606 2607  switch (ErrorDiagnostic) {2608  case diag::err_odr_variable_type_inconsistent:2609    return diag::warn_odr_variable_type_inconsistent;2610  case diag::err_odr_variable_multiple_def:2611    return diag::warn_odr_variable_multiple_def;2612  case diag::err_odr_function_type_inconsistent:2613    return diag::warn_odr_function_type_inconsistent;2614  case diag::err_odr_tag_type_inconsistent:2615    return diag::warn_odr_tag_type_inconsistent;2616  case diag::err_odr_field_type_inconsistent:2617    return diag::warn_odr_field_type_inconsistent;2618  case diag::err_odr_ivar_type_inconsistent:2619    return diag::warn_odr_ivar_type_inconsistent;2620  case diag::err_odr_objc_superclass_inconsistent:2621    return diag::warn_odr_objc_superclass_inconsistent;2622  case diag::err_odr_objc_method_result_type_inconsistent:2623    return diag::warn_odr_objc_method_result_type_inconsistent;2624  case diag::err_odr_objc_method_num_params_inconsistent:2625    return diag::warn_odr_objc_method_num_params_inconsistent;2626  case diag::err_odr_objc_method_param_type_inconsistent:2627    return diag::warn_odr_objc_method_param_type_inconsistent;2628  case diag::err_odr_objc_method_variadic_inconsistent:2629    return diag::warn_odr_objc_method_variadic_inconsistent;2630  case diag::err_odr_objc_property_type_inconsistent:2631    return diag::warn_odr_objc_property_type_inconsistent;2632  case diag::err_odr_objc_property_impl_kind_inconsistent:2633    return diag::warn_odr_objc_property_impl_kind_inconsistent;2634  case diag::err_odr_objc_synthesize_ivar_inconsistent:2635    return diag::warn_odr_objc_synthesize_ivar_inconsistent;2636  case diag::err_odr_different_num_template_parameters:2637    return diag::warn_odr_different_num_template_parameters;2638  case diag::err_odr_different_template_parameter_kind:2639    return diag::warn_odr_different_template_parameter_kind;2640  case diag::err_odr_parameter_pack_non_pack:2641    return diag::warn_odr_parameter_pack_non_pack;2642  case diag::err_odr_non_type_parameter_type_inconsistent:2643    return diag::warn_odr_non_type_parameter_type_inconsistent;2644  }2645  llvm_unreachable("Diagnostic kind not handled in preceding switch");2646}2647 2648bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {2649 2650  // Ensure that the implementation functions (all static functions in this TU)2651  // never call the public ASTStructuralEquivalence::IsEquivalent() functions,2652  // because that will wreak havoc the internal state (DeclsToCheck and2653  // VisitedDecls members) and can cause faulty behaviour.2654  // In other words: Do not start a graph search from a new node with the2655  // internal data of another search in progress.2656  // FIXME: Better encapsulation and separation of internal and public2657  // functionality.2658  assert(DeclsToCheck.empty());2659  assert(VisitedDecls.empty());2660 2661  if (!::IsStructurallyEquivalent(*this, D1, D2))2662    return false;2663 2664  return !Finish();2665}2666 2667bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {2668  assert(DeclsToCheck.empty());2669  assert(VisitedDecls.empty());2670  if (!::IsStructurallyEquivalent(*this, T1, T2))2671    return false;2672 2673  return !Finish();2674}2675 2676bool StructuralEquivalenceContext::IsEquivalent(Stmt *S1, Stmt *S2) {2677  assert(DeclsToCheck.empty());2678  assert(VisitedDecls.empty());2679  if (!::IsStructurallyEquivalent(*this, S1, S2))2680    return false;2681 2682  return !Finish();2683}2684 2685bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {2686  // Check for equivalent described template.2687  TemplateDecl *Template1 = D1->getDescribedTemplate();2688  TemplateDecl *Template2 = D2->getDescribedTemplate();2689  if ((Template1 != nullptr) != (Template2 != nullptr))2690    return false;2691  if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))2692    return false;2693 2694  // FIXME: Move check for identifier names into this function.2695 2696  return true;2697}2698 2699bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(2700    Decl *D1, Decl *D2) {2701 2702  // Kind mismatch.2703  if (D1->getKind() != D2->getKind())2704    return false;2705 2706  // Cast the Decls to their actual subclass so that the right overload of2707  // IsStructurallyEquivalent is called.2708  switch (D1->getKind()) {2709#define ABSTRACT_DECL(DECL)2710#define DECL(DERIVED, BASE)                                                    \2711  case Decl::Kind::DERIVED:                                                    \2712    return ::IsStructurallyEquivalent(*this, static_cast<DERIVED##Decl *>(D1), \2713                                      static_cast<DERIVED##Decl *>(D2));2714#include "clang/AST/DeclNodes.inc"2715  }2716  return true;2717}2718 2719bool StructuralEquivalenceContext::Finish() {2720  while (!DeclsToCheck.empty()) {2721    // Check the next declaration.2722    std::pair<Decl *, Decl *> P = DeclsToCheck.front();2723    DeclsToCheck.pop();2724 2725    Decl *D1 = P.first;2726    Decl *D2 = P.second;2727 2728    bool Equivalent =2729        CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);2730 2731    if (!Equivalent) {2732      // Note that these two declarations are not equivalent (and we already2733      // know about it).2734      NonEquivalentDecls.insert(2735          std::make_tuple(D1, D2, IgnoreTemplateParmDepth));2736 2737      return true;2738    }2739  }2740 2741  return false;2742}2743