diff --git a/clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h b/clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h new file mode 100644 --- /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 +#include + +namespace clang { +namespace dataflow { + +template +using CFGMatchSwitch = + 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 an AST node +/// contained in a CFG element. +template 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 + CFGMatchSwitchBuilder && + CaseOfCFGStmt(MatchSwitchMatcher M, + MatchSwitchAction A) && { + std::move(StmtBuilder).template CaseOf(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 + CFGMatchSwitchBuilder && + CaseOfCFGInit(MatchSwitchMatcher M, + MatchSwitchAction A) && { + std::move(InitBuilder).template CaseOf(M, A); + return std::move(*this); + } + + CFGMatchSwitch 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().getInitializer(), + Context, S); + case CFGElement::Statement: + case CFGElement::Constructor: + case CFGElement::CXXRecordTypedCall: + return StmtMS(*Element.castAs().getStmt(), Context, S); + default: + // FIXME: Handle other kinds of CFGElement. + return Result(); + } + }; + } + +private: + ASTMatchSwitchBuilder StmtBuilder; + ASTMatchSwitchBuilder 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 --- 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` #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ @@ -28,6 +31,7 @@ #include "llvm/ADT/StringRef.h" #include #include +#include #include #include @@ -44,23 +48,35 @@ Environment &Env; }; -/// Matches against `Stmt` and, based on its structure, dispatches to an -/// appropriate handler. +template +using MatchSwitchMatcher = ast_matchers::internal::Matcher; + +template +using MatchSwitchAction = std::function; + +template +using ASTMatchSwitch = + std::function; + +// FIXME: Remove this alias when all usages of `MatchSwitch` are updated to +// `ASTMatchSwitch`. template -using MatchSwitch = std::function; +using MatchSwitch = ASTMatchSwitch; /// 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 BuildSwitch() { -/// return MatchSwitchBuilder>() +/// ASTMatchSwitch BuildSwitch() { +/// return ASTMatchSwitchBuilder>() /// .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall) /// .CaseOf(callExpr(argumentCountIs(2), /// callee(functionDecl(hasName("bar")))), @@ -68,35 +84,35 @@ /// .Build(); /// } /// \endcode -template class MatchSwitchBuilder { +template +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 - MatchSwitchBuilder && - CaseOf(ast_matchers::internal::Matcher M, - std::function - A) && { + /// `NodeT` should be derived from `BaseT`. + template + ASTMatchSwitchBuilder &&CaseOf(MatchSwitchMatcher M, + MatchSwitchAction A) && { + static_assert(std::is_base_of::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(Stmt), R, S); }); + State &S) { return A(cast(Node), R, S); }); return std::move(*this); } - MatchSwitch Build() && { + ASTMatchSwitch 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 @@ 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 @@ // 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(), + DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind(), std::move(Matchers)); } std::vector Matchers; - std::vector> - Actions; + std::vector> Actions; }; + +// FIXME: Remove this alias when all usages of `MatchSwitchBuilder` are updated +// to `ASTMatchSwitchBuilder`. +template +using MatchSwitchBuilder = ASTMatchSwitchBuilder; + } // 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 --- /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() + .CaseOfCFGStmt( + declStmt(hasSingleDecl( + varDecl(hasInitializer(integerLiteral(equals(42)))))), + [](const DeclStmt *, const MatchFinder::MatchResult &, + CFGElementMatches &Counter) { Counter.StmtMatches++; }) + .CaseOfCFGInit( + 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 +void applySwitchToCode(CFGMatchSwitch &MS, State &S, + llvm::StringRef Code) { + auto Unit = tooling::buildASTFromCodeWithArgs(Code, {"-Wno-unused-value"}); + auto &Ctx = Unit->getASTContext(); + const auto *F = selectFirst( + "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 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 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 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 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 --- a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -4,6 +4,7 @@ ) 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 --- 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"