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::_;
54 using ::testing::Pair;
55 using ::testing::UnorderedElementsAre;
56 
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 
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 
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 
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 
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 
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 
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 
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