https://github.com/ziqingluo-90 updated https://github.com/llvm/llvm-project/pull/218207
>From dfc3dc14a18d11bfdea5c0ebefb5037de636dff7 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Fri, 21 Aug 2026 13:28:47 -0700 Subject: [PATCH 1/6] [SSAF][EntityPointerLevel] Add an intermediate data structure DeclPointerLevel A DeclPointerLevel differs from an EntityPointerLevel only in that it retains the AST Decl node instead of abstracting it to an Entity. The AST node carries more information, such as types, that can be used by extractors before converting DeclPointerLevels to EntityPointerLevels. E.g., PointerFlowExtractor can use it to compute the upper bound on pointer levels for an entity. It is needed for fixing the bug reported in rdar://183529483. First step for: rdar://183529483 --- .../EntityPointerLevel/EntityPointerLevel.h | 48 +++- .../EntityPointerLevel/EntityPointerLevel.cpp | 214 ++++++++++++------ .../EntityPointerLevelTest.cpp | 102 +++++++++ .../ScalableStaticAnalysis/CMakeLists.txt | 1 + 4 files changed, 289 insertions(+), 76 deletions(-) create mode 100644 clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp diff --git a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h index c296016258f8d..1a85003debcb3 100644 --- a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h +++ b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h @@ -12,10 +12,21 @@ #include "clang/AST/Expr.h" #include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h" #include <set> +#include <vector> namespace clang::ssaf { class TUSummaryExtractor; +// Intermediate data structure that can be converted to a `EntityPointerLevel`, +// which abstracts away all the additional information carried in the NamedDecl. +struct DeclPointerLevel { + const NamedDecl *Decl; + unsigned PointerLevel; + bool IsReturn; +}; + +using DeclPointerLevels = std::vector<DeclPointerLevel>; + /// An EntityPointerLevel is associated with a level of the declared /// pointer/array type of an entity. In the fully-expanded spelling of the /// declared type, a EntityPointerLevel is associated with a '*' (or a '[]`) in @@ -90,16 +101,43 @@ using EntityPointerLevelSet = /// /// \param E the pointer expression to be translated /// \param Ctx the AST context of `E` -/// \param AddEntity the callback provided by the caller to convert EntityNames -/// to EntityIds. +/// \param Extractor the TUSummaryExtractor used to convert NamedDecls to +/// EntityIds. llvm::Expected<EntityPointerLevelSet> translateEntityPointerLevel(const Expr *E, ASTContext &Ctx, TUSummaryExtractor &Extractor); +/// Same as `translateEntityPointerLevel`, except it returns raw +/// `(NamedDecl *, pointer level, is-return)` tuples (a.k.a. DeclPointerLevels) +/// instead of assembling an `EntityPointerLevelSet` directly. +llvm::Expected<DeclPointerLevels> +translateDeclPointerLevel(const Expr *E, ASTContext &Ctx, + TUSummaryExtractor &Extractor); + +/// Assemble `(NamedDecl *, pointer level, is-return)` tuples (a.k.a. +/// DeclPointerLevels) to `EntityPointerLevelSet`. +Expected<EntityPointerLevelSet> +toEntityPointerLevels(const DeclPointerLevels &DPLs, ASTContext &Ctx, + TUSummaryExtractor &Extractor); + +/// Convert a single `(NamedDecl *, pointer level, is-return)` tuple (a.k.a. +/// DeclPointerLevel) to an `EntityPointerLevel`. +Expected<EntityPointerLevel> +toEntityPointerLevel(const DeclPointerLevel &DPL, ASTContext &Ctx, + TUSummaryExtractor &Extractor); + /// Creates a `EntityPointerLevel` from a pair of an EntityId and a pointer /// level: EntityPointerLevel buildEntityPointerLevel(EntityId, unsigned); +/// Create an DeclPointerLevel (DPL) from a NamedDecl of a pointer/array type. +/// +/// \param ND the NamedDecl of a pointer/array type. +/// \param IsFunRet true iff the created DPL is associated with the return type +/// of a function entity. +DeclPointerLevel createDeclPointerLevel(const NamedDecl *ND, + bool IsFunRet = false); + /// Create an EntityPointerLevel (EPL) from a NamedDecl of a pointer/array type. /// /// \param ND the NamedDecl of a pointer/array type. @@ -111,6 +149,12 @@ llvm::Expected<EntityPointerLevel> createEntityPointerLevel(const NamedDecl *ND, TUSummaryExtractor &Extractor, bool IsFunRet = false); +/// \return an exhaustive vector of DeclPointerLevels, sorted in ascending order +/// of pointer level, such that every element is identical to \p DPL except with +/// a no-lower-than pointer level. The pointer level of each element is bounded +/// by the type of the NamedDecl of \p DPL. +DeclPointerLevels elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL); + /// Creates a new EntityPointerLevel (EPL) from `E` by incrementing `E`'s /// pointer level. /// \return the EPL that is associated with the pointee (or array element) type diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp index eb8dfdc5d9ace..d7f447fb093a3 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp @@ -14,7 +14,9 @@ #include "clang/AST/ExprCXX.h" #include "clang/AST/StmtVisitor.h" #include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h" +#include "llvm/ADT/STLExtras.h" #include <optional> +#include <vector> using namespace clang; using namespace ssaf; @@ -41,11 +43,11 @@ namespace clang::ssaf { // Translate(&arr[5]) -> {(arr, 1)} class EntityPointerLevelTranslator : ConstStmtVisitor<EntityPointerLevelTranslator, - Expected<EntityPointerLevelSet>> { + Expected<DeclPointerLevels>> { friend class StmtVisitorBase; // Fallback method for all unsupported expression kind: - Expected<EntityPointerLevelSet> fallback(const Stmt *S) { + Expected<DeclPointerLevels> fallback(const Stmt *S) { // Report an error/warning (at least in debug mode) for any unsupported kind // of pointer/array typed expression, because we want to understand every // pointer/array expression. But for non-pointer/array typed expressions, we @@ -55,7 +57,7 @@ class EntityPointerLevelTranslator return makeErrAtNode(Ctx, E, "attempt to translate %s to EntityPointerLevels", E->getStmtClassName()); - return EntityPointerLevelSet{}; + return DeclPointerLevels{}; } Expected<EntityPointerLevel> @@ -79,15 +81,15 @@ class EntityPointerLevelTranslator // The common helper function for Translate(*base): // Translate(*base) -> Translate(base) with .pointerLevel + 1 - Expected<EntityPointerLevelSet> translateDereferencePointer(const Expr *Ptr) { + Expected<DeclPointerLevels> translateDereferencePointer(const Expr *Ptr) { assert(hasPtrOrArrType(Ptr)); - Expected<EntityPointerLevelSet> SubResult = Visit(Ptr); + Expected<DeclPointerLevels> SubResult = Visit(Ptr); if (!SubResult) return SubResult.takeError(); - auto Incremented = llvm::map_range(*SubResult, incrementPointerLevel); - return EntityPointerLevelSet{Incremented.begin(), Incremented.end()}; + llvm::for_each(*SubResult, [](DeclPointerLevel &D) { ++D.PointerLevel; }); + return SubResult; } TUSummaryExtractor &Extractor; @@ -97,7 +99,7 @@ class EntityPointerLevelTranslator EntityPointerLevelTranslator(TUSummaryExtractor &Extractor, ASTContext &Ctx) : Extractor(Extractor), Ctx(Ctx) {} - Expected<EntityPointerLevelSet> translate(const Expr *E) { return Visit(E); } + Expected<DeclPointerLevels> translate(const Expr *E) { return Visit(E); } Expected<EntityPointerLevel> translate(const NamedDecl *D, bool IsRet) { if (!IsRet) return createEntityPointerLevelFor(D); @@ -109,26 +111,27 @@ class EntityPointerLevelTranslator D->getDeclKindName()); } - static EntityPointerLevel incrementPointerLevel(const EntityPointerLevel &E) { - return EntityPointerLevel({E.getEntity(), E.getPointerLevel() + 1}); + // Converts a `DeclPointerLevel` to an `EntityPointerLevel` + Expected<EntityPointerLevel> toEntityPointerLevel(const DeclPointerLevel &D) { + Expected<EntityPointerLevel> Base = translate(D.Decl, D.IsReturn); + if (!Base) + return Base.takeError(); + return buildEntityPointerLevel(Base->getEntity(), D.PointerLevel); } - static EntityPointerLevel decrementPointerLevel(const EntityPointerLevel &E) { - assert(E.getPointerLevel() > 0); - return EntityPointerLevel({E.getEntity(), E.getPointerLevel() - 1}); + static EntityPointerLevel incrementPointerLevel(const EntityPointerLevel &E) { + return EntityPointerLevel({E.getEntity(), E.getPointerLevel() + 1}); } private: - Expected<EntityPointerLevelSet> VisitStmt(const Stmt *E) { - return fallback(E); - } + Expected<DeclPointerLevels> VisitStmt(const Stmt *E) { return fallback(E); } // Translate(base + x) -> Translate(base) // Translate(x + base) -> Translate(base) // Translate(base - x) -> Translate(base) // Translate(base {+=, -=, =} x) -> Translate(base) // Translate(x, base) -> Translate(base) - Expected<EntityPointerLevelSet> VisitBinaryOperator(const BinaryOperator *E) { + Expected<DeclPointerLevels> VisitBinaryOperator(const BinaryOperator *E) { switch (E->getOpcode()) { case clang::BO_Add: if (hasPtrOrArrType(E->getLHS())) @@ -152,7 +155,7 @@ class EntityPointerLevelTranslator // Translate(&base) -> {}, if Translate(base) is {} // -> Translate(base) with .pointerLevel -= 1 // Translate(+base) -> Translate(base) - Expected<EntityPointerLevelSet> VisitUnaryOperator(const UnaryOperator *E) { + Expected<DeclPointerLevels> VisitUnaryOperator(const UnaryOperator *E) { switch (E->getOpcode()) { case clang::UO_PostInc: case clang::UO_PostDec: @@ -160,12 +163,15 @@ class EntityPointerLevelTranslator case clang::UO_PreDec: return Visit(E->getSubExpr()); case clang::UO_AddrOf: { - Expected<EntityPointerLevelSet> SubResult = Visit(E->getSubExpr()); + Expected<DeclPointerLevels> SubResult = Visit(E->getSubExpr()); if (!SubResult) return SubResult.takeError(); - auto Decremented = llvm::map_range(*SubResult, decrementPointerLevel); - return EntityPointerLevelSet{Decremented.begin(), Decremented.end()}; + llvm::for_each(*SubResult, [](DeclPointerLevel &D) { + assert(D.PointerLevel > 0); + --D.PointerLevel; + }); + return SubResult; } case clang::UO_Deref: return translateDereferencePointer(E->getSubExpr()); @@ -178,36 +184,35 @@ class EntityPointerLevelTranslator // Translate((T*)base) -> Translate(base) if base has pointer type // -> {} otherwise - Expected<EntityPointerLevelSet> VisitCastExpr(const CastExpr *E) { + Expected<DeclPointerLevels> VisitCastExpr(const CastExpr *E) { if (hasPtrOrArrType(E->getSubExpr())) return Visit(E->getSubExpr()); - return EntityPointerLevelSet{}; + return DeclPointerLevels{}; } // Translate(f(...)) -> {} if it is an indirect call // -> {(f_return, 1)}, otherwise - Expected<EntityPointerLevelSet> VisitCallExpr(const CallExpr *E) { - if (auto *FD = E->getDirectCallee()) { - if (auto ReturnId = Extractor.addEntityForReturn(FD)) - return EntityPointerLevelSet{buildEntityPointerLevel(*ReturnId, 1)}; - } - return EntityPointerLevelSet{}; + Expected<DeclPointerLevels> VisitCallExpr(const CallExpr *E) { + if (auto *FD = E->getDirectCallee()) + if (Extractor.addEntityForReturn(FD)) + return DeclPointerLevels{{FD, /*PointerLevel=*/1, /*IsReturn=*/true}}; + return DeclPointerLevels{}; } // Translate(base[x]) -> Translate(*base) - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevels> VisitArraySubscriptExpr(const ArraySubscriptExpr *E) { return translateDereferencePointer(E->getBase()); } // Translate(cond ? base1 : base2) := Translate(base1) U Translate(base2) - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevels> VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) { - Expected<EntityPointerLevelSet> ReT = Visit(E->getTrueExpr()); - Expected<EntityPointerLevelSet> ReF = Visit(E->getFalseExpr()); + Expected<DeclPointerLevels> ReT = Visit(E->getTrueExpr()); + Expected<DeclPointerLevels> ReF = Visit(E->getFalseExpr()); if (ReT && ReF) { - ReT->insert(ReF->begin(), ReF->end()); + ReT->insert(ReT->end(), ReF->begin(), ReF->end()); return ReT; } if (!ReF && !ReT) @@ -217,100 +222,94 @@ class EntityPointerLevelTranslator return ReT.takeError(); } - Expected<EntityPointerLevelSet> VisitParenExpr(const ParenExpr *E) { + Expected<DeclPointerLevels> VisitParenExpr(const ParenExpr *E) { return Visit(E->getSubExpr()); } // Translate("string-literal") -> {} // no entity involved - Expected<EntityPointerLevelSet> VisitStringLiteral(const StringLiteral *E) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevels> VisitStringLiteral(const StringLiteral *E) { + return DeclPointerLevels{}; } // Translate(predefined-expr) -> {} // treated the same as string literals - Expected<EntityPointerLevelSet> VisitPredefinedExpr(const PredefinedExpr *E) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevels> VisitPredefinedExpr(const PredefinedExpr *E) { + return DeclPointerLevels{}; } // Translate(integer-literal) -> {} // no entity involved - Expected<EntityPointerLevelSet> VisitIntegerLiteral(const IntegerLiteral *E) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevels> VisitIntegerLiteral(const IntegerLiteral *E) { + return DeclPointerLevels{}; } // Translate(DRE) -> {(Decl, 1)} - Expected<EntityPointerLevelSet> VisitDeclRefExpr(const DeclRefExpr *E) { - auto Res = createEntityPointerLevelFor(E->getDecl()); - if (!Res) - return Res.takeError(); - return EntityPointerLevelSet{*Res}; + Expected<DeclPointerLevels> VisitDeclRefExpr(const DeclRefExpr *E) { + return DeclPointerLevels{ + {E->getDecl(), /*PointerLevel=*/1, /*IsReturn=*/false}}; } // Translate({., ->}f) -> {(MemberDecl, 1)} - Expected<EntityPointerLevelSet> VisitMemberExpr(const MemberExpr *E) { - auto Res = createEntityPointerLevelFor(E->getMemberDecl()); - if (!Res) - return Res.takeError(); - return EntityPointerLevelSet{*Res}; + Expected<DeclPointerLevels> VisitMemberExpr(const MemberExpr *E) { + return DeclPointerLevels{ + {E->getMemberDecl(), /*PointerLevel=*/1, /*IsReturn=*/false}}; } // Unwrap CXXDefaultArgExpr - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevels> VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E) { return Visit(E->getExpr()); } // Unwrap OpaqueValueExpr - Expected<EntityPointerLevelSet> - VisitOpaqueValueExpr(const OpaqueValueExpr *S) { + Expected<DeclPointerLevels> VisitOpaqueValueExpr(const OpaqueValueExpr *S) { return Visit(S->getSourceExpr()); } // Unwrap ExprWithCleanups - Expected<EntityPointerLevelSet> - VisitExprWithCleanups(const ExprWithCleanups *S) { + Expected<DeclPointerLevels> VisitExprWithCleanups(const ExprWithCleanups *S) { return Visit(S->getSubExpr()); } // Unwrap MaterializeTemporaryExpr - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevels> VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) { return Visit(S->getSubExpr()); } // Unwrap CXXDefaultInitExpr - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevels> VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *E) { return Visit(E->getExpr()); } // Translate(`nullptr`) -> {} - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevels> VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *S) { - return EntityPointerLevelSet{}; + return DeclPointerLevels{}; } // Translate(`this`) -> {} - Expected<EntityPointerLevelSet> VisitCXXThisExpr(const CXXThisExpr *S) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevels> VisitCXXThisExpr(const CXXThisExpr *S) { + return DeclPointerLevels{}; } // Translate(`new`/`new [*]`) -> {} - Expected<EntityPointerLevelSet> VisitCXXNewExpr(const CXXNewExpr *S) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevels> VisitCXXNewExpr(const CXXNewExpr *S) { + return DeclPointerLevels{}; } // ImplicitValueInitExpr, for raw pointer type, // evaluates to a compile-time constant zero (or null). So no EPL in the // result. - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevels> VisitImplicitValueInitExpr(const ImplicitValueInitExpr *S) { - return EntityPointerLevelSet{}; + return DeclPointerLevels{}; } // The InitListExpr must be an empty or singleton list that // initializes a pointer scalar. Other cases are unexpected thus an error. - Expected<EntityPointerLevelSet> VisitInitListExpr(const InitListExpr *E) { + Expected<DeclPointerLevels> VisitInitListExpr(const InitListExpr *E) { if (E->getNumInits() < 1) - return EntityPointerLevelSet{}; + return DeclPointerLevels{}; if (E->getType()->isPointerType()) return Visit(E->getInit(0)); return llvm::createStringError( @@ -323,28 +322,42 @@ class EntityPointerLevelTranslator // When a CXXConstructExpr has an array type, clang is initializing an array // of class-type objects with default values. In this case, no entity is // associated with the initializer. - Expected<EntityPointerLevelSet> - VisitCXXConstructExpr(const CXXConstructExpr *E) { + Expected<DeclPointerLevels> VisitCXXConstructExpr(const CXXConstructExpr *E) { if (E->getType()->isArrayType()) { - return EntityPointerLevelSet{}; + return DeclPointerLevels{}; } return fallback(E); } // No entity is associated with a CXXScalarValueInitExpr: - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevels> VisitCXXScalarValueInitExpr(const CXXScalarValueInitExpr *E) { - return EntityPointerLevelSet{}; + return DeclPointerLevels{}; } }; } // namespace clang::ssaf +Expected<DeclPointerLevels> +clang::ssaf::translateDeclPointerLevel(const Expr *E, ASTContext &Ctx, + TUSummaryExtractor &Extractor) { + EntityPointerLevelTranslator Translator(Extractor, Ctx); + + return Translator.translate(E); +} + Expected<EntityPointerLevelSet> clang::ssaf::translateEntityPointerLevel(const Expr *E, ASTContext &Ctx, TUSummaryExtractor &Extractor) { EntityPointerLevelTranslator Translator(Extractor, Ctx); + auto DPLs = Translator.translate(E); + if (!DPLs) + return DPLs.takeError(); + return toEntityPointerLevels(*DPLs, Ctx, Extractor); +} - return Translator.translate(E); +DeclPointerLevel clang::ssaf::createDeclPointerLevel(const NamedDecl *ND, + bool IsFunRet) { + return {ND, 1, IsFunRet}; } /// Create an EntityPointerLevel from a ValueDecl of a pointer type. @@ -355,6 +368,59 @@ Expected<EntityPointerLevel> clang::ssaf::createEntityPointerLevel( return Translator.translate(ND, IsFunRet); } +DeclPointerLevels +clang::ssaf::elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL) { + DeclPointerLevels Result{DPL}; + QualType T; + + if (DPL.IsReturn) { + if (const auto *FD = dyn_cast<FunctionDecl>(DPL.Decl)) + T = FD->getReturnType().getNonReferenceType(); + } else if (const auto *VD = dyn_cast<ValueDecl>(DPL.Decl)) { + T = VD->getType().getNonReferenceType(); + } + if (T.isNull()) + return Result; + + // Count the max pointer/array levels of `T`: + unsigned MaxLevel = 0; + for (T = T.getCanonicalType();; ++MaxLevel) { + if (const auto *PT = dyn_cast<PointerType>(T)) + T = PT->getPointeeType().getCanonicalType(); + else if (const auto *AT = dyn_cast<ArrayType>(T)) + T = AT->getElementType().getCanonicalType(); + else + break; + } + + for (unsigned Level = DPL.PointerLevel + 1; Level <= MaxLevel; ++Level) + Result.push_back({DPL.Decl, Level, DPL.IsReturn}); + return Result; +} + +Expected<EntityPointerLevelSet> +clang::ssaf::toEntityPointerLevels(const DeclPointerLevels &DPLs, + ASTContext &Ctx, + TUSummaryExtractor &Extractor) { + EntityPointerLevelTranslator Translator(Extractor, Ctx); + EntityPointerLevelSet Result; + + for (const auto &DPL : DPLs) { + Expected<EntityPointerLevel> EPL = Translator.toEntityPointerLevel(DPL); + if (!EPL) + return EPL.takeError(); + Result.insert(*EPL); + } + return Result; +} + +Expected<EntityPointerLevel> +clang::ssaf::toEntityPointerLevel(const DeclPointerLevel &DPL, ASTContext &Ctx, + TUSummaryExtractor &Extractor) { + EntityPointerLevelTranslator Translator(Extractor, Ctx); + return Translator.toEntityPointerLevel(DPL); +} + EntityPointerLevel clang::ssaf::incrementPointerLevel(const EntityPointerLevel &E) { return EntityPointerLevelTranslator::incrementPointerLevel(E); diff --git a/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp b/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp new file mode 100644 index 0000000000000..d9b5a347edb6c --- /dev/null +++ b/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp @@ -0,0 +1,102 @@ +//===- EntityPointerLevelTest.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/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h" +#include "FindDecl.h" +#include "clang/AST/Decl.h" +#include "clang/Frontend/ASTUnit.h" +#include "clang/Tooling/Tooling.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include <memory> +#include <vector> + +using namespace clang; +using namespace ssaf; +using testing::ElementsAre; + +namespace { + +static std::vector<unsigned> levelsOf(const DeclPointerLevels &DPLs) { + std::vector<unsigned> Levels; + for (const DeclPointerLevel &DPL : DPLs) + Levels.push_back(DPL.PointerLevel); + return Levels; +} + +// `elaborateHigherDeclPointerLevels` expands a DeclPointerLevel into an +// ascending, exhaustive vector of DeclPointerLevels for the same declaration, +// from the given level up to the maximum pointer level of the declared type. +TEST(EntityPointerLevelTest, ElaborateHigherDeclPointerLevels) { + std::unique_ptr<ASTUnit> AST = + tooling::buildASTFromCodeWithArgs(R"cpp( + int *p; // one pointer level + int **q; // two pointer levels + int ***r; // three pointer levels + int *arr[10]; // array of pointers: two levels (array + pointer) + )cpp", + {"-Wno-unused"}); + ASSERT_TRUE(AST); + ASTContext &Ctx = AST->getASTContext(); + + // Elaborate the decl named `Name` starting at `StartLevel`, checking that + // every result shares the input's declaration and is-return flag, and return + // the produced pointer levels. + auto elaborate = [&](StringRef Name, unsigned StartLevel) { + const NamedDecl *ND = findDeclByName(Name, Ctx); + EXPECT_NE(ND, nullptr) << "decl not found: " << Name.str(); + if (!ND) + return std::vector<unsigned>{}; + DeclPointerLevels DPLs = elaborateHigherDeclPointerLevels( + DeclPointerLevel{ND, StartLevel, /*IsReturn=*/false}); + for (const DeclPointerLevel &DPL : DPLs) { + EXPECT_TRUE(DPL.Decl == ND); + EXPECT_FALSE(DPL.IsReturn); + } + return levelsOf(DPLs); + }; + + EXPECT_THAT(elaborate("p", 1), ElementsAre(1U)); // int* + EXPECT_THAT(elaborate("q", 1), ElementsAre(1U, 2U)); // int** + EXPECT_THAT(elaborate("r", 1), ElementsAre(1U, 2U, 3U)); // int*** + EXPECT_THAT(elaborate("arr", 1), ElementsAre(1U, 2U)); // int*[10] + EXPECT_THAT(elaborate("r", 2), ElementsAre(2U, 3U)); + EXPECT_THAT(elaborate("r", 3), ElementsAre(3U)); +} + +// For a function entity (IsReturn=true), the maximum pointer level is bounded +// by the return type, whose reference must be stripped first. +TEST(EntityPointerLevelTest, ElaborateHigherDeclPointerLevelsForReturn) { + std::unique_ptr<ASTUnit> AST = + tooling::buildASTFromCodeWithArgs(R"cpp( + int **&refret(); // reference to int**: two pointer levels + int *valret(); // int*: one pointer level + )cpp", + {"-Wno-unused"}); + ASSERT_TRUE(AST); + ASTContext &Ctx = AST->getASTContext(); + + auto elaborateReturn = [&](StringRef Name, unsigned StartLevel) { + const FunctionDecl *FD = findFnByName(Name, Ctx); + EXPECT_NE(FD, nullptr) << "function not found: " << Name.str(); + if (!FD) + return std::vector<unsigned>{}; + DeclPointerLevels DPLs = elaborateHigherDeclPointerLevels( + DeclPointerLevel{FD, StartLevel, /*IsReturn=*/true}); + for (const DeclPointerLevel &DPL : DPLs) { + EXPECT_TRUE(DPL.Decl == FD); + EXPECT_TRUE(DPL.IsReturn); + } + return levelsOf(DPLs); + }; + + EXPECT_THAT(elaborateReturn("refret", 1), ElementsAre(1U, 2U)); // int**& + EXPECT_THAT(elaborateReturn("valret", 1), ElementsAre(1U)); // int* +} + +} // namespace diff --git a/clang/unittests/ScalableStaticAnalysis/CMakeLists.txt b/clang/unittests/ScalableStaticAnalysis/CMakeLists.txt index ed3b57168b069..21fcfd34741cb 100644 --- a/clang/unittests/ScalableStaticAnalysis/CMakeLists.txt +++ b/clang/unittests/ScalableStaticAnalysis/CMakeLists.txt @@ -1,4 +1,5 @@ add_distinct_clang_unittest(ClangScalableAnalysisTests + Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp Analyses/PointerFlow/PointerFlowTest.cpp Analyses/PointerFlow/PointerFlowWPATest.cpp Analyses/CallGraph/CallGraphExtractorTest.cpp >From cc8ca52fc83cebb8157591fef2c6c8e064a7850e Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Thu, 20 Aug 2026 18:34:32 -0700 Subject: [PATCH 2/6] [SSAF][PointerFlow] A pointer assignment may yield more than one edge This commit is a redesign of #198889, which introduced a non-termination bug. Consider a pointer assignment 'p = q', where 'p' and 'q' are multi-level pointers. The PointerFlow extractor previously built a single relation '(p,1) -> (q,1)', meaning that if 'p' has a property, so must 'q'. For the properties we care about, such as "a pointer type has bounds", the assignment also encodes '(p,2) -> (q,2)', meaning that if '*p/p[i]' has a property, so must '*q/q[j]', and so on, up to the maximum pointer level 'p' and 'q' can have. Otherwise, the bounds information will be lost after the assignment. These additional relations were previously expanded during the WPA phase, relying on the fact that 'p' and 'q' are type-checked so that the expansion is monotone---the graph cannot simultaneously contain '(p,2) -> (q,1)' and '(q,2) -> (p,1)'. However, that assumption does not hold in the presence of reinterpreting casts, which causes WPA to hang on examples such as: ``` a = *b; // (a, 1) -> (b, 2) b = (char ***)*a; // (b, 1) -> (a, 2) ``` The fix is to impose an upper bound on the pointer level according to the pointers' types. Since type information is abstracted away before WPA, this commit moves the expansion logic back into PointerFlowExtractor, where the types are still available. The difference it makes to the PointerFlowExtractor is that the output was compressed (because one graph edge represents more) and is now uncompressed. It simplifies WPA, because the meaning of each graph edge is now straightforward. In the future, we may want to make the edge expansion optional, so that it can be disabled when propagating non-type properties. Second step of: rdar://183529483 --- .../EntityPointerLevel/EntityPointerLevel.h | 6 - .../EntityPointerLevel/EntityPointerLevel.cpp | 9 -- .../PointerFlow/PointerFlowExtractor.cpp | 112 +++++++++--------- .../Analyses/PointerFlow/PointerFlowTest.cpp | 43 ++++++- 4 files changed, 96 insertions(+), 74 deletions(-) diff --git a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h index 1a85003debcb3..4db6a8116f476 100644 --- a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h +++ b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h @@ -154,12 +154,6 @@ createEntityPointerLevel(const NamedDecl *ND, TUSummaryExtractor &Extractor, /// a no-lower-than pointer level. The pointer level of each element is bounded /// by the type of the NamedDecl of \p DPL. DeclPointerLevels elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL); - -/// Creates a new EntityPointerLevel (EPL) from `E` by incrementing `E`'s -/// pointer level. -/// \return the EPL that is associated with the pointee (or array element) type -/// of `E`'s associated pointer/array type of the same entity. -EntityPointerLevel incrementPointerLevel(const EntityPointerLevel &E); } // namespace clang::ssaf #endif // LLVM_CLANG_SCALABLESTATICANALYSIS_ANALYSES_ENTITYPOINTERLEVEL_ENTITYPOINTERLEVEL_H diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp index d7f447fb093a3..0eceeb8256a3c 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp @@ -119,10 +119,6 @@ class EntityPointerLevelTranslator return buildEntityPointerLevel(Base->getEntity(), D.PointerLevel); } - static EntityPointerLevel incrementPointerLevel(const EntityPointerLevel &E) { - return EntityPointerLevel({E.getEntity(), E.getPointerLevel() + 1}); - } - private: Expected<DeclPointerLevels> VisitStmt(const Stmt *E) { return fallback(E); } @@ -421,11 +417,6 @@ clang::ssaf::toEntityPointerLevel(const DeclPointerLevel &DPL, ASTContext &Ctx, return Translator.toEntityPointerLevel(DPL); } -EntityPointerLevel -clang::ssaf::incrementPointerLevel(const EntityPointerLevel &E) { - return EntityPointerLevelTranslator::incrementPointerLevel(E); -} - EntityPointerLevel clang::ssaf::buildEntityPointerLevel(EntityId Id, unsigned PtrLv) { return EntityPointerLevel({Id, PtrLv}); diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp index 42d5b5a7de041..3b9b225a52d0a 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp @@ -15,21 +15,16 @@ #include "clang/AST/ExprCXX.h" #include "clang/AST/Stmt.h" #include "clang/AST/TypeBase.h" -#include "clang/Frontend/SSAFOptions.h" #include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h" #include "clang/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlow.h" #include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h" -#include "clang/ScalableStaticAnalysis/Core/Model/EntityName.h" #include "clang/ScalableStaticAnalysis/Core/TUSummary/ExtractorRegistry.h" #include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryBuilder.h" #include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/STLFunctionalExtras.h" -#include "llvm/ADT/Sequence.h" -#include "llvm/Support/Debug.h" #include "llvm/Support/Error.h" #include <memory> -#include <optional> namespace clang::ssaf { extern PointerFlowEntitySummary buildPointerFlowEntitySummary(EdgeSet Edges); @@ -59,15 +54,16 @@ class PointerFlowMatcher { llvm::Error matchesDecl(const Decl *D, const NamedDecl *RootDecl); private: - std::function<EntityId(const EntityName &)> AddEntity; + llvm::Error addEdges(Expected<DeclPointerLevels> &&LHS, + Expected<DeclPointerLevels> &&RHS); - Expected<EntityPointerLevelSet> toEPL(const NamedDecl *N, - bool IsRet = false) const; - - Expected<EntityPointerLevelSet> toEPL(const Expr *N) const; + Expected<DeclPointerLevels> toDPL(const Expr *N) const { + return translateDeclPointerLevel(N, Ctx, Extractor); + } - llvm::Error addEdges(Expected<EntityPointerLevelSet> &&LHS, - Expected<EntityPointerLevelSet> &&RHS); + static DeclPointerLevel toDPL(const NamedDecl *N, bool IsRet = false) { + return createDeclPointerLevel(N, IsRet); + } template <typename ParmsProvider, typename ArgsProvider> llvm::Error matchesArgsWithParams(unsigned ArgIdxStart, ParmsProvider *PP, @@ -79,7 +75,8 @@ class PointerFlowMatcher { ++ArgIdx, ++ParmIdx) { if (const ParmVarDecl *PD = PP->getParamDecl(ParmIdx); PD && hasPtrOrArrType(PD)) { - if (auto Err = addEdges(toEPL(PD), toEPL(AP->getArg(ArgIdx)))) + if (auto Err = addEdges(DeclPointerLevels{toDPL(PD)}, + toDPL(AP->getArg(ArgIdx)))) return Err; } } @@ -87,22 +84,8 @@ class PointerFlowMatcher { } }; -Expected<EntityPointerLevelSet> PointerFlowMatcher::toEPL(const NamedDecl *N, - bool IsRet) const { - auto Ret = createEntityPointerLevel(N, Extractor, IsRet); - - if (Ret) - return EntityPointerLevelSet{*Ret}; - return Ret.takeError(); -} - -Expected<EntityPointerLevelSet> PointerFlowMatcher::toEPL(const Expr *N) const { - return translateEntityPointerLevel(N, Ctx, Extractor); -} - -llvm::Error -PointerFlowMatcher::addEdges(Expected<EntityPointerLevelSet> &&LHS, - Expected<EntityPointerLevelSet> &&RHS) { +llvm::Error PointerFlowMatcher::addEdges(Expected<DeclPointerLevels> &&LHS, + Expected<DeclPointerLevels> &&RHS) { if (!LHS && !RHS) return llvm::joinErrors(LHS.takeError(), RHS.takeError()); if (!LHS) @@ -111,15 +94,45 @@ PointerFlowMatcher::addEdges(Expected<EntityPointerLevelSet> &&LHS, return RHS.takeError(); if (RHS->empty()) return llvm::Error::success(); - for (auto L : *LHS) - Results[L].insert(RHS->begin(), RHS->end()); + + std::vector<DeclPointerLevels> LVecs, RVecs; + + for (const auto &L : *LHS) + LVecs.push_back(elaborateHigherDeclPointerLevels(L)); + for (const auto &R : *RHS) + RVecs.push_back(elaborateHigherDeclPointerLevels(R)); + + // Imagine an assignment from pointer q to p: 'p = q'. It encodes that if 'p' + // has some property, so must 'q'; moreover, if '*p/p[i]' has some property, + // so must '*q/q[i]' and so on. Therefore, for each edge '(a, n) -> (b, m)' + // that represents an explicitly spelled place in the source code, we also add + // '(a, n + 1) -> (b, m + 1)', + // '(a, n + 2) -> (b, m + 2)', ... continuing until either 'a' or 'b' reaches + // its maximum pointer level, whichever happens first. + // + // Note that type checking ensures that 'p' and 'q' have + // identical pointer levels, but '(a, n)' and '(b, m)' may have different + // upper bounds on their pointer levels, when, for example, 'q' is a + // cast-expression. + + for (const DeclPointerLevels &L : LVecs) + for (const DeclPointerLevels &R : RVecs) + for (const auto &[LDPL, RDPL] : llvm::zip(L, R)) { + auto LEPL = toEntityPointerLevel(LDPL, Ctx, Extractor); + if (!LEPL) + return LEPL.takeError(); + auto REPL = toEntityPointerLevel(RDPL, Ctx, Extractor); + if (!REPL) + return REPL.takeError(); + Results[*LEPL].insert(*REPL); + } return llvm::Error::success(); } /// Match and extract pointer flow. /// The extraction function 'XF' can be described by the following rules: /// -/// XF(l = r) := add edge "toEPL(l) -> toEPL(r))" +/// XF(l = r) := addEdges(toDPL(l), toDPL(r)) /// XF(foo(a, b, ...)) := XF(Param_1 = a), XF(Param_2 = b), ... /// XF(return e;) := XF(FunRet = e), where 'FunRet' is the return /// entity of the enclosing @@ -130,7 +143,7 @@ PointerFlowMatcher::addEdges(Expected<EntityPointerLevelSet> &&LHS, /// ctor's body will be visited separately. /// XF(T var = e) := XF(var = e) /// XF(T var = init-list) := see \ref -/// PointerFlowMatcher::matchInitializerList +/// PointerFlowMatcher::matchesInitializerList llvm::Error PointerFlowMatcher::matches(const DynTypedNode &DynNode, const NamedDecl *RootDecl) { if (const Stmt *S = DynNode.get<Stmt>()) @@ -145,7 +158,7 @@ llvm::Error PointerFlowMatcher::matchesStmt(const Stmt *S, // Match 'p = q' whenever it has pointer or array type: if (const auto *BO = dyn_cast<BinaryOperator>(S); BO && BO->getOpcode() == BO_Assign && hasPtrOrArrType(BO)) { - return addEdges(toEPL(BO->getLHS()), toEPL(BO->getRHS())); + return addEdges(toDPL(BO->getLHS()), toDPL(BO->getRHS())); } // Match arg-to-param passing (in CallExpr) for any pointer type argument: @@ -172,7 +185,7 @@ llvm::Error PointerFlowMatcher::matchesStmt(const Stmt *S, const Expr *RetExpr = RS->getRetValue(); if (!RetExpr || !hasPtrOrArrType(RetExpr)) return llvm::Error::success(); - return addEdges(toEPL(RootDecl, true), toEPL(RetExpr)); + return addEdges(DeclPointerLevels{toDPL(RootDecl, true)}, toDPL(RetExpr)); } return llvm::Error::success(); } @@ -193,7 +206,7 @@ llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D, // Match initializers to variables/fields of a pointer type: if (InitExpr && hasPtrOrArrType(VD)) - return addEdges(toEPL(VD), toEPL(InitExpr)); + return addEdges(DeclPointerLevels{toDPL(VD)}, toDPL(InitExpr)); } // Match C++ constructor member-initializers: @@ -202,7 +215,8 @@ llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D, if (E->isDelegatingInitializer()) return matches(DynTypedNode::create(*E->getInit()), RootDecl); if (const FieldDecl *FD = E->getMember(); FD && hasPtrOrArrType(FD)) { - if (auto Err = addEdges(toEPL(E->getMember()), toEPL(E->getInit()))) + if (auto Err = addEdges(DeclPointerLevels{toDPL(E->getMember())}, + toDPL(E->getInit()))) return Err; } } @@ -210,7 +224,7 @@ llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D, return llvm::Error::success(); } -// Helper function for matchInitializerList that handles record: +// Helper function for matchesInitializerList that handles record: llvm::Error matchInitializerListForRecordDecl(PointerFlowMatcher &Matcher, const RecordDecl *RecordTy, const InitListExpr *ILE) { @@ -242,7 +256,7 @@ llvm::Error matchInitializerListForRecordDecl(PointerFlowMatcher &Matcher, return llvm::Error::success(); } -// Helper function for matchInitializerList that handles array: +// Helper function for matchesInitializerList that handles array: llvm::Error matchInitializerListForArray(PointerFlowMatcher &Matcher, const ValueDecl *Array, const InitListExpr *ILE, @@ -267,7 +281,7 @@ llvm::Error matchInitializerListForArray(PointerFlowMatcher &Matcher, /// /// The process is recursive: 'a', 'b', 'c', ... may themselves be /// initializer lists. We therefore use \p ArrayElementIndirectLevel to keep -/// track of the pointer level the left-hand side. +/// track of the pointer level of the left-hand side. llvm::Error PointerFlowMatcher::matchesInitializerList(const ValueDecl *Base, const Expr *InitExpr, @@ -278,20 +292,10 @@ PointerFlowMatcher::matchesInitializerList(const ValueDecl *Base, if (!hasPtrOrArrType(InitExpr)) return llvm::Error::success(); - auto BaseEPL = toEPL(Base); - - if (!BaseEPL) - return BaseEPL.takeError(); - - // Apply ArrayElementIndirectLevel to BaseEPL - auto R = llvm::map_range(*BaseEPL, [&ArrayElementIndirectLevel]( - const EntityPointerLevel &EPL) { - EntityPointerLevel Result = EPL; - for ([[maybe_unused]] auto Ignored : llvm::seq(ArrayElementIndirectLevel)) - Result = incrementPointerLevel(Result); - return Result; - }); - return addEdges(EntityPointerLevelSet{R.begin(), R.end()}, toEPL(InitExpr)); + auto BaseDPL = toDPL(Base); + // Apply ArrayElementIndirectLevel to BaseDPL + BaseDPL.PointerLevel += ArrayElementIndirectLevel; + return addEdges(DeclPointerLevels{BaseDPL}, toDPL(InitExpr)); } // Note that `Base`'s type is NOT the real LHS type when // ArrayElementIndirectLevel > 0: diff --git a/clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp b/clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp index 1260aad81a8bf..1f5b3d697c35c 100644 --- a/clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp +++ b/clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp @@ -751,7 +751,10 @@ TEST_F(PointerFlowTest, LocalVarDeclInit2) { auto *Sum = getEntitySummary("foo"); ASSERT_NE(Sum, nullptr); - EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"p", 1U}, {"arr", 1U}}})); + // 'p' and 'arr' are both 'int (*)[10]' (max level 2: pointer + array), so the + // base edge (p, 1) -> (arr, 1) is elaborated with (p, 2) -> (arr, 2). + EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"p", 1U}, {"arr", 1U}}, + {{"p", 2U}, {"arr", 2U}}})); } TEST_F(PointerFlowTest, FieldInit) { @@ -1113,6 +1116,26 @@ TEST_F(PointerFlowTest, MultipleReturnEdges) { })); } +// A function returning a reference to a multi-level pointer. The return +// type `int **&` has two pointer levels once the reference is stripped, so the +// (foo_ret, n) -> (gpp, m) edge should be elaborated up to level 2. +TEST_F(PointerFlowTest, ReturnRefToMultiLevelPointer) { + ASSERT_TRUE(setUpTest(R"cpp( + int **gpp; + int **&foo() { + return gpp; + } + )cpp")); + + auto *Sum = getEntitySummary("foo"); + + ASSERT_NE(Sum, nullptr); + EXPECT_EQ(*Sum, makeEdges(__LINE__, { + {{"foo", 1U, true}, {"gpp", 1U}}, + {{"foo", 2U, true}, {"gpp", 2U}}, + })); +} + TEST_F(PointerFlowTest, NoReturnEdgeForNonPointerReturnType) { ASSERT_EQ(setUpTest(R"cpp( int foo(int *p, int x) { @@ -1390,9 +1413,13 @@ TEST_F(PointerFlowTest, StructuredBindingWithPointers) { testing::internal::CaptureStderr(); ASSERT_TRUE(setUpTest(Code)); - // Verify the warning was logged + // Verify the warning was logged: + // The structured-binding initializer is an ArrayInitLoopExpr (an element-wise + // array copy), which the translator does not support. It is reported as a + // warning rather than crashing, and no summary is produced for 'foo'. ASSERT_TRUE(StringRef(testing::internal::GetCapturedStderr()) - .contains("failed to create EntityId for Decomposition")); + .contains("attempt to translate ArrayInitLoopExpr to " + "EntityPointerLevels")); } #endif @@ -1440,7 +1467,10 @@ TEST_F(PointerFlowTest, ArgToRefParamLevel2) { auto *Sum = getEntitySummary("caller"); ASSERT_TRUE(Sum); - EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"rp", 1U}, {"pp", 1U}}})); + // Both 'rp' and 'pp' are 'int**' (max level 2), so the base edge + // (rp, 1) -> (pp, 1) is elaborated with the higher-level (rp, 2) -> (pp, 2). + EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"rp", 1U}, {"pp", 1U}}, + {{"rp", 2U}, {"pp", 2U}}})); } TEST_F(PointerFlowTest, InitRefPtr) { @@ -1543,7 +1573,10 @@ TEST_F(PointerFlowTest, RefBindMultiLevel) { auto *Sum = getEntitySummary<VarDecl>("r"); ASSERT_NE(Sum, nullptr); - EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"r", 1U}, {"gpp", 1U}}})); + // Both 'r' and 'gpp' are 'int**' (max level 2), so the base edge + // (r, 1) -> (gpp, 1) is elaborated with the higher-level (r, 2) -> (gpp, 2). + EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"r", 1U}, {"gpp", 1U}}, + {{"r", 2U}, {"gpp", 2U}}})); } TEST_F(PointerFlowTest, RefBindTernaryInit) { >From ebd5fb67a2866eec87dd38ad807eeda334af9e2e Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Fri, 28 Aug 2026 11:56:31 -0700 Subject: [PATCH 3/6] Update clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Balázs Benics <[email protected]> --- .../Analyses/EntityPointerLevel/EntityPointerLevel.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h index 1a85003debcb3..9fb63ba2295e3 100644 --- a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h +++ b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h @@ -107,7 +107,7 @@ llvm::Expected<EntityPointerLevelSet> translateEntityPointerLevel(const Expr *E, ASTContext &Ctx, TUSummaryExtractor &Extractor); -/// Same as `translateEntityPointerLevel`, except it returns raw +/// Same as \c translateEntityPointerLevel, except it returns raw /// `(NamedDecl *, pointer level, is-return)` tuples (a.k.a. DeclPointerLevels) /// instead of assembling an `EntityPointerLevelSet` directly. llvm::Expected<DeclPointerLevels> >From 80b68743b9674e1771b1fa79f5f01fdb4a57a390 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Fri, 28 Aug 2026 14:31:20 -0700 Subject: [PATCH 4/6] address comments --- .../EntityPointerLevel/EntityPointerLevel.h | 24 ++- .../EntityPointerLevel/EntityPointerLevel.cpp | 122 ++++++------ .../EntityPointerLevelTest.cpp | 175 +++++++++++++----- 3 files changed, 200 insertions(+), 121 deletions(-) diff --git a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h index 9fb63ba2295e3..c3bb3b13acd2d 100644 --- a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h +++ b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h @@ -11,8 +11,8 @@ #include "clang/AST/Expr.h" #include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h" +#include "llvm/ADT/SmallVector.h" #include <set> -#include <vector> namespace clang::ssaf { class TUSummaryExtractor; @@ -25,7 +25,7 @@ struct DeclPointerLevel { bool IsReturn; }; -using DeclPointerLevels = std::vector<DeclPointerLevel>; +using DeclPointerLevelVec = llvm::SmallVector<DeclPointerLevel, 2>; /// An EntityPointerLevel is associated with a level of the declared /// pointer/array type of an entity. In the fully-expanded spelling of the @@ -110,18 +110,16 @@ translateEntityPointerLevel(const Expr *E, ASTContext &Ctx, /// Same as \c translateEntityPointerLevel, except it returns raw /// `(NamedDecl *, pointer level, is-return)` tuples (a.k.a. DeclPointerLevels) /// instead of assembling an `EntityPointerLevelSet` directly. -llvm::Expected<DeclPointerLevels> +llvm::Expected<DeclPointerLevelVec> translateDeclPointerLevel(const Expr *E, ASTContext &Ctx, TUSummaryExtractor &Extractor); -/// Assemble `(NamedDecl *, pointer level, is-return)` tuples (a.k.a. -/// DeclPointerLevels) to `EntityPointerLevelSet`. +/// Assemble `DeclPointerLevels` into an `EntityPointerLevelSet`. Expected<EntityPointerLevelSet> -toEntityPointerLevels(const DeclPointerLevels &DPLs, ASTContext &Ctx, +toEntityPointerLevels(const DeclPointerLevelVec &DPLs, ASTContext &Ctx, TUSummaryExtractor &Extractor); -/// Convert a single `(NamedDecl *, pointer level, is-return)` tuple (a.k.a. -/// DeclPointerLevel) to an `EntityPointerLevel`. +/// Convert a single `DeclPointerLevel` to an `EntityPointerLevel`. Expected<EntityPointerLevel> toEntityPointerLevel(const DeclPointerLevel &DPL, ASTContext &Ctx, TUSummaryExtractor &Extractor); @@ -149,11 +147,11 @@ llvm::Expected<EntityPointerLevel> createEntityPointerLevel(const NamedDecl *ND, TUSummaryExtractor &Extractor, bool IsFunRet = false); -/// \return an exhaustive vector of DeclPointerLevels, sorted in ascending order -/// of pointer level, such that every element is identical to \p DPL except with -/// a no-lower-than pointer level. The pointer level of each element is bounded -/// by the type of the NamedDecl of \p DPL. -DeclPointerLevels elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL); +/// \return an exhaustive vector of unique DeclPointerLevels, sorted in +/// ascending order of pointer levels. All elements are identical to \p DPL +/// except with a pointer level greater than or equal to that of \p DPL. The +/// pointer level of each element is bounded by the type of \p DPL's NamedDecl. +DeclPointerLevelVec elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL); /// Creates a new EntityPointerLevel (EPL) from `E` by incrementing `E`'s /// pointer level. diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp index d7f447fb093a3..e337e37577ec7 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp @@ -16,7 +16,6 @@ #include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h" #include "llvm/ADT/STLExtras.h" #include <optional> -#include <vector> using namespace clang; using namespace ssaf; @@ -43,11 +42,11 @@ namespace clang::ssaf { // Translate(&arr[5]) -> {(arr, 1)} class EntityPointerLevelTranslator : ConstStmtVisitor<EntityPointerLevelTranslator, - Expected<DeclPointerLevels>> { + Expected<DeclPointerLevelVec>> { friend class StmtVisitorBase; // Fallback method for all unsupported expression kind: - Expected<DeclPointerLevels> fallback(const Stmt *S) { + Expected<DeclPointerLevelVec> fallback(const Stmt *S) { // Report an error/warning (at least in debug mode) for any unsupported kind // of pointer/array typed expression, because we want to understand every // pointer/array expression. But for non-pointer/array typed expressions, we @@ -57,7 +56,7 @@ class EntityPointerLevelTranslator return makeErrAtNode(Ctx, E, "attempt to translate %s to EntityPointerLevels", E->getStmtClassName()); - return DeclPointerLevels{}; + return DeclPointerLevelVec{}; } Expected<EntityPointerLevel> @@ -81,10 +80,10 @@ class EntityPointerLevelTranslator // The common helper function for Translate(*base): // Translate(*base) -> Translate(base) with .pointerLevel + 1 - Expected<DeclPointerLevels> translateDereferencePointer(const Expr *Ptr) { + Expected<DeclPointerLevelVec> translateDereferencePointer(const Expr *Ptr) { assert(hasPtrOrArrType(Ptr)); - Expected<DeclPointerLevels> SubResult = Visit(Ptr); + Expected<DeclPointerLevelVec> SubResult = Visit(Ptr); if (!SubResult) return SubResult.takeError(); @@ -99,7 +98,7 @@ class EntityPointerLevelTranslator EntityPointerLevelTranslator(TUSummaryExtractor &Extractor, ASTContext &Ctx) : Extractor(Extractor), Ctx(Ctx) {} - Expected<DeclPointerLevels> translate(const Expr *E) { return Visit(E); } + Expected<DeclPointerLevelVec> translate(const Expr *E) { return Visit(E); } Expected<EntityPointerLevel> translate(const NamedDecl *D, bool IsRet) { if (!IsRet) return createEntityPointerLevelFor(D); @@ -124,14 +123,14 @@ class EntityPointerLevelTranslator } private: - Expected<DeclPointerLevels> VisitStmt(const Stmt *E) { return fallback(E); } + Expected<DeclPointerLevelVec> VisitStmt(const Stmt *E) { return fallback(E); } // Translate(base + x) -> Translate(base) // Translate(x + base) -> Translate(base) // Translate(base - x) -> Translate(base) // Translate(base {+=, -=, =} x) -> Translate(base) // Translate(x, base) -> Translate(base) - Expected<DeclPointerLevels> VisitBinaryOperator(const BinaryOperator *E) { + Expected<DeclPointerLevelVec> VisitBinaryOperator(const BinaryOperator *E) { switch (E->getOpcode()) { case clang::BO_Add: if (hasPtrOrArrType(E->getLHS())) @@ -155,7 +154,7 @@ class EntityPointerLevelTranslator // Translate(&base) -> {}, if Translate(base) is {} // -> Translate(base) with .pointerLevel -= 1 // Translate(+base) -> Translate(base) - Expected<DeclPointerLevels> VisitUnaryOperator(const UnaryOperator *E) { + Expected<DeclPointerLevelVec> VisitUnaryOperator(const UnaryOperator *E) { switch (E->getOpcode()) { case clang::UO_PostInc: case clang::UO_PostDec: @@ -163,7 +162,7 @@ class EntityPointerLevelTranslator case clang::UO_PreDec: return Visit(E->getSubExpr()); case clang::UO_AddrOf: { - Expected<DeclPointerLevels> SubResult = Visit(E->getSubExpr()); + Expected<DeclPointerLevelVec> SubResult = Visit(E->getSubExpr()); if (!SubResult) return SubResult.takeError(); @@ -184,32 +183,31 @@ class EntityPointerLevelTranslator // Translate((T*)base) -> Translate(base) if base has pointer type // -> {} otherwise - Expected<DeclPointerLevels> VisitCastExpr(const CastExpr *E) { + Expected<DeclPointerLevelVec> VisitCastExpr(const CastExpr *E) { if (hasPtrOrArrType(E->getSubExpr())) return Visit(E->getSubExpr()); - return DeclPointerLevels{}; + return DeclPointerLevelVec{}; } // Translate(f(...)) -> {} if it is an indirect call // -> {(f_return, 1)}, otherwise - Expected<DeclPointerLevels> VisitCallExpr(const CallExpr *E) { + Expected<DeclPointerLevelVec> VisitCallExpr(const CallExpr *E) { if (auto *FD = E->getDirectCallee()) - if (Extractor.addEntityForReturn(FD)) - return DeclPointerLevels{{FD, /*PointerLevel=*/1, /*IsReturn=*/true}}; - return DeclPointerLevels{}; + return DeclPointerLevelVec{{FD, /*PointerLevel=*/1, /*IsReturn=*/true}}; + return DeclPointerLevelVec{}; } // Translate(base[x]) -> Translate(*base) - Expected<DeclPointerLevels> + Expected<DeclPointerLevelVec> VisitArraySubscriptExpr(const ArraySubscriptExpr *E) { return translateDereferencePointer(E->getBase()); } // Translate(cond ? base1 : base2) := Translate(base1) U Translate(base2) - Expected<DeclPointerLevels> + Expected<DeclPointerLevelVec> VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) { - Expected<DeclPointerLevels> ReT = Visit(E->getTrueExpr()); - Expected<DeclPointerLevels> ReF = Visit(E->getFalseExpr()); + Expected<DeclPointerLevelVec> ReT = Visit(E->getTrueExpr()); + Expected<DeclPointerLevelVec> ReF = Visit(E->getFalseExpr()); if (ReT && ReF) { ReT->insert(ReT->end(), ReF->begin(), ReF->end()); @@ -222,94 +220,94 @@ class EntityPointerLevelTranslator return ReT.takeError(); } - Expected<DeclPointerLevels> VisitParenExpr(const ParenExpr *E) { + Expected<DeclPointerLevelVec> VisitParenExpr(const ParenExpr *E) { return Visit(E->getSubExpr()); } // Translate("string-literal") -> {} // no entity involved - Expected<DeclPointerLevels> VisitStringLiteral(const StringLiteral *E) { - return DeclPointerLevels{}; + Expected<DeclPointerLevelVec> VisitStringLiteral(const StringLiteral *E) { + return DeclPointerLevelVec{}; } // Translate(predefined-expr) -> {} // treated the same as string literals - Expected<DeclPointerLevels> VisitPredefinedExpr(const PredefinedExpr *E) { - return DeclPointerLevels{}; + Expected<DeclPointerLevelVec> VisitPredefinedExpr(const PredefinedExpr *E) { + return DeclPointerLevelVec{}; } // Translate(integer-literal) -> {} // no entity involved - Expected<DeclPointerLevels> VisitIntegerLiteral(const IntegerLiteral *E) { - return DeclPointerLevels{}; + Expected<DeclPointerLevelVec> VisitIntegerLiteral(const IntegerLiteral *E) { + return DeclPointerLevelVec{}; } // Translate(DRE) -> {(Decl, 1)} - Expected<DeclPointerLevels> VisitDeclRefExpr(const DeclRefExpr *E) { - return DeclPointerLevels{ + Expected<DeclPointerLevelVec> VisitDeclRefExpr(const DeclRefExpr *E) { + return DeclPointerLevelVec{ {E->getDecl(), /*PointerLevel=*/1, /*IsReturn=*/false}}; } // Translate({., ->}f) -> {(MemberDecl, 1)} - Expected<DeclPointerLevels> VisitMemberExpr(const MemberExpr *E) { - return DeclPointerLevels{ + Expected<DeclPointerLevelVec> VisitMemberExpr(const MemberExpr *E) { + return DeclPointerLevelVec{ {E->getMemberDecl(), /*PointerLevel=*/1, /*IsReturn=*/false}}; } // Unwrap CXXDefaultArgExpr - Expected<DeclPointerLevels> + Expected<DeclPointerLevelVec> VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E) { return Visit(E->getExpr()); } // Unwrap OpaqueValueExpr - Expected<DeclPointerLevels> VisitOpaqueValueExpr(const OpaqueValueExpr *S) { + Expected<DeclPointerLevelVec> VisitOpaqueValueExpr(const OpaqueValueExpr *S) { return Visit(S->getSourceExpr()); } // Unwrap ExprWithCleanups - Expected<DeclPointerLevels> VisitExprWithCleanups(const ExprWithCleanups *S) { + Expected<DeclPointerLevelVec> VisitExprWithCleanups(const ExprWithCleanups *S) { return Visit(S->getSubExpr()); } // Unwrap MaterializeTemporaryExpr - Expected<DeclPointerLevels> + Expected<DeclPointerLevelVec> VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) { return Visit(S->getSubExpr()); } // Unwrap CXXDefaultInitExpr - Expected<DeclPointerLevels> + Expected<DeclPointerLevelVec> VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *E) { return Visit(E->getExpr()); } // Translate(`nullptr`) -> {} - Expected<DeclPointerLevels> + Expected<DeclPointerLevelVec> VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *S) { - return DeclPointerLevels{}; + return DeclPointerLevelVec{}; } // Translate(`this`) -> {} - Expected<DeclPointerLevels> VisitCXXThisExpr(const CXXThisExpr *S) { - return DeclPointerLevels{}; + Expected<DeclPointerLevelVec> VisitCXXThisExpr(const CXXThisExpr *S) { + return DeclPointerLevelVec{}; } // Translate(`new`/`new [*]`) -> {} - Expected<DeclPointerLevels> VisitCXXNewExpr(const CXXNewExpr *S) { - return DeclPointerLevels{}; + Expected<DeclPointerLevelVec> VisitCXXNewExpr(const CXXNewExpr *S) { + return DeclPointerLevelVec{}; } // ImplicitValueInitExpr, for raw pointer type, // evaluates to a compile-time constant zero (or null). So no EPL in the // result. - Expected<DeclPointerLevels> + Expected<DeclPointerLevelVec> VisitImplicitValueInitExpr(const ImplicitValueInitExpr *S) { - return DeclPointerLevels{}; + return DeclPointerLevelVec{}; } // The InitListExpr must be an empty or singleton list that // initializes a pointer scalar. Other cases are unexpected thus an error. - Expected<DeclPointerLevels> VisitInitListExpr(const InitListExpr *E) { + Expected<DeclPointerLevelVec> VisitInitListExpr(const InitListExpr *E) { if (E->getNumInits() < 1) - return DeclPointerLevels{}; + return DeclPointerLevelVec{}; if (E->getType()->isPointerType()) return Visit(E->getInit(0)); return llvm::createStringError( @@ -322,22 +320,22 @@ class EntityPointerLevelTranslator // When a CXXConstructExpr has an array type, clang is initializing an array // of class-type objects with default values. In this case, no entity is // associated with the initializer. - Expected<DeclPointerLevels> VisitCXXConstructExpr(const CXXConstructExpr *E) { + Expected<DeclPointerLevelVec> VisitCXXConstructExpr(const CXXConstructExpr *E) { if (E->getType()->isArrayType()) { - return DeclPointerLevels{}; + return DeclPointerLevelVec{}; } return fallback(E); } // No entity is associated with a CXXScalarValueInitExpr: - Expected<DeclPointerLevels> + Expected<DeclPointerLevelVec> VisitCXXScalarValueInitExpr(const CXXScalarValueInitExpr *E) { - return DeclPointerLevels{}; + return DeclPointerLevelVec{}; } }; } // namespace clang::ssaf -Expected<DeclPointerLevels> +Expected<DeclPointerLevelVec> clang::ssaf::translateDeclPointerLevel(const Expr *E, ASTContext &Ctx, TUSummaryExtractor &Extractor) { EntityPointerLevelTranslator Translator(Extractor, Ctx); @@ -368,9 +366,9 @@ Expected<EntityPointerLevel> clang::ssaf::createEntityPointerLevel( return Translator.translate(ND, IsFunRet); } -DeclPointerLevels +DeclPointerLevelVec clang::ssaf::elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL) { - DeclPointerLevels Result{DPL}; + DeclPointerLevelVec Result{DPL}; QualType T; if (DPL.IsReturn) { @@ -384,22 +382,24 @@ clang::ssaf::elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL) { // Count the max pointer/array levels of `T`: unsigned MaxLevel = 0; - for (T = T.getCanonicalType();; ++MaxLevel) { + + T = T.getCanonicalType(); + while (!T.isNull() && (T->isPointerType() || T->isArrayType())) { if (const auto *PT = dyn_cast<PointerType>(T)) - T = PT->getPointeeType().getCanonicalType(); - else if (const auto *AT = dyn_cast<ArrayType>(T)) - T = AT->getElementType().getCanonicalType(); + T = PT->getPointeeType(); else - break; + T = cast<ArrayType>(T)->getElementType(); + ++MaxLevel; } - + assert(MaxLevel > 0); + Result.reserve(MaxLevel); for (unsigned Level = DPL.PointerLevel + 1; Level <= MaxLevel; ++Level) Result.push_back({DPL.Decl, Level, DPL.IsReturn}); return Result; } Expected<EntityPointerLevelSet> -clang::ssaf::toEntityPointerLevels(const DeclPointerLevels &DPLs, +clang::ssaf::toEntityPointerLevels(const DeclPointerLevelVec &DPLs, ASTContext &Ctx, TUSummaryExtractor &Extractor) { EntityPointerLevelTranslator Translator(Extractor, Ctx); diff --git a/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp b/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp index d9b5a347edb6c..3ab935a0a5ccb 100644 --- a/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp +++ b/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp @@ -10,68 +10,126 @@ #include "FindDecl.h" #include "clang/AST/Decl.h" #include "clang/Frontend/ASTUnit.h" +#include "clang/Frontend/SSAFOptions.h" +#include "clang/ScalableStaticAnalysis/Core/Model/BuildNamespace.h" +#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummary.h" +#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryBuilder.h" +#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h" #include "clang/Tooling/Tooling.h" +#include "llvm/Support/Error.h" +#include "llvm/Testing/Support/Error.h" #include "gmock/gmock.h" #include "gtest/gtest.h" #include <memory> -#include <vector> +#include <ostream> using namespace clang; using namespace ssaf; +using testing::AllOf; +using testing::Each; using testing::ElementsAre; +using testing::Field; +using testing::Matcher; +using testing::Property; +using testing::UnorderedElementsAre; + +namespace clang::ssaf { +// Let gmock print DeclPointerLevels by declaration name. Found by ADL, so it +// must live in the namespace of `DeclPointerLevel`. +void PrintTo(const DeclPointerLevel &DPL, std::ostream *OS) { + *OS << "DeclPointerLevel { Decl: '" + << (DPL.Decl ? DPL.Decl->getNameAsString() : "<null>") + << "', PointerLevel: " << DPL.PointerLevel + << ", IsReturn: " << (DPL.IsReturn ? "true" : "false") << " }"; +} +} // namespace clang::ssaf namespace { -static std::vector<unsigned> levelsOf(const DeclPointerLevels &DPLs) { - std::vector<unsigned> Levels; - for (const DeclPointerLevel &DPL : DPLs) - Levels.push_back(DPL.PointerLevel); - return Levels; +/// Matches a DeclPointerLevel at pointer level \p Level. +Matcher<const DeclPointerLevel &> hasPointerLevel(unsigned Level) { + return Field("PointerLevel", &DeclPointerLevel::PointerLevel, Level); +} + +/// Matches a DeclPointerLevel of \p ND, for the entity kind selected by +/// \p IsReturn. +Matcher<const DeclPointerLevel &> isLevelOfDecl(const NamedDecl *ND, + bool IsReturn) { + return AllOf(Field("Decl", &DeclPointerLevel::Decl, ND), + Field("IsReturn", &DeclPointerLevel::IsReturn, IsReturn)); +} + +/// Matches exactly the given pointer levels, in order. +template <typename... Levels> auto hasPointerLevels(Levels... Ls) { + return ElementsAre(hasPointerLevel(Ls)...); } +/// Elaborates the DeclPointerLevel of the \p DeclT named \p Name in \p Ctx, +/// starting at pointer level \p StartLevel, and checks that every result +/// belongs to that declaration. +template <typename DeclT = NamedDecl> +DeclPointerLevelVec elaborateFor(ASTContext &Ctx, StringRef Name, + unsigned StartLevel, bool IsReturn = false) { + const DeclT *ND = findDeclByName<DeclT>(Name, Ctx); + EXPECT_TRUE(ND) << "decl not found: " << Name.str(); + if (!ND) + return {}; + + DeclPointerLevelVec DPLs = elaborateHigherDeclPointerLevels( + DeclPointerLevel{ND, StartLevel, IsReturn}); + EXPECT_THAT(DPLs, Each(isLevelOfDecl(ND, IsReturn))); + return DPLs; +} + +/// Matches an EntityPointerLevel with the given entity and pointer level. +auto isEntityPointerLevel(EntityId Id, unsigned Level) { + return AllOf( + Property("getEntity", &EntityPointerLevel::getEntity, Id), + Property("getPointerLevel", &EntityPointerLevel::getPointerLevel, Level)); +} + +struct EntityPointerLevelTest : testing::Test { + SSAFOptions Opts; + TUSummary Summary{ + llvm::Triple("fake-unittest-triple"), + BuildNamespace(BuildNamespaceKind::CompilationUnit, "Mock.cpp")}; + TUSummaryBuilder Builder{Summary, Opts}; + TUSummaryExtractor Extractor{Builder}; +}; + // `elaborateHigherDeclPointerLevels` expands a DeclPointerLevel into an // ascending, exhaustive vector of DeclPointerLevels for the same declaration, // from the given level up to the maximum pointer level of the declared type. -TEST(EntityPointerLevelTest, ElaborateHigherDeclPointerLevels) { +TEST_F(EntityPointerLevelTest, ElaborateHigherDeclPointerLevels) { std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCodeWithArgs(R"cpp( int *p; // one pointer level int **q; // two pointer levels int ***r; // three pointer levels int *arr[10]; // array of pointers: two levels (array + pointer) + int mat[3][4]; // 2D array: two levels + typedef int *IP; + IP *pp; // sugar for `int **`: two levels )cpp", {"-Wno-unused"}); ASSERT_TRUE(AST); ASTContext &Ctx = AST->getASTContext(); - // Elaborate the decl named `Name` starting at `StartLevel`, checking that - // every result shares the input's declaration and is-return flag, and return - // the produced pointer levels. - auto elaborate = [&](StringRef Name, unsigned StartLevel) { - const NamedDecl *ND = findDeclByName(Name, Ctx); - EXPECT_NE(ND, nullptr) << "decl not found: " << Name.str(); - if (!ND) - return std::vector<unsigned>{}; - DeclPointerLevels DPLs = elaborateHigherDeclPointerLevels( - DeclPointerLevel{ND, StartLevel, /*IsReturn=*/false}); - for (const DeclPointerLevel &DPL : DPLs) { - EXPECT_TRUE(DPL.Decl == ND); - EXPECT_FALSE(DPL.IsReturn); - } - return levelsOf(DPLs); - }; - - EXPECT_THAT(elaborate("p", 1), ElementsAre(1U)); // int* - EXPECT_THAT(elaborate("q", 1), ElementsAre(1U, 2U)); // int** - EXPECT_THAT(elaborate("r", 1), ElementsAre(1U, 2U, 3U)); // int*** - EXPECT_THAT(elaborate("arr", 1), ElementsAre(1U, 2U)); // int*[10] - EXPECT_THAT(elaborate("r", 2), ElementsAre(2U, 3U)); - EXPECT_THAT(elaborate("r", 3), ElementsAre(3U)); + EXPECT_THAT(elaborateFor(Ctx, "p", 1), hasPointerLevels(1)); // int* + EXPECT_THAT(elaborateFor(Ctx, "q", 1), hasPointerLevels(1, 2)); // int** + EXPECT_THAT(elaborateFor(Ctx, "r", 1), hasPointerLevels(1, 2, 3)); // int*** + EXPECT_THAT(elaborateFor(Ctx, "arr", 1), hasPointerLevels(1, 2)); // int*[10] + EXPECT_THAT(elaborateFor(Ctx, "mat", 1), hasPointerLevels(1, 2)); // int[3][4] + EXPECT_THAT(elaborateFor(Ctx, "pp", 1), hasPointerLevels(1, 2)); // IP* + EXPECT_THAT(elaborateFor(Ctx, "r", 2), hasPointerLevels(2, 3)); + EXPECT_THAT(elaborateFor(Ctx, "r", 3), hasPointerLevels(3)); + // A level beyond the declared type's level count is preserved as is: + EXPECT_THAT(elaborateFor(Ctx, "p", 2), hasPointerLevels(2)); } // For a function entity (IsReturn=true), the maximum pointer level is bounded // by the return type, whose reference must be stripped first. -TEST(EntityPointerLevelTest, ElaborateHigherDeclPointerLevelsForReturn) { +TEST_F(EntityPointerLevelTest, ElaborateHigherDeclPointerLevelsForReturn) { std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCodeWithArgs(R"cpp( int **&refret(); // reference to int**: two pointer levels @@ -81,22 +139,45 @@ TEST(EntityPointerLevelTest, ElaborateHigherDeclPointerLevelsForReturn) { ASSERT_TRUE(AST); ASTContext &Ctx = AST->getASTContext(); - auto elaborateReturn = [&](StringRef Name, unsigned StartLevel) { - const FunctionDecl *FD = findFnByName(Name, Ctx); - EXPECT_NE(FD, nullptr) << "function not found: " << Name.str(); - if (!FD) - return std::vector<unsigned>{}; - DeclPointerLevels DPLs = elaborateHigherDeclPointerLevels( - DeclPointerLevel{FD, StartLevel, /*IsReturn=*/true}); - for (const DeclPointerLevel &DPL : DPLs) { - EXPECT_TRUE(DPL.Decl == FD); - EXPECT_TRUE(DPL.IsReturn); - } - return levelsOf(DPLs); - }; - - EXPECT_THAT(elaborateReturn("refret", 1), ElementsAre(1U, 2U)); // int**& - EXPECT_THAT(elaborateReturn("valret", 1), ElementsAre(1U)); // int* + EXPECT_THAT(elaborateFor<FunctionDecl>(Ctx, "refret", 1, /*IsReturn=*/true), + hasPointerLevels(1, 2)); // int**& + EXPECT_THAT(elaborateFor<FunctionDecl>(Ctx, "valret", 1, /*IsReturn=*/true), + hasPointerLevels(1)); // int* +} + +TEST_F(EntityPointerLevelTest, ToEntityPointerLevel) { + std::unique_ptr<ASTUnit> AST = + tooling::buildASTFromCodeWithArgs(R"cpp( + int ***p; + int **&refret(); + )cpp", + {"-Wno-unused"}); + ASSERT_TRUE(AST); + ASTContext &Ctx = AST->getASTContext(); + + const NamedDecl *ND = findDeclByName("p", Ctx); + ASSERT_TRUE(ND); + std::optional<EntityId> PId = Extractor.addEntity(ND); + ASSERT_TRUE(PId); + + const FunctionDecl *FD = findFnByName("refret", Ctx); + ASSERT_TRUE(FD); + std::optional<EntityId> RefretId = Extractor.addEntityForReturn(FD); + ASSERT_TRUE(RefretId); + + DeclPointerLevelVec DPLs = + elaborateHigherDeclPointerLevels({ND, 1, /*IsReturn=*/false}); + DeclPointerLevelVec ReturnDPLs = + elaborateHigherDeclPointerLevels({FD, 1, /*IsReturn=*/true}); + DPLs.append(ReturnDPLs.begin(), ReturnDPLs.end()); + DPLs.push_back(DPLs.front()); // duplicate, to exercise de-duplication + + ASSERT_THAT_EXPECTED( + toEntityPointerLevels(DPLs, Ctx, Extractor), + llvm::HasValue(UnorderedElementsAre( + isEntityPointerLevel(*PId, 1), isEntityPointerLevel(*PId, 2), + isEntityPointerLevel(*PId, 3), isEntityPointerLevel(*RefretId, 1), + isEntityPointerLevel(*RefretId, 2)))); } } // namespace >From 01a1a0850d423d73ae5aa61ec656b0c50348e056 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Fri, 28 Aug 2026 14:39:34 -0700 Subject: [PATCH 5/6] fix clang-format --- .../Analyses/EntityPointerLevel/EntityPointerLevel.h | 3 ++- .../Analyses/EntityPointerLevel/EntityPointerLevel.cpp | 6 ++++-- .../Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp | 2 +- 3 files changed, 7 insertions(+), 4 deletions(-) diff --git a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h index c3bb3b13acd2d..6e8971bd2eb8d 100644 --- a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h +++ b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h @@ -151,7 +151,8 @@ createEntityPointerLevel(const NamedDecl *ND, TUSummaryExtractor &Extractor, /// ascending order of pointer levels. All elements are identical to \p DPL /// except with a pointer level greater than or equal to that of \p DPL. The /// pointer level of each element is bounded by the type of \p DPL's NamedDecl. -DeclPointerLevelVec elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL); +DeclPointerLevelVec +elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL); /// Creates a new EntityPointerLevel (EPL) from `E` by incrementing `E`'s /// pointer level. diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp index e337e37577ec7..83786185de06e 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp @@ -263,7 +263,8 @@ class EntityPointerLevelTranslator } // Unwrap ExprWithCleanups - Expected<DeclPointerLevelVec> VisitExprWithCleanups(const ExprWithCleanups *S) { + Expected<DeclPointerLevelVec> + VisitExprWithCleanups(const ExprWithCleanups *S) { return Visit(S->getSubExpr()); } @@ -320,7 +321,8 @@ class EntityPointerLevelTranslator // When a CXXConstructExpr has an array type, clang is initializing an array // of class-type objects with default values. In this case, no entity is // associated with the initializer. - Expected<DeclPointerLevelVec> VisitCXXConstructExpr(const CXXConstructExpr *E) { + Expected<DeclPointerLevelVec> + VisitCXXConstructExpr(const CXXConstructExpr *E) { if (E->getType()->isArrayType()) { return DeclPointerLevelVec{}; } diff --git a/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp b/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp index 3ab935a0a5ccb..4c1e4c6bae361 100644 --- a/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp +++ b/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp @@ -69,7 +69,7 @@ template <typename... Levels> auto hasPointerLevels(Levels... Ls) { /// belongs to that declaration. template <typename DeclT = NamedDecl> DeclPointerLevelVec elaborateFor(ASTContext &Ctx, StringRef Name, - unsigned StartLevel, bool IsReturn = false) { + unsigned StartLevel, bool IsReturn = false) { const DeclT *ND = findDeclByName<DeclT>(Name, Ctx); EXPECT_TRUE(ND) << "decl not found: " << Name.str(); if (!ND) >From 7079c4b92ff75894fc39150895e5e075e415477a Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Fri, 28 Aug 2026 15:44:02 -0700 Subject: [PATCH 6/6] address comments --- .../PointerFlow/PointerFlowExtractor.cpp | 31 ++++++++++--------- 1 file changed, 17 insertions(+), 14 deletions(-) diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp index 3b9b225a52d0a..719929bd7d43a 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp @@ -54,10 +54,10 @@ class PointerFlowMatcher { llvm::Error matchesDecl(const Decl *D, const NamedDecl *RootDecl); private: - llvm::Error addEdges(Expected<DeclPointerLevels> &&LHS, - Expected<DeclPointerLevels> &&RHS); + llvm::Error addEdges(Expected<DeclPointerLevelVec> &&LHS, + Expected<DeclPointerLevelVec> &&RHS); - Expected<DeclPointerLevels> toDPL(const Expr *N) const { + Expected<DeclPointerLevelVec> toDPL(const Expr *N) const { return translateDeclPointerLevel(N, Ctx, Extractor); } @@ -75,7 +75,7 @@ class PointerFlowMatcher { ++ArgIdx, ++ParmIdx) { if (const ParmVarDecl *PD = PP->getParamDecl(ParmIdx); PD && hasPtrOrArrType(PD)) { - if (auto Err = addEdges(DeclPointerLevels{toDPL(PD)}, + if (auto Err = addEdges(DeclPointerLevelVec{toDPL(PD)}, toDPL(AP->getArg(ArgIdx)))) return Err; } @@ -84,8 +84,8 @@ class PointerFlowMatcher { } }; -llvm::Error PointerFlowMatcher::addEdges(Expected<DeclPointerLevels> &&LHS, - Expected<DeclPointerLevels> &&RHS) { +llvm::Error PointerFlowMatcher::addEdges(Expected<DeclPointerLevelVec> &&LHS, + Expected<DeclPointerLevelVec> &&RHS) { if (!LHS && !RHS) return llvm::joinErrors(LHS.takeError(), RHS.takeError()); if (!LHS) @@ -95,10 +95,12 @@ llvm::Error PointerFlowMatcher::addEdges(Expected<DeclPointerLevels> &&LHS, if (RHS->empty()) return llvm::Error::success(); - std::vector<DeclPointerLevels> LVecs, RVecs; + std::vector<DeclPointerLevelVec> LVecs, RVecs; + LVecs.reserve(LHS->size()); for (const auto &L : *LHS) LVecs.push_back(elaborateHigherDeclPointerLevels(L)); + RVecs.reserve(RHS->size()); for (const auto &R : *RHS) RVecs.push_back(elaborateHigherDeclPointerLevels(R)); @@ -113,10 +115,11 @@ llvm::Error PointerFlowMatcher::addEdges(Expected<DeclPointerLevels> &&LHS, // Note that type checking ensures that 'p' and 'q' have // identical pointer levels, but '(a, n)' and '(b, m)' may have different // upper bounds on their pointer levels, when, for example, 'q' is a - // cast-expression. + // reinterpret-cast expression, which can have different pointer level than + // its sub-expression. - for (const DeclPointerLevels &L : LVecs) - for (const DeclPointerLevels &R : RVecs) + for (const DeclPointerLevelVec &L : LVecs) + for (const DeclPointerLevelVec &R : RVecs) for (const auto &[LDPL, RDPL] : llvm::zip(L, R)) { auto LEPL = toEntityPointerLevel(LDPL, Ctx, Extractor); if (!LEPL) @@ -185,7 +188,7 @@ llvm::Error PointerFlowMatcher::matchesStmt(const Stmt *S, const Expr *RetExpr = RS->getRetValue(); if (!RetExpr || !hasPtrOrArrType(RetExpr)) return llvm::Error::success(); - return addEdges(DeclPointerLevels{toDPL(RootDecl, true)}, toDPL(RetExpr)); + return addEdges(DeclPointerLevelVec{toDPL(RootDecl, true)}, toDPL(RetExpr)); } return llvm::Error::success(); } @@ -206,7 +209,7 @@ llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D, // Match initializers to variables/fields of a pointer type: if (InitExpr && hasPtrOrArrType(VD)) - return addEdges(DeclPointerLevels{toDPL(VD)}, toDPL(InitExpr)); + return addEdges(DeclPointerLevelVec{toDPL(VD)}, toDPL(InitExpr)); } // Match C++ constructor member-initializers: @@ -215,7 +218,7 @@ llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D, if (E->isDelegatingInitializer()) return matches(DynTypedNode::create(*E->getInit()), RootDecl); if (const FieldDecl *FD = E->getMember(); FD && hasPtrOrArrType(FD)) { - if (auto Err = addEdges(DeclPointerLevels{toDPL(E->getMember())}, + if (auto Err = addEdges(DeclPointerLevelVec{toDPL(E->getMember())}, toDPL(E->getInit()))) return Err; } @@ -295,7 +298,7 @@ PointerFlowMatcher::matchesInitializerList(const ValueDecl *Base, auto BaseDPL = toDPL(Base); // Apply ArrayElementIndirectLevel to BaseDPL BaseDPL.PointerLevel += ArrayElementIndirectLevel; - return addEdges(DeclPointerLevels{BaseDPL}, toDPL(InitExpr)); + return addEdges(DeclPointerLevelVec{BaseDPL}, toDPL(InitExpr)); } // Note that `Base`'s type is NOT the real LHS type when // ArrayElementIndirectLevel > 0: _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
