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: 52 BooleanLattice() : Value(false) {} 53 explicit BooleanLattice(bool B) : Value(B) {} 54 55 static BooleanLattice bottom() { return BooleanLattice(false); } 56 57 static BooleanLattice top() { return BooleanLattice(true); } 58 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 66 friend bool operator==(BooleanLattice LHS, BooleanLattice RHS) { 67 return LHS.Value == RHS.Value; 68 } 69 70 friend std::ostream &operator<<(std::ostream &Os, const BooleanLattice &B) { 71 Os << B.Value; 72 return Os; 73 } 74 75 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 90 void TransferSetTrue(const DeclRefExpr *, 91 const ast_matchers::MatchFinder::MatchResult &, 92 TransferState<BooleanLattice> &State) { 93 State.Lattice = BooleanLattice(true); 94 } 95 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: 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 118 static BooleanLattice initialElement() { return BooleanLattice::bottom(); } 119 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> 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 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 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 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 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 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 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