Author: Ziqing Luo Date: 2026-08-29T16:35:10-07:00 New Revision: deebdb554054078888e5551917e5fb01a8690426
URL: https://github.com/llvm/llvm-project/commit/deebdb554054078888e5551917e5fb01a8690426 DIFF: https://github.com/llvm/llvm-project/commit/deebdb554054078888e5551917e5fb01a8690426.diff LOG: [SSAF][EntityPointerLevel] Add an intermediate data structure DeclPointerLevel (#218196) This is the first of three patches aimed at solving a non-termination problem when using DFS in the pointer-flow graph. Problem & context: Currently, the pointer-flow graph creates exactly one edge corresponding to an assignment in the source code. For example, a pointer assignment `p = q;` results in an edge `(p, i) -> (q, j)` for some pointer levels `i` and `j`. In unsafe buffer propagation, this edge encodes the meaning that if `p` is bounded, `q` must also be bounded. Additionally, if `*p/p[x]` is bounded, `*q/q[y]` must be bounded, and so on until the maximum pointer level of `p` or `q` is reached. Because of this, during DFS, a node `(p, i+1)` can reach `(q, j+1)` through the edge `(p, i) -> (q, j)`. This logic is correct only when `p` and `q` have compatible types, which is true for most cases due to standard type checking. However, this assumption breaks down with pointer casts. A cast like `a = (T)b` contributes an edge `(a, x) -> (b, y)` where `a` and `b` do not have compatible types. Consequently, the graph can contain cycles such as `(a, 1) -> (b, 2)` and `(b, 1) -> (a, 2)`. Because type information is abstracted out during DFS, we do not know the exact pointer level upper bounds to limit this growth, causing the DFS to loop indefinitely as pointer levels keep growing. Solution: To fix this, the pointer-flow graph must explicitly include the finite set of edges encoded by each assignment. Since type information is available during graph construction, we can use it to compute upper bounds. Consequently, the graph search can go back to being simple and guaranteed to terminate. As a first step toward that solution, this patch introduces a new data structure: `DeclPointerLevel`. A `DeclPointerLevel` differs from an `EntityPointerLevel` only in that it retains the AST Decl node instead of directly abstracting it to an Entity. The AST node carries crucial information, such as types, which can be used by extractors before converting `DeclPointerLevels` to `EntityPointerLevels`. First step for: rdar://183529483 --------- Co-authored-by: Balázs Benics <[email protected]> Added: clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp Modified: clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp clang/unittests/ScalableStaticAnalysis/CMakeLists.txt Removed: ################################################################################ diff --git a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h index c296016258f8d..6e8971bd2eb8d 100644 --- a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h +++ b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h @@ -11,11 +11,22 @@ #include "clang/AST/Expr.h" #include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h" +#include "llvm/ADT/SmallVector.h" #include <set> 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 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 /// declared type, a EntityPointerLevel is associated with a '*' (or a '[]`) in @@ -90,16 +101,41 @@ 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 \c translateEntityPointerLevel, except it returns raw +/// `(NamedDecl *, pointer level, is-return)` tuples (a.k.a. DeclPointerLevels) +/// instead of assembling an `EntityPointerLevelSet` directly. +llvm::Expected<DeclPointerLevelVec> +translateDeclPointerLevel(const Expr *E, ASTContext &Ctx, + TUSummaryExtractor &Extractor); + +/// Assemble `DeclPointerLevels` into an `EntityPointerLevelSet`. +Expected<EntityPointerLevelSet> +toEntityPointerLevels(const DeclPointerLevelVec &DPLs, ASTContext &Ctx, + TUSummaryExtractor &Extractor); + +/// Convert a single `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 +147,13 @@ llvm::Expected<EntityPointerLevel> createEntityPointerLevel(const NamedDecl *ND, TUSummaryExtractor &Extractor, bool IsFunRet = false); +/// \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. /// \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..83786185de06e 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp @@ -14,6 +14,7 @@ #include "clang/AST/ExprCXX.h" #include "clang/AST/StmtVisitor.h" #include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h" +#include "llvm/ADT/STLExtras.h" #include <optional> using namespace clang; @@ -41,11 +42,11 @@ namespace clang::ssaf { // Translate(&arr[5]) -> {(arr, 1)} class EntityPointerLevelTranslator : ConstStmtVisitor<EntityPointerLevelTranslator, - Expected<EntityPointerLevelSet>> { + Expected<DeclPointerLevelVec>> { friend class StmtVisitorBase; // Fallback method for all unsupported expression kind: - Expected<EntityPointerLevelSet> 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 @@ -55,7 +56,7 @@ class EntityPointerLevelTranslator return makeErrAtNode(Ctx, E, "attempt to translate %s to EntityPointerLevels", E->getStmtClassName()); - return EntityPointerLevelSet{}; + return DeclPointerLevelVec{}; } Expected<EntityPointerLevel> @@ -79,15 +80,15 @@ class EntityPointerLevelTranslator // The common helper function for Translate(*base): // Translate(*base) -> Translate(base) with .pointerLevel + 1 - Expected<EntityPointerLevelSet> translateDereferencePointer(const Expr *Ptr) { + Expected<DeclPointerLevelVec> translateDereferencePointer(const Expr *Ptr) { assert(hasPtrOrArrType(Ptr)); - Expected<EntityPointerLevelSet> SubResult = Visit(Ptr); + Expected<DeclPointerLevelVec> 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 +98,7 @@ class EntityPointerLevelTranslator EntityPointerLevelTranslator(TUSummaryExtractor &Extractor, ASTContext &Ctx) : Extractor(Extractor), Ctx(Ctx) {} - Expected<EntityPointerLevelSet> 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); @@ -109,26 +110,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<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<EntityPointerLevelSet> VisitBinaryOperator(const BinaryOperator *E) { + Expected<DeclPointerLevelVec> VisitBinaryOperator(const BinaryOperator *E) { switch (E->getOpcode()) { case clang::BO_Add: if (hasPtrOrArrType(E->getLHS())) @@ -152,7 +154,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<DeclPointerLevelVec> VisitUnaryOperator(const UnaryOperator *E) { switch (E->getOpcode()) { case clang::UO_PostInc: case clang::UO_PostDec: @@ -160,12 +162,15 @@ class EntityPointerLevelTranslator case clang::UO_PreDec: return Visit(E->getSubExpr()); case clang::UO_AddrOf: { - Expected<EntityPointerLevelSet> SubResult = Visit(E->getSubExpr()); + Expected<DeclPointerLevelVec> 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 +183,34 @@ class EntityPointerLevelTranslator // Translate((T*)base) -> Translate(base) if base has pointer type // -> {} otherwise - Expected<EntityPointerLevelSet> VisitCastExpr(const CastExpr *E) { + Expected<DeclPointerLevelVec> VisitCastExpr(const CastExpr *E) { if (hasPtrOrArrType(E->getSubExpr())) return Visit(E->getSubExpr()); - return EntityPointerLevelSet{}; + return DeclPointerLevelVec{}; } // 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<DeclPointerLevelVec> VisitCallExpr(const CallExpr *E) { + if (auto *FD = E->getDirectCallee()) + return DeclPointerLevelVec{{FD, /*PointerLevel=*/1, /*IsReturn=*/true}}; + return DeclPointerLevelVec{}; } // Translate(base[x]) -> Translate(*base) - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitArraySubscriptExpr(const ArraySubscriptExpr *E) { return translateDereferencePointer(E->getBase()); } // Translate(cond ? base1 : base2) := Translate(base1) U Translate(base2) - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) { - Expected<EntityPointerLevelSet> ReT = Visit(E->getTrueExpr()); - Expected<EntityPointerLevelSet> ReF = Visit(E->getFalseExpr()); + Expected<DeclPointerLevelVec> ReT = Visit(E->getTrueExpr()); + Expected<DeclPointerLevelVec> 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 +220,95 @@ class EntityPointerLevelTranslator return ReT.takeError(); } - Expected<EntityPointerLevelSet> VisitParenExpr(const ParenExpr *E) { + Expected<DeclPointerLevelVec> VisitParenExpr(const ParenExpr *E) { return Visit(E->getSubExpr()); } // Translate("string-literal") -> {} // no entity involved - Expected<EntityPointerLevelSet> VisitStringLiteral(const StringLiteral *E) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevelVec> VisitStringLiteral(const StringLiteral *E) { + return DeclPointerLevelVec{}; } // Translate(predefined-expr) -> {} // treated the same as string literals - Expected<EntityPointerLevelSet> VisitPredefinedExpr(const PredefinedExpr *E) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevelVec> VisitPredefinedExpr(const PredefinedExpr *E) { + return DeclPointerLevelVec{}; } // Translate(integer-literal) -> {} // no entity involved - Expected<EntityPointerLevelSet> VisitIntegerLiteral(const IntegerLiteral *E) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevelVec> VisitIntegerLiteral(const IntegerLiteral *E) { + return DeclPointerLevelVec{}; } // Translate(DRE) -> {(Decl, 1)} - Expected<EntityPointerLevelSet> VisitDeclRefExpr(const DeclRefExpr *E) { - auto Res = createEntityPointerLevelFor(E->getDecl()); - if (!Res) - return Res.takeError(); - return EntityPointerLevelSet{*Res}; + Expected<DeclPointerLevelVec> VisitDeclRefExpr(const DeclRefExpr *E) { + return DeclPointerLevelVec{ + {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<DeclPointerLevelVec> VisitMemberExpr(const MemberExpr *E) { + return DeclPointerLevelVec{ + {E->getMemberDecl(), /*PointerLevel=*/1, /*IsReturn=*/false}}; } // Unwrap CXXDefaultArgExpr - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E) { return Visit(E->getExpr()); } // Unwrap OpaqueValueExpr - Expected<EntityPointerLevelSet> - VisitOpaqueValueExpr(const OpaqueValueExpr *S) { + Expected<DeclPointerLevelVec> VisitOpaqueValueExpr(const OpaqueValueExpr *S) { return Visit(S->getSourceExpr()); } // Unwrap ExprWithCleanups - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitExprWithCleanups(const ExprWithCleanups *S) { return Visit(S->getSubExpr()); } // Unwrap MaterializeTemporaryExpr - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) { return Visit(S->getSubExpr()); } // Unwrap CXXDefaultInitExpr - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *E) { return Visit(E->getExpr()); } // Translate(`nullptr`) -> {} - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *S) { - return EntityPointerLevelSet{}; + return DeclPointerLevelVec{}; } // Translate(`this`) -> {} - Expected<EntityPointerLevelSet> VisitCXXThisExpr(const CXXThisExpr *S) { - return EntityPointerLevelSet{}; + Expected<DeclPointerLevelVec> VisitCXXThisExpr(const CXXThisExpr *S) { + return DeclPointerLevelVec{}; } // Translate(`new`/`new [*]`) -> {} - Expected<EntityPointerLevelSet> VisitCXXNewExpr(const CXXNewExpr *S) { - return EntityPointerLevelSet{}; + 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<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitImplicitValueInitExpr(const ImplicitValueInitExpr *S) { - return EntityPointerLevelSet{}; + return DeclPointerLevelVec{}; } // 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<DeclPointerLevelVec> VisitInitListExpr(const InitListExpr *E) { if (E->getNumInits() < 1) - return EntityPointerLevelSet{}; + return DeclPointerLevelVec{}; if (E->getType()->isPointerType()) return Visit(E->getInit(0)); return llvm::createStringError( @@ -323,28 +321,43 @@ 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> + Expected<DeclPointerLevelVec> VisitCXXConstructExpr(const CXXConstructExpr *E) { if (E->getType()->isArrayType()) { - return EntityPointerLevelSet{}; + return DeclPointerLevelVec{}; } return fallback(E); } // No entity is associated with a CXXScalarValueInitExpr: - Expected<EntityPointerLevelSet> + Expected<DeclPointerLevelVec> VisitCXXScalarValueInitExpr(const CXXScalarValueInitExpr *E) { - return EntityPointerLevelSet{}; + return DeclPointerLevelVec{}; } }; } // namespace clang::ssaf +Expected<DeclPointerLevelVec> +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,61 @@ Expected<EntityPointerLevel> clang::ssaf::createEntityPointerLevel( return Translator.translate(ND, IsFunRet); } +DeclPointerLevelVec +clang::ssaf::elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL) { + DeclPointerLevelVec 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; + + T = T.getCanonicalType(); + while (!T.isNull() && (T->isPointerType() || T->isArrayType())) { + if (const auto *PT = dyn_cast<PointerType>(T)) + T = PT->getPointeeType(); + else + 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 DeclPointerLevelVec &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..4c1e4c6bae361 --- /dev/null +++ b/clang/unittests/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelTest.cpp @@ -0,0 +1,183 @@ +//===- 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/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 <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 { + +/// 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_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(); + + 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_F(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(); + + 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 diff --git a/clang/unittests/ScalableStaticAnalysis/CMakeLists.txt b/clang/unittests/ScalableStaticAnalysis/CMakeLists.txt index 0f3bf9ad4512b..8c339bee60f63 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 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
