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,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 +#include +#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 derivable from `Stmt`. + template + CFGMatchSwitchBuilder CaseOfCFGStmt(MSMatcherT M, + MSActionT A) { + StmtBuilder = 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 derivable from `CXXCtorInitializer`. + template + CFGMatchSwitchBuilder CaseOfCFGInit(MSMatcherT M, + MSActionT A) { + InitBuilder = InitBuilder.template CaseOf(M, A); + return std::move(*this); + } + + CFGMatchSwitch 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()->getInitializer(), + Context, S); + case CFGElement::Statement: + case CFGElement::Constructor: + case CFGElement::CXXRecordTypedCall: + return StmtMS(*Element.getAs()->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/DataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ b/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(this)->transferCFGElement(Element, L, Env)) void transferTypeErased(const CFGElement *Element, TypeErasedLattice &E, Environment &Env) final { Lattice &L = llvm::any_cast(E.Value); transferCFGElement(Element, L, Env); - // FIXME: Remove after users have been updated to implement - // transferCFGElement. + // To deprecate. if (auto Stmt = Element->getAs()) { transfer(Stmt->getStmt(), L, Env); } 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 @@ -44,23 +44,34 @@ Environment &Env; }; -/// Matches against `Stmt` and, based on its structure, dispatches to an -/// appropriate handler. +template using MSMatcherT = ast_matchers::internal::Matcher; + +template +using MSActionT = 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 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 BuildSwitch() { -/// return MatchSwitchBuilder>() +/// ASTMatchSwitch BuildSwitch() { +/// return ASTMatchSwitchBuilder>() /// .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall) /// .CaseOf(callExpr(argumentCountIs(2), /// callee(functionDecl(hasName("bar")))), @@ -68,35 +79,33 @@ /// .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 derivable from `BaseT`. + template + ASTMatchSwitchBuilder CaseOf(MSMatcherT M, + MSActionT 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(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 +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(), + DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind(), std::move(Matchers)); } +public: 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/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ b/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>> runTypeErasedDataflowAnalysis( 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,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 +#include +#include +#include +#include + +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() + .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, 0); + EXPECT_EQ(Counter.InitializerMatches, 0); +} + +TEST(CFGMatchSwitchTest, SingleLocalVarInitializationTo42) { + CFGMatchSwitch 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 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 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 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"