1 //===---- MatchSwitch.h -----------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the `MatchSwitch` abstraction for building a "switch" 10 // statement, where each case of the switch is defined by an AST matcher. The 11 // cases are considered in order, like pattern matching in functional 12 // languages. 13 // 14 // Currently, the design is catered towards simplifying the implementation of 15 // `DataflowAnalysis` transfer functions. Based on experience here, this 16 // library may be generalized and moved to ASTMatchers. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ 21 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ 22 23 #include "clang/AST/ASTContext.h" 24 #include "clang/AST/Stmt.h" 25 #include "clang/ASTMatchers/ASTMatchFinder.h" 26 #include "clang/ASTMatchers/ASTMatchers.h" 27 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 28 #include "llvm/ADT/StringRef.h" 29 #include <functional> 30 #include <string> 31 #include <utility> 32 #include <vector> 33 34 namespace clang { 35 namespace dataflow { 36 37 /// A common form of state shared between the cases of a transfer function. 38 template <typename LatticeT> struct TransferState { 39 TransferState(LatticeT &Lattice, Environment &Env) 40 : Lattice(Lattice), Env(Env) {} 41 42 /// Current lattice element. 43 LatticeT &Lattice; 44 Environment &Env; 45 }; 46 47 /// Matches against `Stmt` and, based on its structure, dispatches to an 48 /// appropriate handler. 49 template <typename State, typename Result = void> 50 using MatchSwitch = std::function<Result(const Stmt &, ASTContext &, State &)>; 51 52 /// Collects cases of a "match switch": a collection of matchers paired with 53 /// callbacks, which together define a switch that can be applied to a 54 /// `Stmt`. This structure can simplify the definition of `transfer` functions 55 /// that rely on pattern-matching. 56 /// 57 /// For example, consider an analysis that handles particular function calls. It 58 /// can define the `MatchSwitch` once, in the constructor of the analysis, and 59 /// then reuse it each time that `transfer` is called, with a fresh state value. 60 /// 61 /// \code 62 /// MatchSwitch<TransferState<MyLattice> BuildSwitch() { 63 /// return MatchSwitchBuilder<TransferState<MyLattice>>() 64 /// .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall) 65 /// .CaseOf(callExpr(argumentCountIs(2), 66 /// callee(functionDecl(hasName("bar")))), 67 /// TransferBarCall) 68 /// .Build(); 69 /// } 70 /// \endcode 71 template <typename State, typename Result = void> class MatchSwitchBuilder { 72 public: 73 /// Registers an action that will be triggered by the match of a pattern 74 /// against the input statement. 75 /// 76 /// Requirements: 77 /// 78 /// `Node` should be a subclass of `Stmt`. 79 template <typename Node> 80 MatchSwitchBuilder && 81 CaseOf(ast_matchers::internal::Matcher<Stmt> M, 82 std::function<Result(const Node *, 83 const ast_matchers::MatchFinder::MatchResult &, 84 State &)> 85 A) && { 86 Matchers.push_back(std::move(M)); 87 Actions.push_back( 88 [A = std::move(A)](const Stmt *Stmt, 89 const ast_matchers::MatchFinder::MatchResult &R, 90 State &S) { return A(cast<Node>(Stmt), R, S); }); 91 return std::move(*this); 92 } 93 94 MatchSwitch<State, Result> Build() && { 95 return [Matcher = BuildMatcher(), Actions = std::move(Actions)]( 96 const Stmt &Stmt, ASTContext &Context, State &S) -> Result { 97 auto Results = ast_matchers::matchDynamic(Matcher, Stmt, Context); 98 if (Results.empty()) 99 return Result(); 100 // Look through the map for the first binding of the form "TagN..." use 101 // that to select the action. 102 for (const auto &Element : Results[0].getMap()) { 103 llvm::StringRef ID(Element.first); 104 size_t Index = 0; 105 if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) && 106 Index < Actions.size()) { 107 return Actions[Index]( 108 &Stmt, 109 ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S); 110 } 111 } 112 return Result(); 113 }; 114 } 115 116 private: 117 ast_matchers::internal::DynTypedMatcher BuildMatcher() { 118 using ast_matchers::anything; 119 using ast_matchers::stmt; 120 using ast_matchers::unless; 121 using ast_matchers::internal::DynTypedMatcher; 122 if (Matchers.empty()) 123 return stmt(unless(anything())); 124 for (int I = 0, N = Matchers.size(); I < N; ++I) { 125 std::string Tag = ("Tag" + llvm::Twine(I)).str(); 126 // Many matchers are not bindable, so ensure that tryBind will work. 127 Matchers[I].setAllowBind(true); 128 auto M = *Matchers[I].tryBind(Tag); 129 // Each anyOf explicitly controls the traversal kind. The anyOf itself is 130 // set to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to 131 // the kind of the branches. Then, each branch is either left as is, if 132 // the kind is already set, or explicitly set to `TK_AsIs`. We choose this 133 // setting because it is the default interpretation of matchers. 134 Matchers[I] = 135 !M.getTraversalKind() ? M.withTraversalKind(TK_AsIs) : std::move(M); 136 } 137 // The matcher type on the cases ensures that `Expr` kind is compatible with 138 // all of the matchers. 139 return DynTypedMatcher::constructVariadic( 140 DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<Stmt>(), 141 std::move(Matchers)); 142 } 143 144 std::vector<ast_matchers::internal::DynTypedMatcher> Matchers; 145 std::vector<std::function<Result( 146 const Stmt *, const ast_matchers::MatchFinder::MatchResult &, State &)>> 147 Actions; 148 }; 149 } // namespace dataflow 150 } // namespace clang 151 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ 152