[analysis] Simplify the stack lattice (#6069)

Remove the ability to represent the top element of the stack lattice since it
isn't necessary. Also simplify the element type to be a simple vector, update
the lattice method implementations to be more consistent with implementations in
other lattices, and make the tests more consistent with the tests for other
lattices.

2 files changed, 26 insertions, 97 deletions

diff --git a/test/gtest/cfg.cpp b/test/gtest/cfg.cpp
index 9f037e644..583c8c4f0 100644
--- a/test/gtest/cfg.cpp
+++ b/test/gtest/cfg.cpp
@@ -411,100 +411,3 @@ TEST_F(CFGTest, ReachingDefinitionsLoop) {
 
   EXPECT_EQ(expectedResult, getSetses);
 }
-
-TEST_F(CFGTest, StackLatticeFunctioning) {
-  FiniteIntPowersetLattice contentLattice(4);
-  StackLattice<FiniteIntPowersetLattice> stackLattice(contentLattice);
-
-  // These are constructed as expected references to compare everything else.
-  StackLattice<FiniteIntPowersetLattice>::Element expectedStack =
-    stackLattice.getBottom();
-  FiniteIntPowersetLattice::Element expectedStackElement =
-    contentLattice.getBottom();
-
-  StackLattice<FiniteIntPowersetLattice>::Element firstStack =
-    stackLattice.getBottom();
-  StackLattice<FiniteIntPowersetLattice>::Element secondStack =
-    stackLattice.getBottom();
-
-  for (size_t i = 0; i < 4; i++) {
-    FiniteIntPowersetLattice::Element temp = contentLattice.getBottom();
-    for (size_t j = 0; j <= i; j++) {
-      temp.set(j, true);
-    }
-    firstStack.push(temp);
-    secondStack.push(temp);
-    if (i < 2) {
-      expectedStack.push(temp);
-    }
-  }
-
-  EXPECT_EQ(stackLattice.compare(firstStack, secondStack),
-            LatticeComparison::EQUAL);
-
-  for (size_t j = 0; j < 4; ++j) {
-    expectedStackElement.set(j, true);
-  }
-
-  EXPECT_EQ(contentLattice.compare(secondStack.pop(), expectedStackElement),
-            LatticeComparison::EQUAL);
-  expectedStackElement.set(3, false);
-  EXPECT_EQ(contentLattice.compare(secondStack.pop(), expectedStackElement),
-            LatticeComparison::EQUAL);
-
-  EXPECT_EQ(stackLattice.compare(firstStack, secondStack),
-            LatticeComparison::GREATER);
-  EXPECT_EQ(stackLattice.compare(secondStack, firstStack),
-            LatticeComparison::LESS);
-
-  EXPECT_EQ(stackLattice.compare(secondStack, expectedStack),
-            LatticeComparison::EQUAL);
-
-  {
-    expectedStack.stackTop().set(0, false);
-    expectedStack.stackTop().set(2, true);
-    FiniteIntPowersetLattice::Element temp = expectedStack.pop();
-    expectedStack.stackTop().set(3, true);
-    expectedStack.push(temp);
-
-    FiniteIntPowersetLattice::Element temp2 = contentLattice.getBottom();
-    temp2.set(1, true);
-    temp2.set(3, true);
-    expectedStack.push(temp2);
-  }
-
-  StackLattice<FiniteIntPowersetLattice>::Element thirdStack =
-    stackLattice.getBottom();
-  {
-    FiniteIntPowersetLattice::Element temp = contentLattice.getBottom();
-    temp.set(0, true);
-    temp.set(3, true);
-    FiniteIntPowersetLattice::Element temp2 = contentLattice.getBottom();
-    temp2.set(1, true);
-    temp2.set(2, true);
-    FiniteIntPowersetLattice::Element temp3 = contentLattice.getBottom();
-    temp3.set(1, true);
-    temp3.set(3, true);
-    thirdStack.push(std::move(temp));
-    thirdStack.push(std::move(temp2));
-    thirdStack.push(std::move(temp3));
-  }
-
-  EXPECT_EQ(stackLattice.compare(secondStack, thirdStack),
-            LatticeComparison::NO_RELATION);
-
-  EXPECT_EQ(stackLattice.compare(thirdStack, expectedStack),
-            LatticeComparison::EQUAL);
-
-  EXPECT_TRUE(stackLattice.join(thirdStack, secondStack));
-
-  {
-    expectedStack.stackTop().set(0, true);
-    FiniteIntPowersetLattice::Element temp = expectedStack.pop();
-    expectedStack.stackTop().set(0, true);
-    expectedStack.push(temp);
-  }
-
-  EXPECT_EQ(stackLattice.compare(thirdStack, expectedStack),
-            LatticeComparison::EQUAL);
-}
diff --git a/test/gtest/lattices.cpp b/test/gtest/lattices.cpp
index 49288fe85..ed4f48e38 100644
--- a/test/gtest/lattices.cpp
+++ b/test/gtest/lattices.cpp
@@ -21,6 +21,7 @@
 #include "analysis/lattices/inverted.h"
 #include "analysis/lattices/lift.h"
 #include "analysis/lattices/shared.h"
+#include "analysis/lattices/stack.h"
 #include "analysis/lattices/tuple.h"
 #include "analysis/lattices/valtype.h"
 #include "analysis/lattices/vector.h"
@@ -654,3 +655,28 @@ TEST(SharedLattice, Join) {
     EXPECT_EQ(elem, two);
   }
 }
+
+TEST(StackLattice, GetBottom) {
+  analysis::Stack stack{analysis::Flat<uint32_t>{}};
+  EXPECT_EQ(stack.getBottom().size(), 0u);
+}
+
+TEST(StackLattice, Compare) {
+  analysis::Stack stack{analysis::Flat<uint32_t>{}};
+  auto& flat = stack.lattice;
+  testDiamondCompare(stack,
+                     {},
+                     {flat.get(0)},
+                     {flat.get(0), flat.get(1)},
+                     {flat.get(0), flat.getTop()});
+}
+
+TEST(StackLattice, Join) {
+  analysis::Stack stack{analysis::Flat<uint32_t>{}};
+  auto& flat = stack.lattice;
+  testDiamondJoin(stack,
+                  {},
+                  {flat.get(0)},
+                  {flat.get(0), flat.get(1)},
+                  {flat.get(0), flat.getTop()});
+}