1 #include "clang/Analysis/FlowSensitive/MapLattice.h"
2 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
3 #include "llvm/Support/Error.h"
4 #include "gmock/gmock.h"
5 #include "gtest/gtest.h"
6 #include <ostream>
7
8 using namespace clang;
9 using namespace dataflow;
10
11 namespace {
12 // A simple lattice for basic tests.
13 class BooleanLattice {
14 public:
BooleanLattice()15 BooleanLattice() : Value(false) {}
BooleanLattice(bool B)16 explicit BooleanLattice(bool B) : Value(B) {}
17
bottom()18 static BooleanLattice bottom() { return BooleanLattice(false); }
19
top()20 static BooleanLattice top() { return BooleanLattice(true); }
21
join(BooleanLattice Other)22 LatticeJoinEffect join(BooleanLattice Other) {
23 auto Prev = Value;
24 Value = Value || Other.Value;
25 return Prev == Value ? LatticeJoinEffect::Unchanged
26 : LatticeJoinEffect::Changed;
27 }
28
operator ==(BooleanLattice LHS,BooleanLattice RHS)29 friend bool operator==(BooleanLattice LHS, BooleanLattice RHS) {
30 return LHS.Value == RHS.Value;
31 }
32
operator !=(BooleanLattice LHS,BooleanLattice RHS)33 friend bool operator!=(BooleanLattice LHS, BooleanLattice RHS) {
34 return LHS.Value != RHS.Value;
35 }
36
operator <<(std::ostream & Os,const BooleanLattice & B)37 friend std::ostream &operator<<(std::ostream &Os, const BooleanLattice &B) {
38 Os << B.Value;
39 return Os;
40 }
41
value() const42 bool value() const { return Value; }
43
44 private:
45 bool Value;
46 };
47 } // namespace
48
49 static constexpr int Key1 = 0;
50 static constexpr int Key2 = 1;
51
52 namespace {
53 using ::testing::_;
54 using ::testing::Pair;
55 using ::testing::UnorderedElementsAre;
56
TEST(MapLatticeTest,InsertWorks)57 TEST(MapLatticeTest, InsertWorks) {
58 MapLattice<int, BooleanLattice> Lattice;
59 EXPECT_THAT(Lattice.insert({Key1, BooleanLattice(false)}), Pair(_, true));
60 EXPECT_THAT(Lattice.insert({Key2, BooleanLattice(false)}), Pair(_, true));
61
62 // Insertion fails on collision.
63 EXPECT_THAT(Lattice.insert({Key1, BooleanLattice(false)}), Pair(_, false));
64 EXPECT_THAT(Lattice.insert({Key2, BooleanLattice(false)}), Pair(_, false));
65
66 EXPECT_THAT(Lattice, UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
67 Pair(Key2, BooleanLattice(false))));
68 }
69
TEST(MapLatticeTest,ComparisonWorks)70 TEST(MapLatticeTest, ComparisonWorks) {
71 MapLattice<int, BooleanLattice> Lattice1;
72 Lattice1.insert({Key1, BooleanLattice(true)});
73 Lattice1.insert({Key2, BooleanLattice(false)});
74 MapLattice<int, BooleanLattice> Lattice2 = Lattice1;
75 EXPECT_EQ(Lattice1, Lattice2);
76
77 Lattice2.find(Key2)->second = BooleanLattice(true);
78 EXPECT_NE(Lattice1, Lattice2);
79 }
80
TEST(MapLatticeTest,JoinChange)81 TEST(MapLatticeTest, JoinChange) {
82 MapLattice<int, BooleanLattice> Lattice1;
83 Lattice1.insert({Key1, BooleanLattice(false)});
84 Lattice1.insert({Key2, BooleanLattice(false)});
85
86 MapLattice<int, BooleanLattice> Lattice2;
87 Lattice2.insert({Key1, BooleanLattice(true)});
88 Lattice2.insert({Key2, BooleanLattice(true)});
89
90 ASSERT_THAT(Lattice1,
91 UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
92 Pair(Key2, BooleanLattice(false))));
93
94 ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
95 EXPECT_THAT(Lattice1, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
96 Pair(Key2, BooleanLattice(true))));
97 }
98
TEST(MapLatticeTest,JoinEqNoChange)99 TEST(MapLatticeTest, JoinEqNoChange) {
100 MapLattice<int, BooleanLattice> Lattice;
101 Lattice.insert({Key1, BooleanLattice(false)});
102 Lattice.insert({Key2, BooleanLattice(false)});
103
104 ASSERT_EQ(Lattice.join(Lattice), LatticeJoinEffect::Unchanged);
105 EXPECT_THAT(Lattice, UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
106 Pair(Key2, BooleanLattice(false))));
107 }
108
TEST(MapLatticeTest,JoinLtNoChange)109 TEST(MapLatticeTest, JoinLtNoChange) {
110 MapLattice<int, BooleanLattice> Lattice1;
111 Lattice1.insert({Key1, BooleanLattice(false)});
112 Lattice1.insert({Key2, BooleanLattice(false)});
113
114 MapLattice<int, BooleanLattice> Lattice2;
115 Lattice2.insert({Key1, BooleanLattice(true)});
116 Lattice2.insert({Key2, BooleanLattice(true)});
117
118 ASSERT_THAT(Lattice1,
119 UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
120 Pair(Key2, BooleanLattice(false))));
121
122 ASSERT_THAT(Lattice2, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
123 Pair(Key2, BooleanLattice(true))));
124
125 ASSERT_EQ(Lattice2.join(Lattice1), LatticeJoinEffect::Unchanged);
126 EXPECT_THAT(Lattice2, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
127 Pair(Key2, BooleanLattice(true))));
128 }
129
TEST(MapLatticeTest,JoinDifferentDomainsProducesUnion)130 TEST(MapLatticeTest, JoinDifferentDomainsProducesUnion) {
131 MapLattice<int, BooleanLattice> Lattice1;
132 Lattice1.insert({Key1, BooleanLattice(true)});
133 MapLattice<int, BooleanLattice> Lattice2;
134 Lattice2.insert({Key2, BooleanLattice(true)});
135
136 ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
137 EXPECT_THAT(Lattice1, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
138 Pair(Key2, BooleanLattice(true))));
139 }
140
TEST(MapLatticeTest,FindWorks)141 TEST(MapLatticeTest, FindWorks) {
142 MapLattice<int, BooleanLattice> Lattice;
143 Lattice.insert({Key1, BooleanLattice(true)});
144 Lattice.insert({Key2, BooleanLattice(false)});
145
146 auto It = Lattice.find(Key1);
147 ASSERT_NE(It, Lattice.end());
148 EXPECT_EQ(It->second, BooleanLattice(true));
149
150 It = Lattice.find(Key2);
151 ASSERT_NE(It, Lattice.end());
152 EXPECT_EQ(It->second, BooleanLattice(false));
153 }
154
TEST(MapLatticeTest,ContainsWorks)155 TEST(MapLatticeTest, ContainsWorks) {
156 MapLattice<int, BooleanLattice> Lattice;
157 Lattice.insert({Key1, BooleanLattice(true)});
158 EXPECT_TRUE(Lattice.contains(Key1));
159 EXPECT_FALSE(Lattice.contains(Key2));
160 }
161 } // namespace
162