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.

3 files changed, 37 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();
diff --git a/test/lit/recursive-type-sort.wast b/test/lit/recursive-type-sort.wast
new file mode 100644
index 000000000..087cb7fe6
--- /dev/null
+++ b/test/lit/recursive-type-sort.wast
@@ -0,0 +1,29 @@
+;; Test that multiple recursive types are sorted and emitted properly.
+;; Regression test for a bug in TypeComparator that made it fail to properly
+;; implement the C++ Compare requirements. See #3648.
+
+;; RUN: wasm-opt %s -all --roundtrip -S -o - | filecheck %s
+
+;; Check that there's no crash.
+;; CHECK: module
+
+(module
+ (type $a (func (param (ref null $b))))
+ (type $b (struct (field (ref null $i))))
+ (type $c (struct (field (ref null $l))))
+ (type $d (func (param (ref null $b))))
+ (type $e (func (result (ref null $g))))
+ (type $f (func (result (ref null $c))))
+ (type $g (struct (field (ref null $j))))
+ (type $h (struct (field (ref null $k))))
+ (type $i (struct (field (mut (ref null $a)))))
+ (type $j (struct (field (mut (ref null $a))) (field (mut (ref null $a)))))
+ (type $k (struct (field (mut (ref null $a))) (field (mut (ref null $a))) (field (mut (ref null $e)))))
+ (type $l (struct (field (mut (ref null $a))) (field (mut (ref null $d))) (field (mut (ref null $f)))))
+
+ (func $foo
+  (local $1 (ref null $h))
+  (local $2 (ref null $b))
+  (local $3 (ref null $c))
+ )
+)