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:
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 
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::Pair;
54 using ::testing::UnorderedElementsAre;
55 
56 TEST(MapLatticeTest, InsertWorks) {
57   MapLattice<int, BooleanLattice> Lattice;
58   Lattice.insert({Key1, BooleanLattice(false)});
59   Lattice.insert({Key2, BooleanLattice(false)});
60 
61   EXPECT_THAT(Lattice, UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
62                                             Pair(Key2, BooleanLattice(false))));
63 }
64 
65 TEST(MapLatticeTest, ComparisonWorks) {
66   MapLattice<int, BooleanLattice> Lattice1;
67   Lattice1.insert({Key1, BooleanLattice(true)});
68   Lattice1.insert({Key2, BooleanLattice(false)});
69   MapLattice<int, BooleanLattice> Lattice2 = Lattice1;
70   EXPECT_EQ(Lattice1, Lattice2);
71 
72   Lattice2.find(Key2)->second = BooleanLattice(true);
73   EXPECT_NE(Lattice1, Lattice2);
74 }
75 
76 TEST(MapLatticeTest, JoinChange) {
77   MapLattice<int, BooleanLattice> Lattice1;
78   Lattice1.insert({Key1, BooleanLattice(false)});
79   Lattice1.insert({Key2, BooleanLattice(false)});
80 
81   MapLattice<int, BooleanLattice> Lattice2;
82   Lattice2.insert({Key1, BooleanLattice(true)});
83   Lattice2.insert({Key2, BooleanLattice(true)});
84 
85   ASSERT_THAT(Lattice1,
86               UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
87                                    Pair(Key2, BooleanLattice(false))));
88 
89   ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
90   EXPECT_THAT(Lattice1, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
91                                              Pair(Key2, BooleanLattice(true))));
92 }
93 
94 TEST(MapLatticeTest, JoinEqNoChange) {
95   MapLattice<int, BooleanLattice> Lattice;
96   Lattice.insert({Key1, BooleanLattice(false)});
97   Lattice.insert({Key2, BooleanLattice(false)});
98 
99   ASSERT_EQ(Lattice.join(Lattice), LatticeJoinEffect::Unchanged);
100   EXPECT_THAT(Lattice, UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
101                                             Pair(Key2, BooleanLattice(false))));
102 }
103 
104 TEST(MapLatticeTest, JoinLtNoChange) {
105   MapLattice<int, BooleanLattice> Lattice1;
106   Lattice1.insert({Key1, BooleanLattice(false)});
107   Lattice1.insert({Key2, BooleanLattice(false)});
108 
109   MapLattice<int, BooleanLattice> Lattice2;
110   Lattice2.insert({Key1, BooleanLattice(true)});
111   Lattice2.insert({Key2, BooleanLattice(true)});
112 
113   ASSERT_THAT(Lattice1,
114               UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
115                                    Pair(Key2, BooleanLattice(false))));
116 
117   ASSERT_THAT(Lattice2, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
118                                              Pair(Key2, BooleanLattice(true))));
119 
120   ASSERT_EQ(Lattice2.join(Lattice1), LatticeJoinEffect::Unchanged);
121   EXPECT_THAT(Lattice2, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
122                                              Pair(Key2, BooleanLattice(true))));
123 }
124 
125 TEST(MapLatticeTest, JoinDifferentDomainsProducesUnion) {
126   MapLattice<int, BooleanLattice> Lattice1;
127   Lattice1.insert({Key1, BooleanLattice(true)});
128   MapLattice<int, BooleanLattice> Lattice2;
129   Lattice2.insert({Key2, BooleanLattice(true)});
130 
131   ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
132   EXPECT_THAT(Lattice1, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
133                                              Pair(Key2, BooleanLattice(true))));
134 }
135 
136 TEST(MapLatticeTest, FindWorks) {
137   MapLattice<int, BooleanLattice> Lattice;
138   Lattice.insert({Key1, BooleanLattice(true)});
139   Lattice.insert({Key2, BooleanLattice(false)});
140 
141   auto It = Lattice.find(Key1);
142   ASSERT_NE(It, Lattice.end());
143   EXPECT_EQ(It->second, BooleanLattice(true));
144 
145   It = Lattice.find(Key2);
146   ASSERT_NE(It, Lattice.end());
147   EXPECT_EQ(It->second, BooleanLattice(false));
148 }
149 
150 TEST(MapLatticeTest, ContainsWorks) {
151   MapLattice<int, BooleanLattice> Lattice;
152   Lattice.insert({Key1, BooleanLattice(true)});
153   EXPECT_TRUE(Lattice.contains(Key1));
154   EXPECT_FALSE(Lattice.contains(Key2));
155 }
156 } // namespace
157