[clang][ssaf] Introduce entity abstraction for SSAF (#169131)
Add core abstractions for identifying program entities across
compilation and link unit boundaries in the Scalable Static Analysis
Framework (SSAF).
Introduces three key components:
- BuildNamespace: Represents build artifacts (compilation units, link
units)
- EntityName: Globally unique entity identifiers across compilation
boundaries
- AST mapping: Functions to map Clang AST declarations to EntityNames
Entity identification uses Unified Symbol Resolution (USR) as the
underlying mechanism, with extensions for sub-entities (parameters,
return values) via suffixes. The abstraction allows whole-program
analysis by providing stable identifiers that persist across separately
compiled translation units.
diff --git a/clang/include/clang/Analysis/Scalable/ASTEntityMapping.h b/clang/include/clang/Analysis/Scalable/ASTEntityMapping.h
new file mode 100644
index 0000000..0e5fc20
--- /dev/null
+++ b/clang/include/clang/Analysis/Scalable/ASTEntityMapping.h
@@ -0,0 +1,47 @@
+//===- ASTEntityMapping.h - AST to SSAF Entity mapping ----------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_SCALABLE_ASTENTITYMAPPING_H
+#define LLVM_CLANG_ANALYSIS_SCALABLE_ASTENTITYMAPPING_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/Scalable/Model/EntityName.h"
+#include "llvm/ADT/StringRef.h"
+#include <optional>
+
+namespace clang::ssaf {
+
+/// Maps a declaration to an EntityName.
+///
+/// Supported declaration types for entity mapping:
+/// - Functions and methods
+/// - Global Variables
+/// - Function parameters
+/// - Struct/class/union type definitions
+/// - Struct/class/union fields
+///
+/// Implicit declarations and compiler builtins are not mapped.
+///
+/// \param D The declaration to map. Must not be null.
+///
+/// \return An EntityName if the declaration can be mapped, std::nullopt
+/// otherwise.
+std::optional<EntityName> getEntityName(const Decl *D);
+
+/// Maps return entity of a function to an EntityName.
+/// The returned name uniquely identifies the return value of function \param
+/// FD.
+///
+/// \param FD The function declaration. Must not be null.
+///
+/// \return An EntityName for the function's return entity.
+std::optional<EntityName> getEntityNameForReturn(const FunctionDecl *FD);
+
+} // namespace clang::ssaf
+
+#endif // LLVM_CLANG_ANALYSIS_SCALABLE_ASTENTITYMAPPING_H
diff --git a/clang/include/clang/Analysis/Scalable/Model/BuildNamespace.h b/clang/include/clang/Analysis/Scalable/Model/BuildNamespace.h
new file mode 100644
index 0000000..5ca26df
--- /dev/null
+++ b/clang/include/clang/Analysis/Scalable/Model/BuildNamespace.h
@@ -0,0 +1,123 @@
+//===- BuildNamespace.h -----------------------------------------*- C++ -*-===//
+//
+// 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 defines BuildNamespace and NestedBuildNamespace classes that
+// represent build namespaces in the Scalable Static Analysis Framework.
+//
+// Build namespaces provide an abstraction for grouping program entities (such
+// as those in a shared library or compilation unit) to enable analysis of
+// software projects constructed from individual components.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_BUILDNAMESPACE_H
+#define LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_BUILDNAMESPACE_H
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include <optional>
+#include <string>
+#include <vector>
+
+namespace clang::ssaf {
+
+enum class BuildNamespaceKind : unsigned short { CompilationUnit, LinkUnit };
+
+llvm::StringRef toString(BuildNamespaceKind BNK);
+
+std::optional<BuildNamespaceKind> parseBuildNamespaceKind(llvm::StringRef Str);
+
+/// Represents a single namespace in the build process.
+///
+/// A BuildNamespace groups program entities, such as those belonging to a
+/// compilation unit or link unit (e.g., a shared library). Each namespace has a
+/// kind (CompilationUnit or LinkUnit) and a unique identifier name within that
+/// kind.
+///
+/// BuildNamespaces can be composed into NestedBuildNamespace to represent
+/// hierarchical namespace structures that model how software is constructed
+/// from its components.
+class BuildNamespace {
+ BuildNamespaceKind Kind;
+ std::string Name;
+
+ auto asTuple() const { return std::tie(Kind, Name); }
+
+public:
+ BuildNamespace(BuildNamespaceKind Kind, llvm::StringRef Name)
+ : Kind(Kind), Name(Name.str()) {}
+
+ /// Creates a BuildNamespace representing a compilation unit.
+ ///
+ /// \param CompilationId The unique identifier for the compilation unit.
+ /// \returns A BuildNamespace with CompilationUnit kind.
+ static BuildNamespace makeCompilationUnit(llvm::StringRef CompilationId);
+
+ bool operator==(const BuildNamespace &Other) const;
+ bool operator!=(const BuildNamespace &Other) const;
+ bool operator<(const BuildNamespace &Other) const;
+
+ friend class SerializationFormat;
+};
+
+/// Represents a hierarchical sequence of build namespaces.
+///
+/// A NestedBuildNamespace captures namespace qualification for program entities
+/// by maintaining an ordered sequence of BuildNamespace steps. This models how
+/// entities are organized through multiple steps of the build process, such as
+/// first being part of a compilation unit, then incorporated into a link unit.
+///
+/// For example, an entity might be qualified by a compilation unit namespace
+/// followed by a shared library namespace.
+class NestedBuildNamespace {
+ friend class SerializationFormat;
+
+ std::vector<BuildNamespace> Namespaces;
+
+public:
+ NestedBuildNamespace() = default;
+
+ explicit NestedBuildNamespace(const std::vector<BuildNamespace> &Namespaces)
+ : Namespaces(Namespaces) {}
+
+ explicit NestedBuildNamespace(const BuildNamespace &N) {
+ Namespaces.push_back(N);
+ }
+
+ /// Creates a NestedBuildNamespace representing a compilation unit.
+ ///
+ /// \param CompilationId The unique identifier for the compilation unit.
+ /// \returns A NestedBuildNamespace containing a single CompilationUnit
+ /// BuildNamespace.
+ static NestedBuildNamespace
+ makeCompilationUnit(llvm::StringRef CompilationId);
+
+ /// Creates a new NestedBuildNamespace by appending additional namespace.
+ ///
+ /// \param Namespace The namespace to append.
+ NestedBuildNamespace makeQualified(NestedBuildNamespace Namespace) const {
+ auto Copy = *this;
+ Copy.Namespaces.reserve(Copy.Namespaces.size() +
+ Namespace.Namespaces.size());
+ llvm::append_range(Copy.Namespaces, Namespace.Namespaces);
+ return Copy;
+ }
+
+ bool empty() const;
+
+ bool operator==(const NestedBuildNamespace &Other) const;
+ bool operator!=(const NestedBuildNamespace &Other) const;
+ bool operator<(const NestedBuildNamespace &Other) const;
+
+ friend class JSONWriter;
+ friend class LinkUnitResolution;
+};
+
+} // namespace clang::ssaf
+
+#endif // LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_BUILDNAMESPACE_H
diff --git a/clang/include/clang/Analysis/Scalable/Model/EntityName.h b/clang/include/clang/Analysis/Scalable/Model/EntityName.h
new file mode 100644
index 0000000..23890ab
--- /dev/null
+++ b/clang/include/clang/Analysis/Scalable/Model/EntityName.h
@@ -0,0 +1,56 @@
+//===- EntityName.h ---------------------------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITYNAME_H
+#define LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITYNAME_H
+
+#include "clang/Analysis/Scalable/Model/BuildNamespace.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringRef.h"
+#include <string>
+
+namespace clang::ssaf {
+/// Uniquely identifies an entity in a program.
+///
+/// EntityName provides a globally unique identifier for program entities that
+/// remains stable across compilation boundaries. This enables whole-program
+/// analysis to track and relate entities across separately compiled translation
+/// units.
+///
+/// Client code should not make assumptions about the implementation details,
+/// such as USRs.
+class EntityName {
+ std::string USR;
+ llvm::SmallString<16> Suffix;
+ NestedBuildNamespace Namespace;
+
+ auto asTuple() const { return std::tie(USR, Suffix, Namespace); }
+
+public:
+ /// Client code should not use this constructor directly.
+ /// Use getEntityName and other functions in ASTEntityMapping.h to get
+ /// entity names.
+ EntityName(llvm::StringRef USR, llvm::StringRef Suffix,
+ NestedBuildNamespace Namespace);
+
+ bool operator==(const EntityName &Other) const;
+ bool operator!=(const EntityName &Other) const;
+ bool operator<(const EntityName &Other) const;
+
+ /// Creates a new EntityName with additional build namespace qualification.
+ ///
+ /// \param Namespace The namespace steps to append to this entity's namespace.
+ EntityName makeQualified(NestedBuildNamespace Namespace) const;
+
+ friend class LinkUnitResolution;
+ friend class SerializationFormat;
+};
+
+} // namespace clang::ssaf
+
+#endif // LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITYNAME_H
diff --git a/clang/lib/Analysis/CMakeLists.txt b/clang/lib/Analysis/CMakeLists.txt
index 1dbd415..99a2ec6 100644
--- a/clang/lib/Analysis/CMakeLists.txt
+++ b/clang/lib/Analysis/CMakeLists.txt
@@ -50,3 +50,4 @@
add_subdirectory(plugins)
add_subdirectory(FlowSensitive)
add_subdirectory(LifetimeSafety)
+add_subdirectory(Scalable)
diff --git a/clang/lib/Analysis/Scalable/ASTEntityMapping.cpp b/clang/lib/Analysis/Scalable/ASTEntityMapping.cpp
new file mode 100644
index 0000000..0a25e75
--- /dev/null
+++ b/clang/lib/Analysis/Scalable/ASTEntityMapping.cpp
@@ -0,0 +1,83 @@
+//===- ASTMapping.cpp - AST to SSAF Entity mapping --------------*- C++ -*-===//
+//
+// 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 implements utilities for mapping AST declarations to SSAF entities.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Scalable/ASTEntityMapping.h"
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/Scalable/Model/BuildNamespace.h"
+#include "clang/Index/USRGeneration.h"
+#include "llvm/ADT/SmallString.h"
+
+namespace clang::ssaf {
+
+std::optional<EntityName> getEntityName(const Decl *D) {
+ if (!D)
+ return std::nullopt;
+
+ if (D->isImplicit())
+ return std::nullopt;
+
+ if (isa<FunctionDecl>(D) && cast<FunctionDecl>(D)->getBuiltinID())
+ return std::nullopt;
+
+ if (!isa<FunctionDecl, ParmVarDecl, VarDecl, FieldDecl, RecordDecl>(D))
+ return std::nullopt;
+
+ llvm::SmallString<16> Suffix;
+ const Decl *USRDecl = D;
+
+ // For parameters, use the parent function's USR with parameter index as
+ // suffix
+ if (const auto *PVD = dyn_cast<ParmVarDecl>(D)) {
+ const auto *FD =
+ dyn_cast_or_null<FunctionDecl>(PVD->getParentFunctionOrMethod());
+ if (!FD)
+ return std::nullopt;
+ USRDecl = FD;
+
+ const auto ParamIdx = PVD->getFunctionScopeIndex();
+ llvm::raw_svector_ostream OS(Suffix);
+ // Parameter uses function's USR with 1-based index as suffix
+ OS << (ParamIdx + 1);
+ }
+
+ llvm::SmallString<128> USRBuf;
+ if (clang::index::generateUSRForDecl(USRDecl, USRBuf))
+ return std::nullopt;
+
+ if (USRBuf.empty())
+ return std::nullopt;
+
+ return EntityName(USRBuf.str(), Suffix, {});
+}
+
+std::optional<EntityName> getEntityNameForReturn(const FunctionDecl *FD) {
+ if (!FD)
+ return std::nullopt;
+
+ if (FD->isImplicit())
+ return std::nullopt;
+
+ if (FD->getBuiltinID())
+ return std::nullopt;
+
+ llvm::SmallString<128> USRBuf;
+ if (clang::index::generateUSRForDecl(FD, USRBuf)) {
+ return std::nullopt;
+ }
+
+ if (USRBuf.empty())
+ return std::nullopt;
+
+ return EntityName(USRBuf.str(), /*Suffix=*/"0", /*Namespace=*/{});
+}
+
+} // namespace clang::ssaf
diff --git a/clang/lib/Analysis/Scalable/CMakeLists.txt b/clang/lib/Analysis/Scalable/CMakeLists.txt
new file mode 100644
index 0000000..ea4693f
--- /dev/null
+++ b/clang/lib/Analysis/Scalable/CMakeLists.txt
@@ -0,0 +1,19 @@
+set(LLVM_LINK_COMPONENTS
+ Support
+ )
+
+add_clang_library(clangAnalysisScalable
+ ASTEntityMapping.cpp
+ Model/BuildNamespace.cpp
+ Model/EntityName.cpp
+
+ LINK_LIBS
+ clangAST
+ clangASTMatchers
+ clangBasic
+ clangIndex
+ clangLex
+ clangFrontend
+
+ DEPENDS
+ )
diff --git a/clang/lib/Analysis/Scalable/Model/BuildNamespace.cpp b/clang/lib/Analysis/Scalable/Model/BuildNamespace.cpp
new file mode 100644
index 0000000..040cfe9
--- /dev/null
+++ b/clang/lib/Analysis/Scalable/Model/BuildNamespace.cpp
@@ -0,0 +1,73 @@
+//===- BuildNamespace.cpp ---------------------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Scalable/Model/BuildNamespace.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <tuple>
+
+namespace clang::ssaf {
+
+llvm::StringRef toString(BuildNamespaceKind BNK) {
+ switch (BNK) {
+ case BuildNamespaceKind::CompilationUnit:
+ return "compilation_unit";
+ case BuildNamespaceKind::LinkUnit:
+ return "link_unit";
+ }
+ llvm_unreachable("Unknown BuildNamespaceKind");
+}
+
+std::optional<BuildNamespaceKind> parseBuildNamespaceKind(llvm::StringRef Str) {
+ if (Str == "compilation_unit")
+ return BuildNamespaceKind::CompilationUnit;
+ if (Str == "link_unit")
+ return BuildNamespaceKind::LinkUnit;
+ return std::nullopt;
+}
+
+BuildNamespace
+BuildNamespace::makeCompilationUnit(llvm::StringRef CompilationId) {
+ return BuildNamespace{BuildNamespaceKind::CompilationUnit,
+ CompilationId.str()};
+}
+
+bool BuildNamespace::operator==(const BuildNamespace &Other) const {
+ return asTuple() == Other.asTuple();
+}
+
+bool BuildNamespace::operator!=(const BuildNamespace &Other) const {
+ return !(*this == Other);
+}
+
+bool BuildNamespace::operator<(const BuildNamespace &Other) const {
+ return asTuple() < Other.asTuple();
+}
+
+NestedBuildNamespace
+NestedBuildNamespace::makeCompilationUnit(llvm::StringRef CompilationId) {
+ NestedBuildNamespace Result;
+ Result.Namespaces.push_back(
+ BuildNamespace::makeCompilationUnit(CompilationId));
+ return Result;
+}
+
+bool NestedBuildNamespace::empty() const { return Namespaces.empty(); }
+
+bool NestedBuildNamespace::operator==(const NestedBuildNamespace &Other) const {
+ return Namespaces == Other.Namespaces;
+}
+
+bool NestedBuildNamespace::operator!=(const NestedBuildNamespace &Other) const {
+ return !(*this == Other);
+}
+
+bool NestedBuildNamespace::operator<(const NestedBuildNamespace &Other) const {
+ return Namespaces < Other.Namespaces;
+}
+
+} // namespace clang::ssaf
diff --git a/clang/lib/Analysis/Scalable/Model/EntityName.cpp b/clang/lib/Analysis/Scalable/Model/EntityName.cpp
new file mode 100644
index 0000000..7e66476
--- /dev/null
+++ b/clang/lib/Analysis/Scalable/Model/EntityName.cpp
@@ -0,0 +1,36 @@
+//===- EntityName.cpp -------------------------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Scalable/Model/EntityName.h"
+
+namespace clang::ssaf {
+
+EntityName::EntityName(llvm::StringRef USR, llvm::StringRef Suffix,
+ NestedBuildNamespace Namespace)
+ : USR(USR.str()), Suffix(Suffix), Namespace(std::move(Namespace)) {}
+
+bool EntityName::operator==(const EntityName &Other) const {
+ return asTuple() == Other.asTuple();
+}
+
+bool EntityName::operator!=(const EntityName &Other) const {
+ return !(*this == Other);
+}
+
+bool EntityName::operator<(const EntityName &Other) const {
+ return asTuple() < Other.asTuple();
+}
+
+EntityName EntityName::makeQualified(NestedBuildNamespace Namespace) const {
+ auto Copy = *this;
+ Copy.Namespace = Copy.Namespace.makeQualified(Namespace);
+
+ return Copy;
+}
+
+} // namespace clang::ssaf
diff --git a/clang/unittests/Analysis/CMakeLists.txt b/clang/unittests/Analysis/CMakeLists.txt
index e0acf43..97e768b 100644
--- a/clang/unittests/Analysis/CMakeLists.txt
+++ b/clang/unittests/Analysis/CMakeLists.txt
@@ -26,3 +26,4 @@
)
add_subdirectory(FlowSensitive)
+add_subdirectory(Scalable)
diff --git a/clang/unittests/Analysis/Scalable/ASTEntityMappingTest.cpp b/clang/unittests/Analysis/Scalable/ASTEntityMappingTest.cpp
new file mode 100644
index 0000000..dd41864
--- /dev/null
+++ b/clang/unittests/Analysis/Scalable/ASTEntityMappingTest.cpp
@@ -0,0 +1,352 @@
+//===- unittests/Analysis/Scalable/ASTEntityMappingTest.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Scalable/ASTEntityMapping.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang::ssaf {
+namespace {
+
+// Helper function to find a declaration by name
+template <typename DeclType>
+const DeclType *findDecl(ASTContext &Ctx, StringRef Name) {
+ auto Matcher = namedDecl(hasName(Name)).bind("decl");
+ auto Matches = match(Matcher, Ctx);
+ if (Matches.empty())
+ return nullptr;
+ if (auto Result = Matches[0].getNodeAs<DeclType>("decl"))
+ return dyn_cast<DeclType>(Result->getCanonicalDecl());
+ return nullptr;
+}
+
+TEST(ASTEntityMappingTest, FunctionDecl) {
+ auto AST = tooling::buildASTFromCode(R"cpp(void foo() {})cpp");
+ auto &Ctx = AST->getASTContext();
+
+ const auto *FD = findDecl<FunctionDecl>(Ctx, "foo");
+ ASSERT_NE(FD, nullptr);
+
+ auto EntityName = getEntityName(FD);
+ EXPECT_TRUE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, VarDecl) {
+ auto AST = tooling::buildASTFromCode(R"cpp(int x = 42;)cpp");
+ auto &Ctx = AST->getASTContext();
+
+ const auto *VD = findDecl<VarDecl>(Ctx, "x");
+ ASSERT_NE(VD, nullptr);
+
+ auto EntityName = getEntityName(VD);
+ EXPECT_TRUE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, ParmVarDecl) {
+ auto AST = tooling::buildASTFromCode(R"cpp(void foo(int x) {})cpp");
+ auto &Ctx = AST->getASTContext();
+
+ const auto *FD = findDecl<FunctionDecl>(Ctx, "foo");
+ ASSERT_NE(FD, nullptr);
+ ASSERT_EQ(FD->param_size(), 1u);
+
+ const auto *PVD = FD->getParamDecl(0);
+ ASSERT_NE(PVD, nullptr);
+
+ auto EntityName = getEntityName(PVD);
+ EXPECT_TRUE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, RecordDecl) {
+ auto AST = tooling::buildASTFromCode(R"cpp(struct S {};)cpp");
+ auto &Ctx = AST->getASTContext();
+
+ const auto *RD = findDecl<RecordDecl>(Ctx, "S");
+ ASSERT_NE(RD, nullptr);
+
+ auto EntityName = getEntityName(RD);
+ EXPECT_TRUE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, FieldDecl) {
+ auto AST = tooling::buildASTFromCode(R"cpp(struct S { int field; };)cpp");
+ auto &Ctx = AST->getASTContext();
+
+ const auto *FD = findDecl<FieldDecl>(Ctx, "field");
+ ASSERT_NE(FD, nullptr);
+
+ auto EntityName = getEntityName(FD);
+ EXPECT_TRUE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, NullDecl) {
+ auto EntityName = getEntityName(nullptr);
+ EXPECT_FALSE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, ImplicitDeclLambda) {
+ auto AST = tooling::buildASTFromCode(
+ R"cpp(
+ auto L = [](){};
+ )cpp",
+ "test.cpp", std::make_shared<PCHContainerOperations>());
+ auto &Ctx = AST->getASTContext();
+
+ auto Matcher = cxxRecordDecl(isImplicit()).bind("decl");
+ auto Matches = match(Matcher, Ctx);
+ ASSERT_GT(Matches.size(), 0u);
+
+ const auto *ImplCXXRD = Matches[0].getNodeAs<CXXRecordDecl>("decl");
+ ASSERT_NE(ImplCXXRD, nullptr);
+
+ auto EntityName = getEntityName(ImplCXXRD);
+ EXPECT_FALSE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, BuiltinFunction) {
+ auto AST = tooling::buildASTFromCode(R"cpp(
+ void test() {
+ __builtin_memcpy(0, 0, 0);
+ }
+ )cpp");
+ auto &Ctx = AST->getASTContext();
+
+ // Find the builtin call
+ auto Matcher = callExpr().bind("call");
+ auto Matches = match(Matcher, Ctx);
+ ASSERT_EQ(Matches.size(), 1ul);
+
+ const auto *CE = Matches[0].getNodeAs<CallExpr>("call");
+ ASSERT_NE(CE, nullptr);
+
+ const auto *Callee = CE->getDirectCallee();
+ ASSERT_NE(Callee, nullptr);
+ ASSERT_NE(Callee->getBuiltinID(), 0u /* not a built-in */);
+
+ auto EntityName = getEntityName(Callee);
+ EXPECT_FALSE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, UnsupportedDecl) {
+ auto AST = tooling::buildASTFromCode(R"cpp(namespace N {})cpp");
+ auto &Ctx = AST->getASTContext();
+
+ const auto *ND = findDecl<NamespaceDecl>(Ctx, "N");
+ ASSERT_NE(ND, nullptr);
+
+ auto EntityName = getEntityName(ND);
+ EXPECT_FALSE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, FunctionReturn) {
+ auto AST = tooling::buildASTFromCode(R"cpp(int foo() { return 42; })cpp");
+ auto &Ctx = AST->getASTContext();
+
+ const auto *FD = findDecl<FunctionDecl>(Ctx, "foo");
+ ASSERT_NE(FD, nullptr);
+
+ auto EntityName = getEntityNameForReturn(FD);
+ EXPECT_TRUE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, FunctionReturnNull) {
+ auto EntityName = getEntityNameForReturn(nullptr);
+ EXPECT_FALSE(EntityName.has_value());
+}
+
+TEST(ASTEntityMappingTest, FunctionReturnBuiltin) {
+ auto AST = tooling::buildASTFromCode(R"cpp(
+ void test() {
+ __builtin_memcpy(0, 0, 0);
+ }
+ )cpp");
+ auto &Ctx = AST->getASTContext();
+
+ // Find the builtin call
+ auto Matcher = callExpr().bind("call");
+ auto Matches = match(Matcher, Ctx);
+ ASSERT_FALSE(Matches.empty());
+
+ const auto *CE = Matches[0].getNodeAs<CallExpr>("call");
+ ASSERT_NE(CE, nullptr);
+
+ const auto *Callee = CE->getDirectCallee();
+ if (Callee && Callee->getBuiltinID()) {
+ auto EntityName = getEntityNameForReturn(Callee);
+ EXPECT_FALSE(EntityName.has_value());
+ }
+}
+
+TEST(ASTEntityMappingTest, DifferentFunctionsDifferentNames) {
+ auto AST = tooling::buildASTFromCode(R"cpp(
+ void foo() {}
+ void bar() {}
+ )cpp");
+ auto &Ctx = AST->getASTContext();
+
+ const auto *Foo = findDecl<FunctionDecl>(Ctx, "foo");
+ const auto *Bar = findDecl<FunctionDecl>(Ctx, "bar");
+ ASSERT_NE(Foo, nullptr);
+ ASSERT_NE(Bar, nullptr);
+
+ auto FooName = getEntityName(Foo);
+ auto BarName = getEntityName(Bar);
+ ASSERT_TRUE(FooName.has_value());
+ ASSERT_TRUE(BarName.has_value());
+
+ EXPECT_NE(*FooName, *BarName);
+}
+
+// Redeclaration tests
+
+TEST(ASTEntityMappingTest, FunctionRedeclaration) {
+ auto AST = tooling::buildASTFromCode(R"cpp(
+ void foo();
+ void foo() {}
+ )cpp");
+ auto &Ctx = AST->getASTContext();
+
+ auto Matcher = functionDecl(hasName("foo")).bind("decl");
+ auto Matches = match(Matcher, Ctx);
+ ASSERT_GE(Matches.size(), 2u);
+
+ const auto *FirstDecl = Matches[0].getNodeAs<FunctionDecl>("decl");
+ ASSERT_NE(FirstDecl, nullptr);
+
+ auto FirstName = getEntityName(FirstDecl);
+ ASSERT_TRUE(FirstName.has_value());
+
+ for (size_t I = 1; I < Matches.size(); ++I) {
+ const auto *Decl = Matches[I].getNodeAs<FunctionDecl>("decl");
+ ASSERT_NE(Decl, nullptr);
+
+ auto Name = getEntityName(Decl);
+ ASSERT_TRUE(Name.has_value());
+ EXPECT_EQ(*FirstName, *Name);
+ }
+}
+
+TEST(ASTEntityMappingTest, VarRedeclaration) {
+ auto AST = tooling::buildASTFromCode(R"cpp(
+ extern int x;
+ int x = 42;
+ )cpp");
+ auto &Ctx = AST->getASTContext();
+
+ auto Matcher = varDecl(hasName("x")).bind("decl");
+ auto Matches = match(Matcher, Ctx);
+ ASSERT_EQ(Matches.size(), 2u);
+
+ const auto *FirstDecl = Matches[0].getNodeAs<VarDecl>("decl");
+ ASSERT_NE(FirstDecl, nullptr);
+
+ auto FirstName = getEntityName(FirstDecl);
+ ASSERT_TRUE(FirstName.has_value());
+
+ for (size_t I = 1; I < Matches.size(); ++I) {
+ const auto *Decl = Matches[I].getNodeAs<VarDecl>("decl");
+ ASSERT_NE(Decl, nullptr);
+
+ auto Name = getEntityName(Decl);
+ ASSERT_TRUE(Name.has_value());
+ EXPECT_EQ(*FirstName, *Name);
+ }
+}
+
+TEST(ASTEntityMappingTest, RecordRedeclaration) {
+ auto AST = tooling::buildASTFromCode(R"cpp(
+ struct S;
+ struct S {};
+ )cpp");
+ auto &Ctx = AST->getASTContext();
+
+ auto Matcher = recordDecl(hasName("S"), unless(isImplicit())).bind("decl");
+ auto Matches = match(Matcher, Ctx);
+ ASSERT_GE(Matches.size(), 2u);
+
+ const auto *FirstDecl = Matches[0].getNodeAs<RecordDecl>("decl");
+ ASSERT_NE(FirstDecl, nullptr);
+
+ auto FirstName = getEntityName(FirstDecl);
+ ASSERT_TRUE(FirstName.has_value());
+
+ for (size_t I = 1; I < Matches.size(); ++I) {
+ const auto *Decl = Matches[I].getNodeAs<RecordDecl>("decl");
+ ASSERT_NE(Decl, nullptr);
+
+ auto Name = getEntityName(Decl);
+ ASSERT_TRUE(Name.has_value());
+ EXPECT_EQ(*FirstName, *Name);
+ }
+}
+
+TEST(ASTEntityMappingTest, ParmVarDeclRedeclaration) {
+ auto AST = tooling::buildASTFromCode(R"cpp(
+ void foo(int);
+ void foo(int x);
+ void foo(int y);
+ void foo(int x) {}
+ )cpp");
+ auto &Ctx = AST->getASTContext();
+
+ auto Matcher = functionDecl(hasName("foo")).bind("decl");
+ auto Matches = match(Matcher, Ctx);
+ ASSERT_GE(Matches.size(), 2u);
+
+ const auto *FirstFuncDecl = Matches[0].getNodeAs<FunctionDecl>("decl");
+ ASSERT_NE(FirstFuncDecl, nullptr);
+ ASSERT_GT(FirstFuncDecl->param_size(), 0u);
+
+ auto ParamEName = getEntityName(FirstFuncDecl->getParamDecl(0));
+ ASSERT_TRUE(ParamEName.has_value());
+
+ for (size_t I = 1; I < Matches.size(); ++I) {
+ const auto *FDecl = Matches[I].getNodeAs<FunctionDecl>("decl");
+ ASSERT_NE(FDecl, nullptr);
+ ASSERT_GT(FDecl->param_size(), 0u);
+
+ auto ParamRedeclEName = getEntityName(FDecl->getParamDecl(0));
+ EXPECT_EQ(*ParamEName, *ParamRedeclEName);
+ }
+}
+
+TEST(ASTEntityMappingTest, FunctionReturnRedeclaration) {
+ auto AST = tooling::buildASTFromCode(R"cpp(
+ int foo();
+ int foo() { return 42; }
+ )cpp");
+ auto &Ctx = AST->getASTContext();
+
+ auto Matcher = functionDecl(hasName("foo")).bind("decl");
+ auto Matches = match(Matcher, Ctx);
+ ASSERT_EQ(Matches.size(), 2u);
+
+ const auto *Decl1 = Matches[0].getNodeAs<FunctionDecl>("decl");
+ ASSERT_NE(Decl1, nullptr);
+ auto Name1 = getEntityNameForReturn(Decl1);
+ ASSERT_TRUE(Name1.has_value());
+
+ for (size_t I = 1; I < Matches.size(); ++I) {
+ const auto *FDecl = Matches[I].getNodeAs<FunctionDecl>("decl");
+ ASSERT_NE(FDecl, nullptr);
+
+ auto Name = getEntityNameForReturn(Decl1);
+ ASSERT_TRUE(Name.has_value());
+ EXPECT_EQ(*Name1, *Name);
+ }
+}
+
+} // namespace
+} // namespace clang::ssaf
diff --git a/clang/unittests/Analysis/Scalable/BuildNamespaceTest.cpp b/clang/unittests/Analysis/Scalable/BuildNamespaceTest.cpp
new file mode 100644
index 0000000..80d8a4073
--- /dev/null
+++ b/clang/unittests/Analysis/Scalable/BuildNamespaceTest.cpp
@@ -0,0 +1,97 @@
+//===- unittests/Analysis/Scalable/BuildNamespaceTest.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Scalable/Model/BuildNamespace.h"
+#include "gtest/gtest.h"
+
+namespace clang::ssaf {
+namespace {
+
+TEST(BuildNamespaceTest, Equality) {
+ auto BN1 = BuildNamespace::makeCompilationUnit("test.cpp");
+ auto BN2 = BuildNamespace::makeCompilationUnit("test.cpp");
+ auto BN3 = BuildNamespace::makeCompilationUnit("other.cpp");
+
+ EXPECT_EQ(BN1, BN2);
+ EXPECT_NE(BN1, BN3);
+}
+
+TEST(BuildNamespaceTest, DifferentKinds) {
+ BuildNamespace CU(BuildNamespaceKind::CompilationUnit, "test");
+ BuildNamespace LU(BuildNamespaceKind::LinkUnit, "test");
+
+ EXPECT_NE(CU, LU);
+}
+
+TEST(BuildNamespaceTest, ToStringRoundtripCompilationUnit) {
+ auto Kind = BuildNamespaceKind::CompilationUnit;
+ auto Str = toString(Kind);
+ auto Parsed = parseBuildNamespaceKind(Str);
+
+ ASSERT_TRUE(Parsed.has_value());
+ EXPECT_EQ(Kind, *Parsed);
+}
+
+TEST(BuildNamespaceTest, ToStringRoundtripLinkUnit) {
+ auto Kind = BuildNamespaceKind::LinkUnit;
+ auto Str = toString(Kind);
+ auto Parsed = parseBuildNamespaceKind(Str);
+
+ ASSERT_TRUE(Parsed.has_value());
+ EXPECT_EQ(Kind, *Parsed);
+}
+
+// NestedBuildNamespace Tests
+
+TEST(NestedBuildNamespaceTest, DefaultConstruction) {
+ NestedBuildNamespace NBN;
+ EXPECT_TRUE(NBN.empty());
+}
+
+TEST(NestedBuildNamespaceTest, SingleNamespaceConstruction) {
+ auto BN = BuildNamespace::makeCompilationUnit("test.cpp");
+ NestedBuildNamespace NBN(BN);
+
+ EXPECT_FALSE(NBN.empty());
+}
+
+TEST(NestedBuildNamespaceTest, MakeTU) {
+ auto NBN = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+ EXPECT_FALSE(NBN.empty());
+}
+
+TEST(NestedBuildNamespaceTest, Equality) {
+ auto NBN1 = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+ auto NBN2 = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+ auto NBN3 = NestedBuildNamespace::makeCompilationUnit("other.cpp");
+
+ EXPECT_EQ(NBN1, NBN2);
+ EXPECT_NE(NBN1, NBN3);
+}
+
+TEST(NestedBuildNamespaceTest, MakeQualified) {
+ auto NBN1 = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+ BuildNamespace LinkNS(BuildNamespaceKind::LinkUnit, "app");
+ NestedBuildNamespace NBN2(LinkNS);
+
+ auto Qualified = NBN1.makeQualified(NBN2);
+
+ EXPECT_NE(Qualified, NBN1);
+ EXPECT_NE(Qualified, NBN2);
+}
+
+TEST(NestedBuildNamespaceTest, EmptyQualified) {
+ NestedBuildNamespace Empty;
+ auto NBN = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+
+ auto Qualified = Empty.makeQualified(NBN);
+ EXPECT_EQ(Qualified, NBN);
+}
+
+} // namespace
+} // namespace clang::ssaf
diff --git a/clang/unittests/Analysis/Scalable/CMakeLists.txt b/clang/unittests/Analysis/Scalable/CMakeLists.txt
new file mode 100644
index 0000000..e545e31
--- /dev/null
+++ b/clang/unittests/Analysis/Scalable/CMakeLists.txt
@@ -0,0 +1,18 @@
+add_distinct_clang_unittest(ClangScalableAnalysisFrameworkTests
+ ASTEntityMappingTest.cpp
+ BuildNamespaceTest.cpp
+ EntityNameTest.cpp
+
+ CLANG_LIBS
+ clangAnalysisScalable
+ clangAST
+ clangASTMatchers
+ clangBasic
+ clangSerialization
+ clangTooling
+ )
+
+add_custom_target(ClangScalableAnalysisTests
+ DEPENDS
+ ClangScalableAnalysisFrameworkTests
+ )
diff --git a/clang/unittests/Analysis/Scalable/EntityNameTest.cpp b/clang/unittests/Analysis/Scalable/EntityNameTest.cpp
new file mode 100644
index 0000000..be0c2a9
--- /dev/null
+++ b/clang/unittests/Analysis/Scalable/EntityNameTest.cpp
@@ -0,0 +1,60 @@
+//===- unittests/Analysis/Scalable/EntityNameTest.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Scalable/Model/EntityName.h"
+#include "clang/Analysis/Scalable/Model/BuildNamespace.h"
+#include "gtest/gtest.h"
+
+namespace clang::ssaf {
+namespace {
+
+TEST(EntityNameTest, Equality) {
+ auto NBN1 = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+ auto NBN2 = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+
+ EntityName EN1("c:@F@foo", "", NBN1);
+ EntityName EN2("c:@F@foo", "", NBN2);
+ EntityName EN3("c:@F@bar", "", NBN1);
+
+ EXPECT_EQ(EN1, EN2);
+ EXPECT_NE(EN1, EN3);
+}
+
+TEST(EntityNameTest, EqualityWithDifferentSuffix) {
+ auto NBN = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+
+ EntityName EN1("c:@F@foo", "1", NBN);
+ EntityName EN2("c:@F@foo", "2", NBN);
+
+ EXPECT_NE(EN1, EN2);
+}
+
+TEST(EntityNameTest, EqualityWithDifferentNamespace) {
+ auto NBN1 = NestedBuildNamespace::makeCompilationUnit("test1.cpp");
+ auto NBN2 = NestedBuildNamespace::makeCompilationUnit("test2.cpp");
+
+ EntityName EN1("c:@F@foo", "", NBN1);
+ EntityName EN2("c:@F@foo", "", NBN2);
+
+ EXPECT_NE(EN1, EN2);
+}
+
+TEST(EntityNameTest, MakeQualified) {
+ auto NBN1 = NestedBuildNamespace::makeCompilationUnit("test.cpp");
+ EntityName EN("c:@F@foo", "", NBN1);
+
+ BuildNamespace LinkNS(BuildNamespaceKind::LinkUnit, "app");
+ NestedBuildNamespace NBN2(LinkNS);
+
+ auto Qualified = EN.makeQualified(NBN2);
+
+ EXPECT_NE(Qualified, EN);
+}
+
+} // namespace
+} // namespace clang::ssaf
