[analysis] Implement a vector lattice (#6058)

The vector lattice is nearly identical to the array lattice, except that the
size of the elements is specified at runtime when the lattice object is created
rather than at compile time. The code and tests are largely copy-pasted and
fixed up from the array implementation, but there are a couple differences.
First, initializing vector elements does not need the template magic used to
initialize array elements. Second, the obvious implementations of join and meet
do not work for vectors of bools because they might be specialized to be bit
vectors, so we need workarounds for that particular case.

2 files changed, 139 insertions, 0 deletions

diff --git a/src/analysis/lattices/array.h b/src/analysis/lattices/array.h
index 3426a3a77..7ac027302 100644
--- a/src/analysis/lattices/array.h
+++ b/src/analysis/lattices/array.h
@@ -27,6 +27,7 @@
 namespace wasm::analysis {
 
 // A lattice whose elements are N-tuples of elements of L. Also written as L^N.
+// N is supplied at compile time rather than run time like it is for Vector.
 template<Lattice L, size_t N> struct Array {
   using Element = std::array<typename L::Element, N>;
 
diff --git a/src/analysis/lattices/vector.h b/src/analysis/lattices/vector.h
new file mode 100644
index 000000000..d13380868
--- /dev/null
+++ b/src/analysis/lattices/vector.h
@@ -0,0 +1,138 @@
+/*
+ * Copyright 2023 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef wasm_analysis_lattices_vector_h
+#define wasm_analysis_lattices_vector_h
+
+#include <vector>
+
+#include "../lattice.h"
+#include "bool.h"
+#include "flat.h"
+
+namespace wasm::analysis {
+
+// A lattice whose elements are N-tuples of elements of L. Also written as L^N.
+// N is supplied at run time rather than compile time like it is for Array.
+template<Lattice L> struct Vector {
+  using Element = std::vector<typename L::Element>;
+
+  L lattice;
+  const size_t size;
+
+  Vector(L&& lattice, size_t size) : lattice(std::move(lattice)), size(size) {}
+
+  Element getBottom() const noexcept {
+    return Element(size, lattice.getBottom());
+  }
+
+  Element getTop() const noexcept
+#if __cplusplus >= 202002L
+    requires FullLattice<L>
+#endif
+  {
+    return Element(size, lattice.getTop());
+  }
+
+  // `a` <= `b` if their elements are pairwise <=, etc. Unless we determine
+  // that there is no relation, we must check all the elements.
+  LatticeComparison compare(const Element& a, const Element& b) const noexcept {
+    assert(a.size() == size);
+    assert(b.size() == size);
+    auto result = EQUAL;
+    for (size_t i = 0; i < size; ++i) {
+      switch (lattice.compare(a[i], b[i])) {
+        case NO_RELATION:
+          return NO_RELATION;
+        case EQUAL:
+          continue;
+        case LESS:
+          if (result == GREATER) {
+            // Cannot be both less and greater.
+            return NO_RELATION;
+          }
+          result = LESS;
+          continue;
+        case GREATER:
+          if (result == LESS) {
+            // Cannot be both greater and less.
+            return NO_RELATION;
+          }
+          result = GREATER;
+          continue;
+      }
+    }
+    return result;
+  }
+
+  // Pairwise join on the elements.
+  bool join(Element& joinee, const Element& joiner) const noexcept {
+    assert(joinee.size() == size);
+    assert(joiner.size() == size);
+    bool result = false;
+    for (size_t i = 0; i < size; ++i) {
+      if constexpr (std::is_same_v<typename L::Element, bool>) {
+        // The vector<bool> specialization does not expose references to the
+        // individual bools because they might be in a bitmap, so we need a
+        // workaround.
+        bool e = joinee[i];
+        if (lattice.join(e, joiner[i])) {
+          joinee[i] = e;
+          result = true;
+        }
+      } else {
+        result |= lattice.join(joinee[i], joiner[i]);
+      }
+    }
+
+    return result;
+  }
+
+  // Pairwise meet on the elements.
+  bool meet(Element& meetee, const Element& meeter) const noexcept
+#if __cplusplus >= 202002L
+    requires FullLattice<L>
+#endif
+  {
+    assert(meetee.size() == size);
+    assert(meeter.size() == size);
+    bool result = false;
+    for (size_t i = 0; i < size; ++i) {
+      if constexpr (std::is_same_v<typename L::Element, bool>) {
+        // The vector<bool> specialization does not expose references to the
+        // individual bools because they might be in a bitmap, so we need a
+        // workaround.
+        bool e = meetee[i];
+        if (lattice.meet(e, meeter[i])) {
+          meetee[i] = e;
+          result = true;
+        }
+      } else {
+        result |= lattice.meet(meetee[i], meeter[i]);
+      }
+    }
+    return result;
+  }
+};
+
+#if __cplusplus >= 202002L
+static_assert(FullLattice<Vector<Bool>>);
+static_assert(Lattice<Vector<Flat<bool>>>);
+#endif
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_vector_h