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
8using namespace clang;
9using namespace dataflow;
10
11namespace {
12// A simple lattice for basic tests.
13class BooleanLattice {
14public:
15 BooleanLattice() : Value(false) {}
16 explicit BooleanLattice(bool B) : Value(B) {}
17
18 static BooleanLattice bottom() { return BooleanLattice(false); }
19
20 static BooleanLattice top() { return BooleanLattice(true); }
21
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
29 friend bool operator==(BooleanLattice LHS, BooleanLattice RHS) {
30 return LHS.Value == RHS.Value;
31 }
32
33 friend bool operator!=(BooleanLattice LHS, BooleanLattice RHS) {
34 return LHS.Value != RHS.Value;
35 }
36
37 friend std::ostream &operator<<(std::ostream &Os, const BooleanLattice &B) {
38 Os << B.Value;
39 return Os;
40 }
41
42 bool value() const { return Value; }
43
44private:
45 bool Value;
46};
47} // namespace
48
49static constexpr int Key1 = 0;
50static constexpr int Key2 = 1;
51
52namespace {
53using ::testing::_;
54using ::testing::Pair;
55using ::testing::UnorderedElementsAre;
56
57TEST(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
70TEST(MapLatticeTest, ComparisonWorks) {
71 MapLattice<int, BooleanLattice> Lattice1;
72 Lattice1.insert(P: {Key1, BooleanLattice(true)});
73 Lattice1.insert(P: {Key2, BooleanLattice(false)});
74 MapLattice<int, BooleanLattice> Lattice2 = Lattice1;
75 EXPECT_EQ(Lattice1, Lattice2);
76
77 Lattice2.find(K: Key2)->second = BooleanLattice(true);
78 EXPECT_NE(Lattice1, Lattice2);
79}
80
81TEST(MapLatticeTest, JoinChange) {
82 MapLattice<int, BooleanLattice> Lattice1;
83 Lattice1.insert(P: {Key1, BooleanLattice(false)});
84 Lattice1.insert(P: {Key2, BooleanLattice(false)});
85
86 MapLattice<int, BooleanLattice> Lattice2;
87 Lattice2.insert(P: {Key1, BooleanLattice(true)});
88 Lattice2.insert(P: {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
99TEST(MapLatticeTest, JoinEqNoChange) {
100 MapLattice<int, BooleanLattice> Lattice;
101 Lattice.insert(P: {Key1, BooleanLattice(false)});
102 Lattice.insert(P: {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
109TEST(MapLatticeTest, JoinLtNoChange) {
110 MapLattice<int, BooleanLattice> Lattice1;
111 Lattice1.insert(P: {Key1, BooleanLattice(false)});
112 Lattice1.insert(P: {Key2, BooleanLattice(false)});
113
114 MapLattice<int, BooleanLattice> Lattice2;
115 Lattice2.insert(P: {Key1, BooleanLattice(true)});
116 Lattice2.insert(P: {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
130TEST(MapLatticeTest, JoinDifferentDomainsProducesUnion) {
131 MapLattice<int, BooleanLattice> Lattice1;
132 Lattice1.insert(P: {Key1, BooleanLattice(true)});
133 MapLattice<int, BooleanLattice> Lattice2;
134 Lattice2.insert(P: {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
141TEST(MapLatticeTest, FindWorks) {
142 MapLattice<int, BooleanLattice> Lattice;
143 Lattice.insert(P: {Key1, BooleanLattice(true)});
144 Lattice.insert(P: {Key2, BooleanLattice(false)});
145
146 auto It = Lattice.find(K: Key1);
147 ASSERT_NE(It, Lattice.end());
148 EXPECT_EQ(It->second, BooleanLattice(true));
149
150 It = Lattice.find(K: Key2);
151 ASSERT_NE(It, Lattice.end());
152 EXPECT_EQ(It->second, BooleanLattice(false));
153}
154
155TEST(MapLatticeTest, ContainsWorks) {
156 MapLattice<int, BooleanLattice> Lattice;
157 Lattice.insert(P: {Key1, BooleanLattice(true)});
158 EXPECT_TRUE(Lattice.contains(Key1));
159 EXPECT_FALSE(Lattice.contains(Key2));
160}
161} // namespace
162

source code of clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp