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