[analysis] Add a FullLattice concept and Inverted lattice (#6038)

The FullLattice concept extends the base Lattice with `getTop` and `meet`
operations. The `Inverted` lattice uses these operations to reverse the order of
an arbitrary full lattice, for example to create a lattice of integers ordered
by `>` rather than by `<`.

1 files changed, 49 insertions, 0 deletions

diff --git a/src/analysis/lattices/inverted.h b/src/analysis/lattices/inverted.h
new file mode 100644
index 000000000..57f708421
--- /dev/null
+++ b/src/analysis/lattices/inverted.h
@@ -0,0 +1,49 @@
+/*
+ * 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_inverted_h
+#define wasm_analysis_lattices_inverted_h
+
+#include <utility>
+
+#include "../lattice.h"
+
+namespace wasm::analysis {
+
+// Reverses the order of an arbitrary full lattice. For example,
+// `Inverted<UInt32>` would order uint32_t values by > rather than by <.
+template<FullLattice L> struct Inverted {
+  using Element = typename L::Element;
+
+  L lattice;
+  Inverted(L&& lattice) : lattice(std::move(lattice)) {}
+
+  Element getBottom() const noexcept { return lattice.getTop(); }
+  Element getTop() const noexcept { return lattice.getBottom(); }
+  LatticeComparison compare(const Element& a, const Element& b) const noexcept {
+    return reverseComparison(lattice.compare(a, b));
+  }
+  bool join(Element& self, Element other) const noexcept {
+    return lattice.meet(self, other);
+  }
+  bool meet(Element& self, Element other) const noexcept {
+    return lattice.join(self, other);
+  }
+};
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_inverted_h