Isorecursive canonicalization (#4481)

Isorecursive canonicalization is similar to equirecursive canonicalization in
that it deduplicates types based on their structure, but unlike equirecursive
canonicalization, isorecursive canonicalization does not need to minimize the
type definition first. Another difference is that structures are deduplicated at
the level of recursion groups rather than individual types, so we cannot reuse
the existing `FiniteShapeHasher` and `FiniteShapeEquator` utilities. Instead,
introduce a new `RecGroupStructure` wrapper that provides equality comparison
and hashing very similar to the former utilities.

Another feature of the isorecursive type system is that its constraints on the
order of recursion groups means that they are already topologically sorted and
can be incrementally canonicalized in a bottom-up manner. This incremental
canonicalization means that the `RecGroupStructure` utility can assume that all
child `HeapTypes` have already been canonicalized and can avoid traversing
anything but the top-level type definitions in the wrapped recursion group. The
only exception is self-references into the wrapped recursion group itself, which
may not be canonical. That special case is detected and handled without any
nontrivial extra work.

Overall, the canonicalization algorithm traverses each type definition once to
canonicalize its `HeapType` use sites, then once to hash its recursion group
structure, then finally once to canonicalize its `Type` use sites in
`globallyCanonicalize`, giving only linear time complexity.

1 files changed, 142 insertions, 9 deletions

diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp
index 9cbd04298..8f922380d 100644
--- a/test/gtest/type-builder.cpp
+++ b/test/gtest/type-builder.cpp
@@ -16,6 +16,17 @@ protected:
     destroyAllTypesForTestingPurposesOnly();
     setTypeSystem(originalSystem);
   }
+
+  // Utilities
+  Struct makeStruct(TypeBuilder& builder,
+                    std::initializer_list<size_t> indices) {
+    FieldList fields;
+    for (auto index : indices) {
+      Type ref = builder.getTempRefType(builder[index], Nullable);
+      fields.emplace_back(ref, Mutable);
+    }
+    return Struct(std::move(fields));
+  }
 };
 
 using TypeTest = TypeSystemTest<TypeSystem::Equirecursive>;
