From c88deef0a7218dd5c30500e7d3f58fc23283d3e5 Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Thu, 3 Mar 2022 11:58:57 +0000 Subject: [PATCH] [clang][dataflow] Add `MatchSwitch` utility library. Adds `MatchSwitch`, a library for simplifying implementation of transfer functions. `MatchSwitch` supports constructing a "switch" statement, where each case of the switch is defined by an AST matcher. The cases are considered in order, like pattern matching in functional languages. Differential Revision: https://reviews.llvm.org/D120900 --- .../clang/Analysis/FlowSensitive/MatchSwitch.h | 153 ++++++++++++++++ .../Analysis/FlowSensitive/CMakeLists.txt | 1 + .../Analysis/FlowSensitive/MatchSwitchTest.cpp | 204 +++++++++++++++++++++ 3 files changed, 358 insertions(+) create mode 100644 clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h create mode 100644 clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp diff --git a/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h b/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h new file mode 100644 index 0000000..b319360 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h @@ -0,0 +1,153 @@ +//===---- MatchSwitch.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 `MatchSwitch` abstraction for building a "switch" +// statement, where each case of the switch is defined by an AST matcher. The +// cases are considered in order, like pattern matching in functional +// languages. +// +// Currently, the design is catered towards simplifying the implementation of +// `DataflowAnalysis` transfer functions. Based on experience here, this +// library may be generalized and moved to ASTMatchers. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Stmt.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "llvm/ADT/StringRef.h" +#include +#include +#include +#include + +namespace clang { +namespace dataflow { + +/// A common form of state shared between the cases of a transfer function. +template struct TransferState { + TransferState(LatticeT &Lattice, Environment &Env) + : Lattice(Lattice), Env(Env) {} + + /// Current lattice element. + LatticeT &Lattice; + Environment &Env; +}; + +/// Matches against `Stmt` and, based on its structure, dispatches to an +/// appropriate handler. +template +using MatchSwitch = std::function; + +/// 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. +/// +/// 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. +/// +/// \code +/// MatchSwitch BuildSwitch() { +/// return MatchSwitchBuilder>() +/// .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall) +/// .CaseOf(callExpr(argumentCountIs(2), +/// callee(functionDecl(hasName("bar")))), +/// TransferBarCall) +/// .Build(); +/// } +/// \endcode +template class MatchSwitchBuilder { +public: + // An action is triggered by the match of a pattern against the input + // statement. For generality, actions take both the matched statement and the + // set of bindings produced by the match. + using Action = std::function; + + MatchSwitchBuilder &&CaseOf(ast_matchers::internal::Matcher M, + Action A) && { + Matchers.push_back(std::move(M)); + Actions.push_back(std::move(A)); + return std::move(*this); + } + + // Convenience function for the common case, where bound nodes are not + // needed. `Node` should be a subclass of `Stmt`. + template + MatchSwitchBuilder &&CaseOf(ast_matchers::internal::Matcher M, + void (*Action)(const Node *, State &)) && { + Matchers.push_back(std::move(M)); + Actions.push_back([Action](const Stmt *Stmt, + const ast_matchers::MatchFinder::MatchResult &, + State &S) { Action(cast(Stmt), S); }); + return std::move(*this); + } + + MatchSwitch Build() && { + return [Matcher = BuildMatcher(), Actions = std::move(Actions)]( + const Stmt &Stmt, ASTContext &Context, State &S) { + auto Results = ast_matchers::matchDynamic(Matcher, Stmt, Context); + if (Results.empty()) + return; + // 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()) { + llvm::StringRef ID(Element.first); + size_t Index = 0; + if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) && + Index < Actions.size()) { + Actions[Index]( + &Stmt, + ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S); + return; + } + } + }; + } + +private: + ast_matchers::internal::DynTypedMatcher BuildMatcher() { + using ast_matchers::anything; + using ast_matchers::stmt; + using ast_matchers::unless; + using ast_matchers::internal::DynTypedMatcher; + if (Matchers.empty()) + return stmt(unless(anything())); + for (int I = 0, N = Matchers.size(); I < N; ++I) { + std::string Tag = ("Tag" + llvm::Twine(I)).str(); + // Many matchers are not bindable, so ensure that tryBind will work. + Matchers[I].setAllowBind(true); + auto M = *Matchers[I].tryBind(Tag); + // Each anyOf explicitly controls the traversal kind. The anyOf itself is + // set to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to + // the kind of the branches. Then, each branch is either left as is, if + // the kind is already set, or explicitly set to `TK_AsIs`. We choose this + // setting because it is the default interpretation of matchers. + Matchers[I] = + !M.getTraversalKind() ? M.withTraversalKind(TK_AsIs) : std::move(M); + } + // 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(), + std::move(Matchers)); + } + + std::vector Matchers; + std::vector Actions; +}; +} // namespace dataflow +} // namespace clang +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ diff --git a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt index 4dc442b..d260850 100644 --- a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -7,6 +7,7 @@ add_clang_unittest(ClangAnalysisFlowSensitiveTests DataflowAnalysisContextTest.cpp DataflowEnvironmentTest.cpp MapLatticeTest.cpp + MatchSwitchTest.cpp MultiVarConstantPropagationTest.cpp SingleVarConstantPropagationTest.cpp SourceLocationsLatticeTest.cpp diff --git a/clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp b/clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp new file mode 100644 index 0000000..b99e5c6 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp @@ -0,0 +1,204 @@ +//===- unittests/Analysis/FlowSensitive/MatchSwitchTest.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 +// +//===----------------------------------------------------------------------===// +// +// 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" +#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/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "clang/Analysis/FlowSensitive/MapLattice.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/Twine.h" +#include "llvm/Support/Error.h" +#include "llvm/Testing/Support/Annotations.h" +#include "llvm/Testing/Support/Error.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include +#include +#include +#include +#include + +using namespace clang; +using namespace dataflow; + +namespace { +using ::testing::Pair; +using ::testing::UnorderedElementsAre; + +class BooleanLattice { +public: + BooleanLattice() : Value(false) {} + explicit BooleanLattice(bool B) : Value(B) {} + + static BooleanLattice bottom() { return BooleanLattice(false); } + + static BooleanLattice top() { return BooleanLattice(true); } + + LatticeJoinEffect join(BooleanLattice Other) { + auto Prev = Value; + Value = Value || Other.Value; + return Prev == Value ? LatticeJoinEffect::Unchanged + : LatticeJoinEffect::Changed; + } + + friend bool operator==(BooleanLattice LHS, BooleanLattice RHS) { + return LHS.Value == RHS.Value; + } + + friend std::ostream &operator<<(std::ostream &Os, const BooleanLattice &B) { + Os << B.Value; + return Os; + } + + bool value() const { return Value; } + +private: + bool Value; +}; +} // namespace + +MATCHER_P(Holds, m, + ((negation ? "doesn't hold" : "holds") + + llvm::StringRef(" a lattice element that ") + + ::testing::DescribeMatcher(m, negation)) + .str()) { + return ExplainMatchResult(m, arg.Lattice, result_listener); +} + +void TransferSetTrue(const DeclRefExpr *, + TransferState &State) { + State.Lattice = BooleanLattice(true); +} + +void TransferSetFalse(const Stmt *, + const ast_matchers::MatchFinder::MatchResult &, + TransferState &State) { + State.Lattice = BooleanLattice(false); +} + +class TestAnalysis : public DataflowAnalysis { + MatchSwitch> TransferSwitch; + +public: + explicit TestAnalysis(ASTContext &Context) + : DataflowAnalysis(Context) { + using namespace ast_matchers; + TransferSwitch = + MatchSwitchBuilder>() + .CaseOf(declRefExpr(to(varDecl(hasName("X")))), TransferSetTrue) + .CaseOf(callExpr(callee(functionDecl(hasName("Foo")))), + TransferSetFalse) + .Build(); + } + + static BooleanLattice initialElement() { return BooleanLattice::bottom(); } + + void transfer(const Stmt *S, BooleanLattice &L, Environment &Env) { + TransferState State(L, Env); + TransferSwitch(*S, getASTContext(), State); + } +}; + +class MatchSwitchTest : public ::testing::Test { +protected: + template + void RunDataflow(llvm::StringRef Code, Matcher Expectations) { + ASSERT_THAT_ERROR( + test::checkDataflow( + Code, "fun", + [](ASTContext &C, Environment &) { return TestAnalysis(C); }, + [&Expectations]( + llvm::ArrayRef>> + Results, + ASTContext &) { EXPECT_THAT(Results, Expectations); }, + {"-fsyntax-only", "-std=c++17"}), + llvm::Succeeded()); + } +}; + +TEST_F(MatchSwitchTest, JustX) { + std::string Code = R"( + void fun() { + int X = 1; + (void)X; + // [[p]] + } + )"; + RunDataflow(Code, + UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true))))); +} + +TEST_F(MatchSwitchTest, JustFoo) { + std::string Code = R"( + void Foo(); + void fun() { + Foo(); + // [[p]] + } + )"; + RunDataflow(Code, + UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false))))); +} + +TEST_F(MatchSwitchTest, XThenFoo) { + std::string Code = R"( + void Foo(); + void fun() { + int X = 1; + (void)X; + Foo(); + // [[p]] + } + )"; + RunDataflow(Code, + UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false))))); +} + +TEST_F(MatchSwitchTest, FooThenX) { + std::string Code = R"( + void Foo(); + void fun() { + Foo(); + int X = 1; + (void)X; + // [[p]] + } + )"; + RunDataflow(Code, + UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true))))); +} + +TEST_F(MatchSwitchTest, Neither) { + std::string Code = R"( + void Bar(); + void fun(bool b) { + Bar(); + // [[p]] + } + )"; + RunDataflow(Code, + UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false))))); +} -- 2.7.4