Add a utility for comparing and hashing rec group shapes (#6808)

This is very similar to the internal utilities for canonicalizing rec
groups in the type system implementation, except that the new utility
also supports ordered comparison of rec groups, and of course the new
utility only uses the public type API.

A follow-up PR will replace the internal implementation of rec group
comparison and hashing in the type system with this one.

Another follow-up PR will use this new utility in a type optimization.

1 files changed, 94 insertions, 0 deletions

diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index ecd8883b1..074d235c9 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -23,6 +23,7 @@
 #include "tools/fuzzing/heap-types.h"
 #include "tools/fuzzing/random.h"
 #include "wasm-type-printing.h"
+#include "wasm-type-shape.h"
 
 namespace wasm {
 
@@ -54,6 +55,7 @@ struct Fuzzer {
   void checkLUBs() const;
   void checkCanonicalization();
   void checkInhabitable();
+  void checkRecGroupShapes();
 };
 
 void Fuzzer::run(uint64_t seed) {
@@ -88,6 +90,7 @@ void Fuzzer::run(uint64_t seed) {
   checkLUBs();
   checkCanonicalization();
   checkInhabitable();
+  checkRecGroupShapes();
 }
 
 void Fuzzer::printTypes(const std::vector<HeapType>& types) {
@@ -509,6 +512,97 @@ void Fuzzer::checkInhabitable() {
   }
 }
 
+void Fuzzer::checkRecGroupShapes() {
+  using ShapeHash = std::hash<RecGroupShape>;
+
+  // Collect the groups and order types by index.
+  std::vector<std::vector<HeapType>> groups;
+  std::unordered_map<HeapType, Index> typeIndices;
+  for (auto type : types) {
+    typeIndices.insert({type, typeIndices.size()});
+    // We know we are at the beginning of a new rec group when we see a type
+    // that is at index zero of its rec group.
+    if (type.getRecGroupIndex() == 0) {
+      groups.push_back({type});
+    } else {
+      assert(!groups.empty());
+      groups.back().push_back(type);
+    }
+  }
+
+  auto less = [&typeIndices](HeapType a, HeapType b) {
+    return typeIndices.at(a) < typeIndices.at(b);
+  };
+
+  for (size_t i = 0; i < groups.size(); ++i) {
+    ComparableRecGroupShape shape(groups[i], less);
+    // A rec group should compare equal to itself.
+    if (shape != shape) {
+      Fatal() << "Rec group shape " << i << " not equal to itself";
+    }
+
+    // Its hash should be deterministic
+    auto hash = ShapeHash{}(shape);
+    if (hash != ShapeHash{}(shape)) {
+      Fatal() << "Rec group shape " << i << " has non-deterministic hash";
+    }
+
+    // Check how it compares to other groups.
+    for (size_t j = i + 1; j < groups.size(); ++j) {
+      ComparableRecGroupShape other(groups[j], less);
+      bool isLess = shape < other;
+      bool isEq = shape == other;
+      bool isGreater = shape > other;
+      if (isLess + isEq + isGreater == 0) {
+        Fatal() << "Rec groups " << i << " and " << j
+                << " do not have comparable shapes";
+      }
+      if (isLess + isEq + isGreater > 1) {
+        std::string comparisons;
+        auto append = [&](std::string comp) {
+          comparisons = comparisons == "" ? comp : comparisons + ", " + comp;
+        };
+        if (isLess) {
+          append("<");
+        }
+        if (isEq) {
+          append("==");
+        }
+        if (isGreater) {
+          append(">");
+        }
+        Fatal() << "Rec groups " << i << " and " << j << " compare "
+                << comparisons;
+      }
+
+      auto otherHash = ShapeHash{}(other);
+      if (isEq) {
+        if (hash != otherHash) {
+          Fatal() << "Equivalent rec groups " << i << " and " << j
+                  << " do not have equivalent hashes";
+        }
+      } else {
+        // Hash collisions are technically possible, but should be rare enough
+        // that we can consider them bugs if the fuzzer finds them.
+        if (hash == otherHash) {
+          Fatal() << "Hash collision between rec groups " << i << " and " << j;
+        }
+      }
+
+      if (j + 1 < groups.size()) {
+        // Check transitivity.
+        RecGroupShape third(groups[j + 1]);
+        if ((isLess && other <= third && shape >= third) ||
+            (isEq && other == third && shape != third) ||
+            (isGreater && other >= third && shape <= third)) {
+          Fatal() << "Comparison between rec groups " << i << ", " << j
+                  << ", and " << (j + 1) << " is not transitive";
+        }
+      }
+    }
+  }
+}
+
 } // namespace wasm
 
 int main(int argc, const char* argv[]) {