162 lines · 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 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::Unchanged26 : 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} // namespace48 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({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 81TEST(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 99TEST(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 109TEST(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 130TEST(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 141TEST(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 155TEST(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} // namespace162