1 //===- unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp ---------------===//
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 a simplistic version of Constant Propagation as an example
10 // of a forward, monotonic dataflow analysis. The analysis tracks all
11 // variables in the scope, but lacks escape analysis.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "clang/Analysis/FlowSensitive/MatchSwitch.h"
16 #include "TestingSupport.h"
17 #include "clang/AST/ASTContext.h"
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/AST/Stmt.h"
21 #include "clang/ASTMatchers/ASTMatchFinder.h"
22 #include "clang/ASTMatchers/ASTMatchers.h"
23 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
25 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
26 #include "clang/Analysis/FlowSensitive/MapLattice.h"
27 #include "clang/Tooling/Tooling.h"
28 #include "llvm/ADT/None.h"
29 #include "llvm/ADT/Optional.h"
30 #include "llvm/ADT/StringRef.h"
31 #include "llvm/ADT/Twine.h"
32 #include "llvm/Support/Error.h"
33 #include "llvm/Testing/Support/Annotations.h"
34 #include "llvm/Testing/Support/Error.h"
35 #include "gmock/gmock.h"
36 #include "gtest/gtest.h"
37 #include <cstdint>
38 #include <memory>
39 #include <ostream>
40 #include <string>
41 #include <utility>
42
43 using namespace clang;
44 using namespace dataflow;
45
46 namespace {
47 using ::testing::Pair;
48 using ::testing::UnorderedElementsAre;
49
50 class BooleanLattice {
51 public:
BooleanLattice()52 BooleanLattice() : Value(false) {}
BooleanLattice(bool B)53 explicit BooleanLattice(bool B) : Value(B) {}
54
bottom()55 static BooleanLattice bottom() { return BooleanLattice(false); }
56
top()57 static BooleanLattice top() { return BooleanLattice(true); }
58
join(BooleanLattice Other)59 LatticeJoinEffect join(BooleanLattice Other) {
60 auto Prev = Value;
61 Value = Value || Other.Value;
62 return Prev == Value ? LatticeJoinEffect::Unchanged
63 : LatticeJoinEffect::Changed;
64 }
65
operator ==(BooleanLattice LHS,BooleanLattice RHS)66 friend bool operator==(BooleanLattice LHS, BooleanLattice RHS) {
67 return LHS.Value == RHS.Value;
68 }
69
operator <<(std::ostream & Os,const BooleanLattice & B)70 friend std::ostream &operator<<(std::ostream &Os, const BooleanLattice &B) {
71 Os << B.Value;
72 return Os;
73 }
74
value() const75 bool value() const { return Value; }
76
77 private:
78 bool Value;
79 };
80 } // namespace
81
82 MATCHER_P(Holds, m,
83 ((negation ? "doesn't hold" : "holds") +
84 llvm::StringRef(" a lattice element that ") +
85 ::testing::DescribeMatcher<BooleanLattice>(m, negation))
86 .str()) {
87 return ExplainMatchResult(m, arg.Lattice, result_listener);
88 }
89
TransferSetTrue(const DeclRefExpr *,const ast_matchers::MatchFinder::MatchResult &,TransferState<BooleanLattice> & State)90 void TransferSetTrue(const DeclRefExpr *,
91 const ast_matchers::MatchFinder::MatchResult &,
92 TransferState<BooleanLattice> &State) {
93 State.Lattice = BooleanLattice(true);
94 }
95
TransferSetFalse(const Stmt *,const ast_matchers::MatchFinder::MatchResult &,TransferState<BooleanLattice> & State)96 void TransferSetFalse(const Stmt *,
97 const ast_matchers::MatchFinder::MatchResult &,
98 TransferState<BooleanLattice> &State) {
99 State.Lattice = BooleanLattice(false);
100 }
101
102 class TestAnalysis : public DataflowAnalysis<TestAnalysis, BooleanLattice> {
103 MatchSwitch<TransferState<BooleanLattice>> TransferSwitch;
104
105 public:
TestAnalysis(ASTContext & Context)106 explicit TestAnalysis(ASTContext &Context)
107 : DataflowAnalysis<TestAnalysis, BooleanLattice>(Context) {
108 using namespace ast_matchers;
109 TransferSwitch =
110 MatchSwitchBuilder<TransferState<BooleanLattice>>()
111 .CaseOf<DeclRefExpr>(declRefExpr(to(varDecl(hasName("X")))),
112 TransferSetTrue)
113 .CaseOf<Stmt>(callExpr(callee(functionDecl(hasName("Foo")))),
114 TransferSetFalse)
115 .Build();
116 }
117
initialElement()118 static BooleanLattice initialElement() { return BooleanLattice::bottom(); }
119
transfer(const Stmt * S,BooleanLattice & L,Environment & Env)120 void transfer(const Stmt *S, BooleanLattice &L, Environment &Env) {
121 TransferState<BooleanLattice> State(L, Env);
122 TransferSwitch(*S, getASTContext(), State);
123 }
124 };
125
126 template <typename Matcher>
RunDataflow(llvm::StringRef Code,Matcher Expectations)127 void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
128 ASSERT_THAT_ERROR(
129 test::checkDataflow<TestAnalysis>(
130 Code, "fun",
131 [](ASTContext &C, Environment &) { return TestAnalysis(C); },
132 [&Expectations](
133 llvm::ArrayRef<std::pair<
134 std::string, DataflowAnalysisState<TestAnalysis::Lattice>>>
135 Results,
136 ASTContext &) { EXPECT_THAT(Results, Expectations); },
137 {"-fsyntax-only", "-std=c++17"}),
138 llvm::Succeeded());
139 }
140
TEST(MatchSwitchTest,JustX)141 TEST(MatchSwitchTest, JustX) {
142 std::string Code = R"(
143 void fun() {
144 int X = 1;
145 (void)X;
146 // [[p]]
147 }
148 )";
149 RunDataflow(Code,
150 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true)))));
151 }
152
TEST(MatchSwitchTest,JustFoo)153 TEST(MatchSwitchTest, JustFoo) {
154 std::string Code = R"(
155 void Foo();
156 void fun() {
157 Foo();
158 // [[p]]
159 }
160 )";
161 RunDataflow(Code,
162 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
163 }
164
TEST(MatchSwitchTest,XThenFoo)165 TEST(MatchSwitchTest, XThenFoo) {
166 std::string Code = R"(
167 void Foo();
168 void fun() {
169 int X = 1;
170 (void)X;
171 Foo();
172 // [[p]]
173 }
174 )";
175 RunDataflow(Code,
176 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
177 }
178
TEST(MatchSwitchTest,FooThenX)179 TEST(MatchSwitchTest, FooThenX) {
180 std::string Code = R"(
181 void Foo();
182 void fun() {
183 Foo();
184 int X = 1;
185 (void)X;
186 // [[p]]
187 }
188 )";
189 RunDataflow(Code,
190 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true)))));
191 }
192
TEST(MatchSwitchTest,Neither)193 TEST(MatchSwitchTest, Neither) {
194 std::string Code = R"(
195 void Bar();
196 void fun(bool b) {
197 Bar();
198 // [[p]]
199 }
200 )";
201 RunDataflow(Code,
202 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
203 }
204
TEST(MatchSwitchTest,ReturnNonVoid)205 TEST(MatchSwitchTest, ReturnNonVoid) {
206 using namespace ast_matchers;
207
208 auto Unit =
209 tooling::buildASTFromCode("void f() { int x = 42; }", "input.cc",
210 std::make_shared<PCHContainerOperations>());
211 auto &Context = Unit->getASTContext();
212 const auto *S =
213 selectFirst<FunctionDecl>(
214 "f",
215 match(functionDecl(isDefinition(), hasName("f")).bind("f"), Context))
216 ->getBody();
217
218 MatchSwitch<const int, std::vector<int>> Switch =
219 MatchSwitchBuilder<const int, std::vector<int>>()
220 .CaseOf<Stmt>(stmt(),
221 [](const Stmt *, const MatchFinder::MatchResult &,
222 const int &State) -> std::vector<int> {
223 return {1, State, 3};
224 })
225 .Build();
226 std::vector<int> Actual = Switch(*S, Context, 7);
227 std::vector<int> Expected{1, 7, 3};
228 EXPECT_EQ(Actual, Expected);
229 }
230