clang  16.0.0git
MatchSwitch.h
Go to the documentation of this file.
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"
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 {
44  : Lattice(Lattice), Env(Env) {}
45 
46  /// Current lattice element.
47  LatticeT &Lattice;
49 };
50 
51 template <typename T>
52 using MatchSwitchMatcher = ast_matchers::internal::Matcher<T>;
53 
54 template <typename T, typename State, typename Result = void>
55 using MatchSwitchAction = std::function<Result(
57 
58 template <typename BaseT, typename State, typename Result = void>
59 using ASTMatchSwitch =
60  std::function<Result(const BaseT &, ASTContext &, State &)>;
61 
62 // FIXME: Remove this alias when all usages of `MatchSwitch` are updated to
63 // `ASTMatchSwitch<Stmt>`.
64 template <typename State, typename Result = void>
66 
67 /// Collects cases of a "match switch": a collection of matchers paired with
68 /// callbacks, which together define a switch that can be applied to a node
69 /// whose type derives from `BaseT`. This structure can simplify the definition
70 /// of `transfer` functions that rely on pattern-matching.
71 ///
72 /// For example, consider an analysis that handles particular function calls. It
73 /// can define the `ASTMatchSwitch` once, in the constructor of the analysis,
74 /// and then reuse it each time that `transfer` is called, with a fresh state
75 /// value.
76 ///
77 /// \code
78 /// ASTMatchSwitch<Stmt, TransferState<MyLattice> BuildSwitch() {
79 /// return ASTMatchSwitchBuilder<TransferState<MyLattice>>()
80 /// .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall)
81 /// .CaseOf(callExpr(argumentCountIs(2),
82 /// callee(functionDecl(hasName("bar")))),
83 /// TransferBarCall)
84 /// .Build();
85 /// }
86 /// \endcode
87 template <typename BaseT, typename State, typename Result = void>
89 public:
90  /// Registers an action that will be triggered by the match of a pattern
91  /// against the input statement.
92  ///
93  /// Requirements:
94  ///
95  /// `NodeT` should be derived from `BaseT`.
96  template <typename NodeT>
99  static_assert(std::is_base_of<BaseT, NodeT>::value,
100  "NodeT must be derived from BaseT.");
101  Matchers.push_back(std::move(M));
102  Actions.push_back(
103  [A = std::move(A)](const BaseT *Node,
105  State &S) { return A(cast<NodeT>(Node), R, S); });
106  return std::move(*this);
107  }
108 
110  return [Matcher = BuildMatcher(), Actions = std::move(Actions)](
111  const BaseT &Node, ASTContext &Context, State &S) -> Result {
112  auto Results = ast_matchers::matchDynamic(Matcher, Node, Context);
113  if (Results.empty()) {
114  return Result();
115  }
116  // Look through the map for the first binding of the form "TagN..." use
117  // that to select the action.
118  for (const auto &Element : Results[0].getMap()) {
119  llvm::StringRef ID(Element.first);
120  size_t Index = 0;
121  if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) &&
122  Index < Actions.size()) {
123  return Actions[Index](
124  &Node,
125  ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S);
126  }
127  }
128  return Result();
129  };
130  }
131 
132 private:
133  ast_matchers::internal::DynTypedMatcher BuildMatcher() {
135  using ast_matchers::stmt;
136  using ast_matchers::unless;
137  using ast_matchers::internal::DynTypedMatcher;
138  if (Matchers.empty())
139  return stmt(unless(anything()));
140  for (int I = 0, N = Matchers.size(); I < N; ++I) {
141  std::string Tag = ("Tag" + llvm::Twine(I)).str();
142  // Many matchers are not bindable, so ensure that tryBind will work.
143  Matchers[I].setAllowBind(true);
144  auto M = *Matchers[I].tryBind(Tag);
145  // Each anyOf explicitly controls the traversal kind. The anyOf itself is
146  // set to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to
147  // the kind of the branches. Then, each branch is either left as is, if
148  // the kind is already set, or explicitly set to `TK_AsIs`. We choose this
149  // setting because it is the default interpretation of matchers.
150  Matchers[I] =
151  !M.getTraversalKind() ? M.withTraversalKind(TK_AsIs) : std::move(M);
152  }
153  // The matcher type on the cases ensures that `Expr` kind is compatible with
154  // all of the matchers.
155  return DynTypedMatcher::constructVariadic(
156  DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<BaseT>(),
157  std::move(Matchers));
158  }
159 
160  std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
161  std::vector<MatchSwitchAction<BaseT, State, Result>> Actions;
162 };
163 
164 // FIXME: Remove this alias when all usages of `MatchSwitchBuilder` are updated
165 // to `ASTMatchSwitchBuilder<Stmt>`.
166 template <typename State, typename Result = void>
168 
169 } // namespace dataflow
170 } // namespace clang
171 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_
clang::dataflow::TransferState::TransferState
TransferState(LatticeT &Lattice, Environment &Env)
Definition: MatchSwitch.h:43
string
string(SUBSTRING ${CMAKE_CURRENT_BINARY_DIR} 0 ${PATH_LIB_START} PATH_HEAD) string(SUBSTRING $
Definition: CMakeLists.txt:22
clang::ast_matchers::stmt
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
Definition: ASTMatchersInternal.cpp:810
clang::dataflow::MatchSwitchMatcher
ast_matchers::internal::Matcher< T > MatchSwitchMatcher
Definition: MatchSwitch.h:52
clang::dataflow::TransferState
A common form of state shared between the cases of a transfer function.
Definition: MatchSwitch.h:42
ASTMatchFinder.h
clang::dataflow::TransferState::Env
Environment & Env
Definition: MatchSwitch.h:48
Node
DynTypedNode Node
Definition: ASTMatchFinder.cpp:68
MatchResult
MatchFinder::MatchResult MatchResult
Definition: RangeSelector.cpp:30
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:209
ASTMatchers.h
ASTContext.h
clang::dataflow::MatchSwitch
ASTMatchSwitch< Stmt, State, Result > MatchSwitch
Definition: MatchSwitch.h:65
clang::ast_matchers::matchDynamic
SmallVector< BoundNodes, 1 > matchDynamic(internal::DynTypedMatcher Matcher, const DynTypedNode &Node, ASTContext &Context)
Definition: ASTMatchFinder.h:327
clang::dataflow::ASTMatchSwitchBuilder
Collects cases of a "match switch": a collection of matchers paired with callbacks,...
Definition: MatchSwitch.h:88
clang::ast_matchers::unless
const internal::VariadicOperatorMatcherFunc< 1, 1 > unless
Matches if the provided matcher does not match.
Definition: ASTMatchersInternal.cpp:1026
clang::TK_AsIs
@ TK_AsIs
Will traverse all child nodes.
Definition: ASTTypeTraits.h:40
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1147
DataflowEnvironment.h
clang::ast_matchers::MatchFinder::MatchResult
Contains all information for a given match.
Definition: ASTMatchFinder.h:74
clang::ast_matchers::anything
internal::TrueMatcher anything()
Matches any node.
Definition: ASTMatchers.h:169
clang::Builtin::ID
ID
Definition: Builtins.h:52
clang
Definition: CalledOnceCheck.h:17
clang::dataflow::ASTMatchSwitch
std::function< Result(const BaseT &, ASTContext &, State &)> ASTMatchSwitch
Definition: MatchSwitch.h:60
clang::dataflow::ASTMatchSwitchBuilder::CaseOf
ASTMatchSwitchBuilder && CaseOf(MatchSwitchMatcher< BaseT > M, MatchSwitchAction< NodeT, State, Result > A) &&
Registers an action that will be triggered by the match of a pattern against the input statement.
Definition: MatchSwitch.h:97
clang::dataflow::ASTMatchSwitchBuilder::Build
ASTMatchSwitch< BaseT, State, Result > Build() &&
Definition: MatchSwitch.h:109
Stmt.h
clang::dataflow::MatchSwitchAction
std::function< Result(const T *, const ast_matchers::MatchFinder::MatchResult &, State &)> MatchSwitchAction
Definition: MatchSwitch.h:56
clang::dataflow::Environment
Holds the state of the program (store and heap) at a given program point.
Definition: DataflowEnvironment.h:65
clang::dataflow::TransferState::Lattice
LatticeT & Lattice
Current lattice element.
Definition: MatchSwitch.h:47