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