wyt updated this revision to Diff 452965. wyt added a comment. Propagate change from parent patch.
Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D131616/new/ https://reviews.llvm.org/D131616 Files: clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp clang/unittests/Analysis/FlowSensitive/CMakeLists.txt clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp =================================================================== --- clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp +++ clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp @@ -5,12 +5,6 @@ // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// -// -// This file defines a simplistic version of Constant Propagation as an example -// of a forward, monotonic dataflow analysis. The analysis tracks all -// variables in the scope, but lacks escape analysis. -// -//===----------------------------------------------------------------------===// #include "clang/Analysis/FlowSensitive/MatchSwitch.h" #include "TestingSupport.h" Index: clang/unittests/Analysis/FlowSensitive/CMakeLists.txt =================================================================== --- clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -4,6 +4,7 @@ ) add_clang_unittest(ClangAnalysisFlowSensitiveTests + CFGMatchSwitchTest.cpp ChromiumCheckModelTest.cpp DataflowAnalysisContextTest.cpp DataflowEnvironmentTest.cpp Index: clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp =================================================================== --- /dev/null +++ clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp @@ -0,0 +1,132 @@ +//===- unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp ------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/FlowSensitive/CFGMatchSwitch.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" +#include "clang/AST/Stmt.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/Analysis/CFG.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/StringRef.h" +#include "gtest/gtest.h" +#include <cstdint> +#include <memory> +#include <ostream> +#include <string> +#include <utility> + +using namespace clang; +using namespace dataflow; +using namespace ast_matchers; + +namespace { +// State for tracking the number of matches on each kind of CFGElement by the +// CFGMatchSwitch. Currently only tracks CFGStmt and CFGInitializer. +struct CFGElementMatches { + unsigned int StmtMatches = 0; + unsigned int InitializerMatches = 0; +}; + +// Returns a match switch that counts the number of local variables +// (singly-declared) and fields initialized to the integer literal 42. +auto buildCFGMatchSwitch() { + return CFGMatchSwitchBuilder<CFGElementMatches>() + .CaseOfCFGStmt<DeclStmt>( + declStmt(hasSingleDecl( + varDecl(hasInitializer(integerLiteral(equals(42)))))), + [](const DeclStmt *, const MatchFinder::MatchResult &, + CFGElementMatches &Counter) { Counter.StmtMatches++; }) + .CaseOfCFGInit<CXXCtorInitializer>( + cxxCtorInitializer(withInitializer(integerLiteral(equals(42)))), + [](const CXXCtorInitializer *, const MatchFinder::MatchResult &, + CFGElementMatches &Counter) { Counter.InitializerMatches++; }) + .Build(); +} + +// Runs the match switch `MS` on the control flow graph generated from `Code`, +// tracking information in state `S`. For simplicity, this test utility is +// restricted to CFGs with a single control flow block (excluding entry and +// exit blocks) - generated by `Code` with sequential flow (i.e. no branching). +// +// Requirements: +// +// `Code` must contain a function named `f`, the body of this function will be +// used to generate the CFG. +template <typename State> +void applySwitchToCode(CFGMatchSwitch<State> &MS, State &S, + llvm::StringRef Code) { + auto Unit = tooling::buildASTFromCodeWithArgs(Code, {"-Wno-unused-value"}); + auto &Ctx = Unit->getASTContext(); + const auto *F = selectFirst<FunctionDecl>( + "f", match(functionDecl(isDefinition(), hasName("f")).bind("f"), Ctx)); + + CFG::BuildOptions BO; + BO.AddInitializers = true; + + auto CFG = CFG::buildCFG(F, F->getBody(), &Ctx, BO); + auto CFGBlock = *CFG->getEntry().succ_begin(); + for (auto &Elt : CFGBlock->Elements) { + MS(Elt, Ctx, S); + } +} + +TEST(CFGMatchSwitchTest, NoInitializationTo42) { + CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch(); + CFGElementMatches Counter; + applySwitchToCode(Switch, Counter, R"( + void f() { + 42; + } + )"); + EXPECT_EQ(Counter.StmtMatches, 0); + EXPECT_EQ(Counter.InitializerMatches, 0); +} + +TEST(CFGMatchSwitchTest, SingleLocalVarInitializationTo42) { + CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch(); + CFGElementMatches Counter; + applySwitchToCode(Switch, Counter, R"( + void f() { + int i = 42; + } + )"); + EXPECT_EQ(Counter.StmtMatches, 1); + EXPECT_EQ(Counter.InitializerMatches, 0); +} + +TEST(CFGMatchSwitchTest, SingleFieldInitializationTo42) { + CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch(); + CFGElementMatches Counter; + applySwitchToCode(Switch, Counter, R"( + struct f { + int i; + f(): i(42) {} + }; + )"); + EXPECT_EQ(Counter.StmtMatches, 0); + EXPECT_EQ(Counter.InitializerMatches, 1); +} + +TEST(CFGMatchSwitchTest, LocalVarAndFieldInitializationTo42) { + CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch(); + CFGElementMatches Counter; + applySwitchToCode(Switch, Counter, R"( + struct f { + int i; + f(): i(42) { + int j = 42; + } + }; + )"); + EXPECT_EQ(Counter.StmtMatches, 1); + EXPECT_EQ(Counter.InitializerMatches, 1); +} +} // namespace Index: clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h =================================================================== --- clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -127,7 +127,7 @@ /// dataflow analysis states that model the respective basic blocks. Indices of /// the returned vector correspond to basic block IDs. Returns an error if the /// dataflow analysis cannot be performed successfully. Otherwise, calls -/// `PostVisitCFG` on each CFG element with the final analysis results at that +/// `PostVisitCFG` on each element with the final analysis results at that /// program point. llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>> runTypeErasedDataflowAnalysis( Index: clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h =================================================================== --- clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h +++ clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h @@ -44,23 +44,34 @@ Environment &Env; }; -/// Matches against `Stmt` and, based on its structure, dispatches to an -/// appropriate handler. +template <typename T> using MSMatcherT = ast_matchers::internal::Matcher<T>; + +template <typename T, typename State, typename Result = void> +using MSActionT = std::function<Result( + const T *, const ast_matchers::MatchFinder::MatchResult &, State &)>; + +template <typename BaseT, typename State, typename Result = void> +using ASTMatchSwitch = + std::function<Result(const BaseT &, ASTContext &, State &)>; + +// FIXME: Remove this alias when all usages of `MatchSwitch` are updated to +// `ASTMatchSwitch<Stmt>`. template <typename State, typename Result = void> -using MatchSwitch = std::function<Result(const Stmt &, ASTContext &, State &)>; +using MatchSwitch = ASTMatchSwitch<Stmt, State, Result>; /// Collects cases of a "match switch": a collection of matchers paired with -/// callbacks, which together define a switch that can be applied to a -/// `Stmt`. This structure can simplify the definition of `transfer` functions -/// that rely on pattern-matching. +/// callbacks, which together define a switch that can be applied to a node +/// whose type can be derived from `BaseT`. This structure can simplify the +/// definition of `transfer` functions that rely on pattern-matching. /// /// For example, consider an analysis that handles particular function calls. It -/// can define the `MatchSwitch` once, in the constructor of the analysis, and -/// then reuse it each time that `transfer` is called, with a fresh state value. +/// can define the `ASTMatchSwitch` once, in the constructor of the analysis, +/// and then reuse it each time that `transfer` is called, with a fresh state +/// value. /// /// \code -/// MatchSwitch<TransferState<MyLattice> BuildSwitch() { -/// return MatchSwitchBuilder<TransferState<MyLattice>>() +/// ASTMatchSwitch<Stmt, TransferState<MyLattice> BuildSwitch() { +/// return ASTMatchSwitchBuilder<TransferState<MyLattice>>() /// .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall) /// .CaseOf(callExpr(argumentCountIs(2), /// callee(functionDecl(hasName("bar")))), @@ -68,35 +79,33 @@ /// .Build(); /// } /// \endcode -template <typename State, typename Result = void> class MatchSwitchBuilder { +template <typename BaseT, typename State, typename Result = void> +class ASTMatchSwitchBuilder { public: /// Registers an action that will be triggered by the match of a pattern /// against the input statement. /// /// Requirements: /// - /// `Node` should be a subclass of `Stmt`. - template <typename Node> - MatchSwitchBuilder && - CaseOf(ast_matchers::internal::Matcher<Stmt> M, - std::function<Result(const Node *, - const ast_matchers::MatchFinder::MatchResult &, - State &)> - A) && { + /// `NodeT` should be derivable from `BaseT`. + template <typename NodeT> + ASTMatchSwitchBuilder CaseOf(MSMatcherT<BaseT> M, + MSActionT<NodeT, State, Result> A) { Matchers.push_back(std::move(M)); Actions.push_back( - [A = std::move(A)](const Stmt *Stmt, + [A = std::move(A)](const BaseT *Node, const ast_matchers::MatchFinder::MatchResult &R, - State &S) { return A(cast<Node>(Stmt), R, S); }); + State &S) { return A(cast<NodeT>(Node), R, S); }); return std::move(*this); } - MatchSwitch<State, Result> Build() && { + ASTMatchSwitch<BaseT, State, Result> Build() { return [Matcher = BuildMatcher(), Actions = std::move(Actions)]( - const Stmt &Stmt, ASTContext &Context, State &S) -> Result { - auto Results = ast_matchers::matchDynamic(Matcher, Stmt, Context); - if (Results.empty()) + const BaseT &Node, ASTContext &Context, State &S) -> Result { + auto Results = ast_matchers::matchDynamic(Matcher, Node, Context); + if (Results.empty()) { return Result(); + } // Look through the map for the first binding of the form "TagN..." use // that to select the action. for (const auto &Element : Results[0].getMap()) { @@ -105,7 +114,7 @@ if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) && Index < Actions.size()) { return Actions[Index]( - &Stmt, + &Node, ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S); } } @@ -137,15 +146,20 @@ // The matcher type on the cases ensures that `Expr` kind is compatible with // all of the matchers. return DynTypedMatcher::constructVariadic( - DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<Stmt>(), + DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<BaseT>(), std::move(Matchers)); } +public: std::vector<ast_matchers::internal::DynTypedMatcher> Matchers; - std::vector<std::function<Result( - const Stmt *, const ast_matchers::MatchFinder::MatchResult &, State &)>> - Actions; + std::vector<MSActionT<BaseT, State, Result>> Actions; }; + +// FIXME: Remove this alias when all usages of `MatchSwitchBuilder` are updated +// to `ASTMatchSwitchBuilder<Stmt>`. +template <typename State, typename Result = void> +using MatchSwitchBuilder = ASTMatchSwitchBuilder<Stmt, State, Result>; + } // namespace dataflow } // namespace clang #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h =================================================================== --- clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -93,7 +93,7 @@ return L1 == L2; } - /// Deprecated. Use the more general `transferCFGElement` function. + /// To deprecate. Use the more general `transferCFGElement` function. /// /// Transfer function for statements in the code being analysed. virtual void transfer(const Stmt *Stmt, Lattice &L, Environment &Env) {} @@ -103,16 +103,12 @@ virtual void transferCFGElement(const CFGElement *Element, Lattice &L, Environment &Env) {} - // FIXME: Use CRTP pattern and remove virtual transfer functions after users - // have been updated to implement transferCFGElement. - // (e.g. static_cast<Derived*>(this)->transferCFGElement(Element, L, Env)) void transferTypeErased(const CFGElement *Element, TypeErasedLattice &E, Environment &Env) final { Lattice &L = llvm::any_cast<Lattice &>(E.Value); transferCFGElement(Element, L, Env); - // FIXME: Remove after users have been updated to implement - // transferCFGElement. + // To deprecate. if (auto Stmt = Element->getAs<CFGStmt>()) { transfer(Stmt->getStmt(), L, Env); } Index: clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h @@ -0,0 +1,100 @@ +//===---- CFGMatchSwitch.h --------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the `CFGMatchSwitch` abstraction for building a "switch" +// statement for control flow graph elements. Each case of the switch is +// defined by an ASTMatcher which is applied on the AST node contained in the +// input `CFGElement`. +// +// Currently, the `CFGMatchSwitch` only handles `CFGElement`s of +// `Kind::Statement` and `Kind::Initializer`. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_ +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_ + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Stmt.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/MatchSwitch.h" +#include "llvm/ADT/StringRef.h" +#include <functional> +#include <string> +#include <utility> +#include <vector> + +namespace clang { +namespace dataflow { + +template <typename State, typename Result = void> +using CFGMatchSwitch = + std::function<Result(const CFGElement &, ASTContext &, State &)>; + +/// Collects cases of a "match switch": a collection of matchers paired with +/// callbacks, which together define a switch that can be applied to an AST node +/// contained in a CFG element. +template <typename State, typename Result = void> class CFGMatchSwitchBuilder { +public: + /// Registers an action `A` for `CFGStmt`s that will be triggered by the match + /// of the pattern `M` against the `Stmt` contained in the input `CFGStmt`. + /// + /// Requirements: + /// + /// `NodeT` should be derivable from `Stmt`. + template <typename NodeT> + CFGMatchSwitchBuilder CaseOfCFGStmt(MSMatcherT<Stmt> M, + MSActionT<NodeT, State, Result> A) { + StmtBuilder = StmtBuilder.template CaseOf<NodeT>(M, A); + return std::move(*this); + } + + /// Registers an action `A` for `CFGInitializer`s that will be triggered by + /// the match of the pattern `M` against the `CXXCtorInitializer` contained in + /// the input `CFGInitializer`. + /// + /// Requirements: + /// + /// `NodeT` should be derivable from `CXXCtorInitializer`. + template <typename NodeT> + CFGMatchSwitchBuilder CaseOfCFGInit(MSMatcherT<CXXCtorInitializer> M, + MSActionT<NodeT, State, Result> A) { + InitBuilder = InitBuilder.template CaseOf<NodeT>(M, A); + return std::move(*this); + } + + CFGMatchSwitch<State, Result> Build() && { + return [StmtMS = StmtBuilder.Build(), InitMS = InitBuilder.Build()]( + const CFGElement &Element, ASTContext &Context, + State &S) -> Result { + switch (Element.getKind()) { + case CFGElement::Initializer: + return InitMS(*Element.getAs<CFGInitializer>()->getInitializer(), + Context, S); + case CFGElement::Statement: + case CFGElement::Constructor: + case CFGElement::CXXRecordTypedCall: + return StmtMS(*Element.getAs<CFGStmt>()->getStmt(), Context, S); + default: + // FIXME: Handle other kinds of CFGElement. + return Result(); + } + }; + } + +private: + ASTMatchSwitchBuilder<Stmt, State, Result> StmtBuilder; + ASTMatchSwitchBuilder<CXXCtorInitializer, State, Result> InitBuilder; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
