clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp

   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