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