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 "clang/AST/ASTContext.h" 17 #include "clang/AST/Decl.h" 18 #include "clang/AST/Expr.h" 19 #include "clang/AST/Stmt.h" 20 #include "clang/ASTMatchers/ASTMatchFinder.h" 21 #include "clang/ASTMatchers/ASTMatchers.h" 22 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" 23 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 24 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 25 #include "clang/Analysis/FlowSensitive/MapLattice.h" 26 #include "clang/Analysis/FlowSensitive/TestingSupport.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 TransferState<BooleanLattice> &State) { 92 State.Lattice = BooleanLattice(true); 93 } 94 95 void TransferSetFalse(const Stmt *, 96 const ast_matchers::MatchFinder::MatchResult &, 97 TransferState<BooleanLattice> &State) { 98 State.Lattice = BooleanLattice(false); 99 } 100 101 class TestAnalysis : public DataflowAnalysis<TestAnalysis, BooleanLattice> { 102 MatchSwitch<TransferState<BooleanLattice>> TransferSwitch; 103 104 public: 105 explicit TestAnalysis(ASTContext &Context) 106 : DataflowAnalysis<TestAnalysis, BooleanLattice>(Context) { 107 using namespace ast_matchers; 108 TransferSwitch = 109 MatchSwitchBuilder<TransferState<BooleanLattice>>() 110 .CaseOf(declRefExpr(to(varDecl(hasName("X")))), TransferSetTrue) 111 .CaseOf(callExpr(callee(functionDecl(hasName("Foo")))), 112 TransferSetFalse) 113 .Build(); 114 } 115 116 static BooleanLattice initialElement() { return BooleanLattice::bottom(); } 117 118 void transfer(const Stmt *S, BooleanLattice &L, Environment &Env) { 119 TransferState<BooleanLattice> State(L, Env); 120 TransferSwitch(*S, getASTContext(), State); 121 } 122 }; 123 124 class MatchSwitchTest : public ::testing::Test { 125 protected: 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 142 TEST_F(MatchSwitchTest, JustX) { 143 std::string Code = R"( 144 void fun() { 145 int X = 1; 146 (void)X; 147 // [[p]] 148 } 149 )"; 150 RunDataflow(Code, 151 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true))))); 152 } 153 154 TEST_F(MatchSwitchTest, JustFoo) { 155 std::string Code = R"( 156 void Foo(); 157 void fun() { 158 Foo(); 159 // [[p]] 160 } 161 )"; 162 RunDataflow(Code, 163 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false))))); 164 } 165 166 TEST_F(MatchSwitchTest, XThenFoo) { 167 std::string Code = R"( 168 void Foo(); 169 void fun() { 170 int X = 1; 171 (void)X; 172 Foo(); 173 // [[p]] 174 } 175 )"; 176 RunDataflow(Code, 177 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false))))); 178 } 179 180 TEST_F(MatchSwitchTest, FooThenX) { 181 std::string Code = R"( 182 void Foo(); 183 void fun() { 184 Foo(); 185 int X = 1; 186 (void)X; 187 // [[p]] 188 } 189 )"; 190 RunDataflow(Code, 191 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true))))); 192 } 193 194 TEST_F(MatchSwitchTest, Neither) { 195 std::string Code = R"( 196 void Bar(); 197 void fun(bool b) { 198 Bar(); 199 // [[p]] 200 } 201 )"; 202 RunDataflow(Code, 203 UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false))))); 204 } 205