Author: Wei Yi Tee Date: 2022-09-01T10:15:53Z New Revision: d931ac9e27cab964c65078c80e4488185c62b3d8
URL: https://github.com/llvm/llvm-project/commit/d931ac9e27cab964c65078c80e4488185c62b3d8 DIFF: https://github.com/llvm/llvm-project/commit/d931ac9e27cab964c65078c80e4488185c62b3d8.diff LOG: [clang][dataflow] Generalise match switch utility to other AST types and add a `CFGMatchSwitch` which currently handles `CFGStmt` and `CFGInitializer`. `MatchSwitch` currently takes in matchers and functions for the `Stmt` class. This patch generalises the match switch utility (renamed to `ASTMatchSwitch`) to work for different AST node types by introducing a template argument which is the base type for the AST nodes that the match switch will handle. A `CFGMatchSwitch` is introduced as a wrapper around multiple `ASTMatchSwitch`s for different base types. It works by unwrapping `CFGElement`s into their contained AST nodes and passing the nodes to the relevant `ASTMatchSwitch`. The `CFGMatchSwitch` currently only handles `CFGStmt` and `CFGInitializer`. Reviewed By: gribozavr2, sgatev Differential Revision: https://reviews.llvm.org/D131616 Added: clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp Modified: clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h clang/unittests/Analysis/FlowSensitive/CMakeLists.txt clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h b/clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h new file mode 100644 index 0000000000000..ecd8558970f93 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h @@ -0,0 +1,98 @@ +//===---- 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/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/MatchSwitch.h" +#include <functional> +#include <utility> + +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 derived from `Stmt`. + template <typename NodeT> + CFGMatchSwitchBuilder && + CaseOfCFGStmt(MatchSwitchMatcher<Stmt> M, + MatchSwitchAction<NodeT, State, Result> A) && { + 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 derived from `CXXCtorInitializer`. + template <typename NodeT> + CFGMatchSwitchBuilder && + CaseOfCFGInit(MatchSwitchMatcher<CXXCtorInitializer> M, + MatchSwitchAction<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_ diff --git a/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h b/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h index 927aec7df5731..76d18c1d24463 100644 --- a/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h +++ b/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h @@ -16,6 +16,9 @@ // library may be generalized and moved to ASTMatchers. // //===----------------------------------------------------------------------===// +// +// FIXME: Rename to ASTMatchSwitch.h and update documentation when all usages of +// `MatchSwitch` are updated to `ASTMatchSwitch<Stmt>` #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ @@ -28,6 +31,7 @@ #include "llvm/ADT/StringRef.h" #include <functional> #include <string> +#include <type_traits> #include <utility> #include <vector> @@ -44,23 +48,35 @@ template <typename LatticeT> struct TransferState { Environment &Env; }; -/// Matches against `Stmt` and, based on its structure, dispatches to an -/// appropriate handler. +template <typename T> +using MatchSwitchMatcher = ast_matchers::internal::Matcher<T>; + +template <typename T, typename State, typename Result = void> +using MatchSwitchAction = 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 derives 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 +84,35 @@ using MatchSwitch = std::function<Result(const Stmt &, ASTContext &, State &)>; /// .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 derived from `BaseT`. + template <typename NodeT> + ASTMatchSwitchBuilder &&CaseOf(MatchSwitchMatcher<BaseT> M, + MatchSwitchAction<NodeT, State, Result> A) && { + static_assert(std::is_base_of<BaseT, NodeT>::value, + "NodeT must be derived from BaseT."); 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 +121,7 @@ template <typename State, typename Result = void> class MatchSwitchBuilder { 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 +153,19 @@ template <typename State, typename Result = void> class MatchSwitchBuilder { // 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<MatchSwitchAction<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_ diff --git a/clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp b/clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp new file mode 100644 index 0000000000000..826b84cee529d --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/CFGMatchSwitchTest.cpp @@ -0,0 +1,124 @@ +//===- 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/Stmt.h" +#include "clang/Analysis/CFG.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/StringRef.h" +#include "gtest/gtest.h" + +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, 0u); + EXPECT_EQ(Counter.InitializerMatches, 0u); +} + +TEST(CFGMatchSwitchTest, SingleLocalVarInitializationTo42) { + CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch(); + CFGElementMatches Counter; + applySwitchToCode(Switch, Counter, R"( + void f() { + int i = 42; + } + )"); + EXPECT_EQ(Counter.StmtMatches, 1u); + EXPECT_EQ(Counter.InitializerMatches, 0u); +} + +TEST(CFGMatchSwitchTest, SingleFieldInitializationTo42) { + CFGMatchSwitch<CFGElementMatches> Switch = buildCFGMatchSwitch(); + CFGElementMatches Counter; + applySwitchToCode(Switch, Counter, R"( + struct f { + int i; + f(): i(42) {} + }; + )"); + EXPECT_EQ(Counter.StmtMatches, 0u); + EXPECT_EQ(Counter.InitializerMatches, 1u); +} + +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, 1u); + EXPECT_EQ(Counter.InitializerMatches, 1u); +} +} // namespace diff --git a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt index 8ce2549df36d6..85499ecb30010 100644 --- a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -4,6 +4,7 @@ set(LLVM_LINK_COMPONENTS ) add_clang_unittest(ClangAnalysisFlowSensitiveTests + CFGMatchSwitchTest.cpp ChromiumCheckModelTest.cpp DataflowAnalysisContextTest.cpp DataflowEnvironmentTest.cpp diff --git a/clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp b/clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp index bf8c2f5eedc95..90cc4a19ac7fc 100644 --- a/clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp +++ b/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" _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
