ASTStructuralEquivalence.cpp | Explore in Territory

//===- ASTStructuralEquivalence.cpp ---------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
//  This file implement StructuralEquivalenceContext class and helper functions
//  for layout matching.
//
// The structural equivalence check could have been implemented as a parallel
// BFS on a pair of graphs.  That must have been the original approach at the
// beginning.
// Let's consider this simple BFS algorithm from the `s` source:
// ```
// void bfs(Graph G, int s)
// {
//   Queue<Integer> queue = new Queue<Integer>();
//   marked[s] = true; // Mark the source
//   queue.enqueue(s); // and put it on the queue.
//   while (!q.isEmpty()) {
//     int v = queue.dequeue(); // Remove next vertex from the queue.
//     for (int w : G.adj(v))
//       if (!marked[w]) // For every unmarked adjacent vertex,
//       {
//         marked[w] = true;
//         queue.enqueue(w);
//       }
//   }
// }
// ```
// Indeed, it has it's queue, which holds pairs of nodes, one from each graph,
// this is the `DeclsToCheck` member. `VisitedDecls` plays the role of the
// marking (`marked`) functionality above, we use it to check whether we've
// already seen a pair of nodes.
//
// We put in the elements into the queue only in the toplevel decl check
// function:
// ```
// static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
//                                      Decl *D1, Decl *D2);
// ```
// The `while` loop where we iterate over the children is implemented in
// `Finish()`.  And `Finish` is called only from the two **member** functions
// which check the equivalency of two Decls or two Types. ASTImporter (and
// other clients) call only these functions.
//
// The `static` implementation functions are called from `Finish`, these push
// the children nodes to the queue via `static bool
// IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1,
// Decl *D2)`.  So far so good, this is almost like the BFS.  However, if we
// let a static implementation function to call `Finish` via another **member**
// function that means we end up with two nested while loops each of them
// working on the same queue. This is wrong and nobody can reason about it's
// doing. Thus, static implementation functions must not call the **member**
// functions.
//
//===----------------------------------------------------------------------===//

#include "clang/AST/ASTStructuralEquivalence.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/ASTDiagnostic.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclBase.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclFriend.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/DeclOpenMP.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/ExprConcepts.h"
#include "clang/AST/ExprObjC.h"
#include "clang/AST/ExprOpenMP.h"
#include "clang/AST/NestedNameSpecifier.h"
#include "clang/AST/StmtObjC.h"
#include "clang/AST/StmtOpenACC.h"
#include "clang/AST/StmtOpenMP.h"
#include "clang/AST/TemplateBase.h"
#include "clang/AST/TemplateName.h"
#include "clang/AST/Type.h"
#include "clang/Basic/ExceptionSpecificationType.h"
#include "clang/Basic/IdentifierTable.h"
#include "clang/Basic/LLVM.h"
#include "clang/Basic/SourceLocation.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/APSInt.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ErrorHandling.h"
#include <cassert>
#include <optional>
#include <utility>

usingnamespaceclang;

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     QualType T1, QualType T2);
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     Decl *D1, Decl *D2);
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const Stmt *S1, const Stmt *S2);
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const TemplateArgument &Arg1,
                                     const TemplateArgument &Arg2);
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const TemplateArgumentLoc &Arg1,
                                     const TemplateArgumentLoc &Arg2);
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     NestedNameSpecifier *NNS1,
                                     NestedNameSpecifier *NNS2);
static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
                                     const IdentifierInfo *Name2);

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const DeclarationName Name1,
                                     const DeclarationName Name2) { … }

namespace {
/// Encapsulates Stmt comparison logic.
class StmtComparer { … };
} // namespace

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const UnaryOperator *E1,
                                     const CXXOperatorCallExpr *E2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const CXXOperatorCallExpr *E1,
                                     const UnaryOperator *E2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const BinaryOperator *E1,
                                     const CXXOperatorCallExpr *E2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const CXXOperatorCallExpr *E1,
                                     const BinaryOperator *E2) { … }

/// Determine structural equivalence of two statements.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const Stmt *S1, const Stmt *S2) { … }

/// Determine whether two identifiers are equivalent.
static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
                                     const IdentifierInfo *Name2) { … }

/// Determine whether two nested-name-specifiers are equivalent.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     NestedNameSpecifier *NNS1,
                                     NestedNameSpecifier *NNS2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const TemplateName &N1,
                                     const TemplateName &N2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     ArrayRef<TemplateArgument> Args1,
                                     ArrayRef<TemplateArgument> Args2);

