Fix TypeComparator to satisfy C++'s Compare requirement (#3650)

The comparison implemented by TypeComparator was not previously antisymmetric
because it held that both A < B and B < A when A and B were structurally
identical but nominally distinct recursive types. This meant that it did not
satisfy the conditions of C++'s "Compare" requirement, which meant that std::set
did not operate correctly, as discovered in #3648. The PR fixes the problem by
having making A < B be false (and vice versa), making type comparisons properly
antisymmetric.

As a drive by, also switches to using std::stable_sort in collectHeapTypes to
make the order of the type section completely deterministic accross platforms.

Fixes #3648.

2 files changed, 8 insertions, 8 deletions

diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 4792c5d23..371239e19 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -550,7 +550,7 @@ inline void collectHeapTypes(Module& wasm,
 
   // Sort by frequency and then simplicity.
   std::vector<std::pair<HeapType, size_t>> sorted(counts.begin(), counts.end());
-  std::sort(sorted.begin(), sorted.end(), [&](auto a, auto b) {
+  std::stable_sort(sorted.begin(), sorted.end(), [&](auto a, auto b) {
     if (a.second != b.second) {
       return a.second > b.second;
     }
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 8546e3fc9..e4e7d31a4 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -100,8 +100,8 @@ struct HeapTypeInfo {
 // Helper for coinductively comparing Types and HeapTypes according to some
 // arbitrary notion of complexity.
 struct TypeComparator {
-  // Set of HeapTypes we are assuming satisfy the relation as long as we cannot
-  // prove otherwise.
+  // Set of HeapTypes we are assuming are equivalent as long as we cannot prove
+  // otherwise.
   std::unordered_set<std::pair<HeapType, HeapType>> seen;
   bool lessThan(Type a, Type b);
   bool lessThan(HeapType a, HeapType b);
@@ -118,8 +118,8 @@ struct TypeComparator {
 // Helper for coinductively checking whether a pair of Types or HeapTypes are in
 // a subtype relation.
 struct SubTyper {
-  // Set of HeapTypes we are assuming satisfy the relation as long as we cannot
-  // prove otherwise.
+  // Set of HeapTypes we are assuming are equivalent as long as we cannot prove
+  // otherwise.
   std::unordered_set<std::pair<HeapType, HeapType>> seen;
   bool isSubType(Type a, Type b);
   bool isSubType(HeapType a, HeapType b);
@@ -858,9 +858,9 @@ bool TypeComparator::lessThan(HeapType a, HeapType b) {
     return false;
   }
   if (seen.count({a, b})) {
-    // We weren't able to disprove that a < b since we last saw them, so the
-    // relation holds coinductively.
-    return true;
+    // We weren't able to disprove that a == b since we last saw them, so it
+    // holds coinductively that a < b is false.
+    return false;
   }
   if (a.isBasic() && b.isBasic()) {
     return a.getBasic() < b.getBasic();