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 // FIXME: Rename to ASTMatchSwitch.h and update documentation when all usages of 21 // `MatchSwitch` are updated to `ASTMatchSwitch<Stmt>` 22 23 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ 24 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ 25 26 #include "clang/AST/ASTContext.h" 27 #include "clang/AST/Stmt.h" 28 #include "clang/ASTMatchers/ASTMatchFinder.h" 29 #include "clang/ASTMatchers/ASTMatchers.h" 30 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 31 #include "llvm/ADT/StringRef.h" 32 #include <functional> 33 #include <string> 34 #include <type_traits> 35 #include <utility> 36 #include <vector> 37 38 namespace clang { 39 namespace dataflow { 40 41 /// A common form of state shared between the cases of a transfer function. 42 template <typename LatticeT> struct TransferState { TransferStateTransferState43 TransferState(LatticeT &Lattice, Environment &Env) 44 : Lattice(Lattice), Env(Env) {} 45 46 /// Current lattice element. 47 LatticeT &Lattice; 48 Environment &Env; 49 }; 50 51 /// A read-only version of TransferState. 52 template <typename LatticeT> struct TransferStateForDiagnostics { TransferStateForDiagnosticsTransferStateForDiagnostics53 TransferStateForDiagnostics(const LatticeT &Lattice, const Environment &Env) 54 : Lattice(Lattice), Env(Env) {} 55 56 /// Current lattice element. 57 const LatticeT &Lattice; 58 const Environment &Env; 59 }; 60 61 template <typename T> 62 using MatchSwitchMatcher = ast_matchers::internal::Matcher<T>; 63 64 template <typename T, typename State, typename Result = void> 65 using MatchSwitchAction = std::function<Result( 66 const T *, const ast_matchers::MatchFinder::MatchResult &, State &)>; 67 68 template <typename BaseT, typename State, typename Result = void> 69 using ASTMatchSwitch = 70 std::function<Result(const BaseT &, ASTContext &, State &)>; 71 72 // FIXME: Remove this alias when all usages of `MatchSwitch` are updated to 73 // `ASTMatchSwitch<Stmt>`. 74 template <typename State, typename Result = void> 75 using MatchSwitch = ASTMatchSwitch<Stmt, State, Result>; 76 77 /// Collects cases of a "match switch": a collection of matchers paired with 78 /// callbacks, which together define a switch that can be applied to a node 79 /// whose type derives from `BaseT`. This structure can simplify the definition 80 /// of `transfer` functions that rely on pattern-matching. 81 /// 82 /// For example, consider an analysis that handles particular function calls. It 83 /// can define the `ASTMatchSwitch` once, in the constructor of the analysis, 84 /// and then reuse it each time that `transfer` is called, with a fresh state 85 /// value. 86 /// 87 /// \code 88 /// ASTMatchSwitch<Stmt, TransferState<MyLattice> BuildSwitch() { 89 /// return ASTMatchSwitchBuilder<TransferState<MyLattice>>() 90 /// .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall) 91 /// .CaseOf(callExpr(argumentCountIs(2), 92 /// callee(functionDecl(hasName("bar")))), 93 /// TransferBarCall) 94 /// .Build(); 95 /// } 96 /// \endcode 97 template <typename BaseT, typename State, typename Result = void> 98 class ASTMatchSwitchBuilder { 99 public: 100 /// Registers an action that will be triggered by the match of a pattern 101 /// against the input statement. 102 /// 103 /// Requirements: 104 /// 105 /// `NodeT` should be derived from `BaseT`. 106 template <typename NodeT> CaseOf(MatchSwitchMatcher<BaseT> M,MatchSwitchAction<NodeT,State,Result> A)107 ASTMatchSwitchBuilder &&CaseOf(MatchSwitchMatcher<BaseT> M, 108 MatchSwitchAction<NodeT, State, Result> A) && { 109 static_assert(std::is_base_of<BaseT, NodeT>::value, 110 "NodeT must be derived from BaseT."); 111 Matchers.push_back(std::move(M)); 112 Actions.push_back( 113 [A = std::move(A)](const BaseT *Node, 114 const ast_matchers::MatchFinder::MatchResult &R, 115 State &S) { return A(cast<NodeT>(Node), R, S); }); 116 return std::move(*this); 117 } 118 Build()119 ASTMatchSwitch<BaseT, State, Result> Build() && { 120 return [Matcher = BuildMatcher(), Actions = std::move(Actions)]( 121 const BaseT &Node, ASTContext &Context, State &S) -> Result { 122 auto Results = ast_matchers::matchDynamic(Matcher, Node, Context); 123 if (Results.empty()) { 124 return Result(); 125 } 126 // Look through the map for the first binding of the form "TagN..." use 127 // that to select the action. 128 for (const auto &Element : Results[0].getMap()) { 129 llvm::StringRef ID(Element.first); 130 size_t Index = 0; 131 if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) && 132 Index < Actions.size()) { 133 return Actions[Index]( 134 &Node, 135 ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S); 136 } 137 } 138 return Result(); 139 }; 140 } 141 142 private: BuildMatcher()143 ast_matchers::internal::DynTypedMatcher BuildMatcher() { 144 using ast_matchers::anything; 145 using ast_matchers::stmt; 146 using ast_matchers::unless; 147 using ast_matchers::internal::DynTypedMatcher; 148 if (Matchers.empty()) 149 return stmt(unless(anything())); 150 for (int I = 0, N = Matchers.size(); I < N; ++I) { 151 std::string Tag = ("Tag" + llvm::Twine(I)).str(); 152 // Many matchers are not bindable, so ensure that tryBind will work. 153 Matchers[I].setAllowBind(true); 154 auto M = *Matchers[I].tryBind(Tag); 155 // Each anyOf explicitly controls the traversal kind. The anyOf itself is 156 // set to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to 157 // the kind of the branches. Then, each branch is either left as is, if 158 // the kind is already set, or explicitly set to `TK_AsIs`. We choose this 159 // setting because it is the default interpretation of matchers. 160 Matchers[I] = 161 !M.getTraversalKind() ? M.withTraversalKind(TK_AsIs) : std::move(M); 162 } 163 // The matcher type on the cases ensures that `Expr` kind is compatible with 164 // all of the matchers. 165 return DynTypedMatcher::constructVariadic( 166 DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<BaseT>(), 167 std::move(Matchers)); 168 } 169 170 std::vector<ast_matchers::internal::DynTypedMatcher> Matchers; 171 std::vector<MatchSwitchAction<BaseT, State, Result>> Actions; 172 }; 173 174 // FIXME: Remove this alias when all usages of `MatchSwitchBuilder` are updated 175 // to `ASTMatchSwitchBuilder<Stmt>`. 176 template <typename State, typename Result = void> 177 using MatchSwitchBuilder = ASTMatchSwitchBuilder<Stmt, State, Result>; 178 179 } // namespace dataflow 180 } // namespace clang 181 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ 182