@@ -214,15 +225,6 @@ static void testInvalidSupertype() {
 TEST_F(NominalTest, InvalidSupertype) { testInvalidSupertype(); }
 TEST_F(IsorecursiveTest, InvalidSupertype) { testInvalidSupertype(); }
 
-TEST_F(IsorecursiveTest, SelfReferencedChild) {
-  // A self-referential type should be ok even without an explicit rec group.
-  TypeBuilder builder(1);
-  Type selfRef = builder.getTempRefType(builder[0], Nullable);
-  builder[0] = Struct({Field(selfRef, Immutable)});
-  auto result = builder.build();
-  EXPECT_TRUE(result);
-}
-
 TEST_F(IsorecursiveTest, ForwardReferencedChild) {
   TypeBuilder builder(3);
   builder.createRecGroup(0, 2);
@@ -269,3 +271,134 @@ TEST_F(IsorecursiveTest, RecGroupIndices) {
   EXPECT_EQ(built[3].getRecGroupIndex(), 1u);
   EXPECT_EQ(built[4].getRecGroupIndex(), 2u);
 }
+
+TEST_F(IsorecursiveTest, CanonicalizeGroups) {
+  // Trivial types in the same group are not equivalent.
+  TypeBuilder builderA(2);
+  builderA.createRecGroup(0, 2);
+  builderA[0] = Struct{};
+  builderA[1] = Struct{};
+  auto resultA = builderA.build();
+  ASSERT_TRUE(resultA);
+  auto builtA = *resultA;
+
+  EXPECT_NE(builtA[0], builtA[1]);
+
+  // But if they are in their own separate groups, they are equivalent.
+  TypeBuilder builderB(2);
+  builderB[0] = Struct{};
+  builderB[1] = Struct{};
+  auto resultB = builderB.build();
+  ASSERT_TRUE(resultB);
+  auto builtB = *resultB;
+
+  EXPECT_EQ(builtB[0], builtB[1]);
+  EXPECT_NE(builtB[0], builtA[0]);
+  EXPECT_NE(builtB[0], builtA[1]);
+
+  // If we build the same groups again, we should get the same results.
+  TypeBuilder builderA2(4);
+  builderA2.createRecGroup(0, 2);
+  builderA2.createRecGroup(2, 2);
+  builderA2[0] = Struct{};
+  builderA2[1] = Struct{};
+  builderA2[2] = Struct{};
+  builderA2[3] = Struct{};
+  auto resultA2 = builderA2.build();
+  ASSERT_TRUE(resultA2);
+  auto builtA2 = *resultA2;
+
+  EXPECT_EQ(builtA2[0], builtA[0]);
+  EXPECT_EQ(builtA2[1], builtA[1]);
+  EXPECT_EQ(builtA2[2], builtA[0]);
+  EXPECT_EQ(builtA2[3], builtA[1]);
+
+  TypeBuilder builderB2(1);
+  builderB2[0] = Struct{};
+  auto resultB2 = builderB2.build();
+  ASSERT_TRUE(resultB2);
+  auto builtB2 = *resultB2;
+
+  EXPECT_EQ(builtB2[0], builtB[0]);
+}
+
+TEST_F(IsorecursiveTest, CanonicalizeUses) {
+  TypeBuilder builder(8);
+  builder[0] = makeStruct(builder, {});
+  builder[1] = makeStruct(builder, {});
+  builder[2] = makeStruct(builder, {0});
+  builder[3] = makeStruct(builder, {1});
+  builder[4] = makeStruct(builder, {0, 2});
+  builder[5] = makeStruct(builder, {1, 3});
+  builder[6] = makeStruct(builder, {2, 4});
+  builder[7] = makeStruct(builder, {3, 5});
+
+  auto result = builder.build();
+  ASSERT_TRUE(result);
+  auto built = *result;
+
+  EXPECT_EQ(built[0], built[1]);
+  EXPECT_EQ(built[2], built[3]);
+  EXPECT_EQ(built[4], built[5]);
+  EXPECT_EQ(built[6], built[7]);
+
+  EXPECT_NE(built[0], built[2]);
+  EXPECT_NE(built[0], built[4]);
+  EXPECT_NE(built[0], built[6]);
+  EXPECT_NE(built[2], built[4]);
+  EXPECT_NE(built[2], built[6]);
+  EXPECT_NE(built[4], built[6]);
+}
+
+TEST_F(IsorecursiveTest, CanonicalizeSelfReferences) {
+  TypeBuilder builder(5);
+  // Single self-reference
+  builder[0] = makeStruct(builder, {0});
+  builder[1] = makeStruct(builder, {1});
+  // Single other reference
+  builder[2] = makeStruct(builder, {0});
+  // Other reference followed by self-reference
+  builder[3] = makeStruct(builder, {2, 3});
+  // Self-reference followed by other reference
+  builder[4] = makeStruct(builder, {4, 2});
+
+  auto result = builder.build();
+  ASSERT_TRUE(result);
+  auto built = *result;
+
+  EXPECT_EQ(built[0], built[1]);
+
+  EXPECT_NE(built[0], built[2]);
+  EXPECT_NE(built[0], built[3]);
+  EXPECT_NE(built[0], built[4]);
+  EXPECT_NE(built[2], built[3]);
+  EXPECT_NE(built[2], built[4]);
+  EXPECT_NE(built[3], built[4]);
+}
+
+TEST_F(IsorecursiveTest, CanonicalizeSupertypes) {
+  TypeBuilder builder(6);
+  builder[0] = Struct{};
+  builder[1] = Struct{};
+  // Type with a supertype
+  builder[2] = Struct{};
+  builder[2].subTypeOf(builder[0]);
+  // Type with the same supertype after canonicalization.
+  builder[3] = Struct{};
+  builder[3].subTypeOf(builder[1]);
+  // Type with a different supertype
+  builder[4] = Struct{};
+  builder[4].subTypeOf(builder[2]);
+  // Type with no supertype
+  builder[5] = Struct{};
+
+  auto result = builder.build();
+  ASSERT_TRUE(result);
+  auto built = *result;
+
+  EXPECT_EQ(built[2], built[3]);
+
+  EXPECT_NE(built[3], built[4]);
+  EXPECT_NE(built[3], built[5]);
+  EXPECT_NE(built[4], built[5]);
+}