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 
37 namespace clang {
38 namespace dataflow {
39 
40 /// A common form of state shared between the cases of a transfer function.
41 template <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.
55 template <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 
64 template <typename T>
65 using MatchSwitchMatcher = ast_matchers::internal::Matcher<T>;
66 
67 template <typename T, typename State, typename Result = void>
68 using MatchSwitchAction = std::function<Result(
69     const T *, const ast_matchers::MatchFinder::MatchResult &, State &)>;
70 
71 template <typename BaseT, typename State, typename Result = void>
72 using 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
95 template <typename BaseT, typename State, typename Result = void>
96 class ASTMatchSwitchBuilder {
97 public:
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 
140 private:
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