wyt updated this revision to Diff 454534. wyt added a comment. Rebase.
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/MatchSwitch.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 StmtMatches = 0; + unsigned 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/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,19 @@ // 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)); } 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/CFGMatchSwitch.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h @@ -0,0 +1,101 @@ +//===---- 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) && { + std::move(std::move(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) && { + std::move(InitBuilder).template CaseOf<NodeT>(M, A); + return std::move(*this); + } + + CFGMatchSwitch<State, Result> Build() && { + return [StmtMS = std::move(StmtBuilder).Build(), + InitMS = std::move(InitBuilder).Build()](const CFGElement &Element, + ASTContext &Context, + State &S) -> Result { + switch (Element.getKind()) { + case CFGElement::Initializer: + return InitMS(*Element.castAs<CFGInitializer>().getInitializer(), + Context, S); + case CFGElement::Statement: + case CFGElement::Constructor: + case CFGElement::CXXRecordTypedCall: + return StmtMS(*Element.castAs<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