/// Determine whether two template arguments are equivalent.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const TemplateArgument &Arg1,
                                     const TemplateArgument &Arg2) { … }

/// Determine structural equivalence of two template argument lists.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     ArrayRef<TemplateArgument> Args1,
                                     ArrayRef<TemplateArgument> Args2) { … }

/// Determine whether two template argument locations are equivalent.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     const TemplateArgumentLoc &Arg1,
                                     const TemplateArgumentLoc &Arg2) { … }

/// Determine structural equivalence for the common part of array
/// types.
static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                          const ArrayType *Array1,
                                          const ArrayType *Array2) { … }

/// Determine structural equivalence based on the ExtInfo of functions. This
/// is inspired by ASTContext::mergeFunctionTypes(), we compare calling
/// conventions bits but must not compare some other bits.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     FunctionType::ExtInfo EI1,
                                     FunctionType::ExtInfo EI2) { … }

/// Check the equivalence of exception specifications.
static bool IsEquivalentExceptionSpec(StructuralEquivalenceContext &Context,
                                      const FunctionProtoType *Proto1,
                                      const FunctionProtoType *Proto2) { … }

// Determine structural equivalence of two instances of
// HLSLAttributedResourceType::Attributes
static bool
IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                         const HLSLAttributedResourceType::Attributes &Attrs1,
                         const HLSLAttributedResourceType::Attributes &Attrs2) { … }

/// Determine structural equivalence of two types.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     QualType T1, QualType T2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     VarDecl *D1, VarDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     FieldDecl *Field1, FieldDecl *Field2,
                                     QualType Owner2Type) { … }

/// Determine structural equivalence of two fields.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     FieldDecl *Field1, FieldDecl *Field2) { … }

/// Determine structural equivalence of two methods.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     CXXMethodDecl *Method1,
                                     CXXMethodDecl *Method2) { … }

/// Determine structural equivalence of two lambda classes.
static bool
IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
                                CXXRecordDecl *D1, CXXRecordDecl *D2) { … }

/// Determine if context of a class is equivalent.
static bool
IsRecordContextStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                      RecordDecl *D1, RecordDecl *D2) { … }

static bool NameIsStructurallyEquivalent(const TagDecl &D1, const TagDecl &D2) { … }

/// Determine structural equivalence of two records.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     RecordDecl *D1, RecordDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     EnumConstantDecl *D1,
                                     EnumConstantDecl *D2) { … }

/// Determine structural equivalence of two enums.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     EnumDecl *D1, EnumDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     TemplateParameterList *Params1,
                                     TemplateParameterList *Params2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     TemplateTypeParmDecl *D1,
                                     TemplateTypeParmDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     NonTypeTemplateParmDecl *D1,
                                     NonTypeTemplateParmDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     TemplateTemplateParmDecl *D1,
                                     TemplateTemplateParmDecl *D2) { … }

static bool IsTemplateDeclCommonStructurallyEquivalent(
    StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     ClassTemplateDecl *D1,
                                     ClassTemplateDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     FunctionTemplateDecl *D1,
                                     FunctionTemplateDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     TypeAliasTemplateDecl *D1,
                                     TypeAliasTemplateDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     ConceptDecl *D1,
                                     ConceptDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     FriendDecl *D1, FriendDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     TypedefNameDecl *D1, TypedefNameDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     FunctionDecl *D1, FunctionDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     ObjCIvarDecl *D1, ObjCIvarDecl *D2,
                                     QualType Owner2Type) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     ObjCIvarDecl *D1, ObjCIvarDecl *D2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     ObjCMethodDecl *Method1,
                                     ObjCMethodDecl *Method2) { … }

static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     ObjCCategoryDecl *D1,
                                     ObjCCategoryDecl *D2) { … }

/// Determine structural equivalence of two declarations.
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
                                     Decl *D1, Decl *D2) { … }

DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
                                                      unsigned DiagID) { … }

DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
                                                      unsigned DiagID) { … }

std::optional<unsigned>
StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) { … }

unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
    unsigned ErrorDiagnostic) { … }

bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) { … }

bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) { … }

bool StructuralEquivalenceContext::IsEquivalent(Stmt *S1, Stmt *S2) { … }

bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) { … }

bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
    Decl *D1, Decl *D2) { … }

bool StructuralEquivalenceContext::Finish() { … }
llvm/clang/lib/AST/ASTStructuralEquivalence.cpp
