From b89b601a36e9cfe17dc1f09c641266ac2a715299 Mon Sep 17 00:00:00 2001 From: Thomas Lively <7121787+tlively@users.noreply.github.com> Date: Thu, 25 Feb 2021 16:21:35 -0800 Subject: Support comparing, subtyping, and naming recursive types (#3610) When the type section is emitted, types with an equal amount of references are ordered by an arbitrary measure of simplicity, which previously would infinitely recurse on structurally equivalent recursive types. Similarly, calculating whether an recursive type was a subtype of another recursive type could have infinitely recursed. This PR avoids infinite recursions in both cases by switching the algorithms from using normal inductive recursion to using coinductive recursion. The difference is that while the inductive algorithms assume the relations do not hold for a pair of HeapTypes until they have been exhaustively shown to hold, the coinductive algorithms assume the relations hold unless a counterexample can be found. In addition to those two algorithms, this PR also implement name generation for recursive types, using de Bruijn indices to stand in for inner uses of the recursive types. There are additional algorithms that will need to be switched from inductive to coinductive recursion, such as least upper bound generation, but these presented a good starting point and are sufficient to get some interesting programs working end-to-end. --- src/ir/module-utils.h | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) (limited to 'src/ir/module-utils.h') diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h index 84ef3a508..4792c5d23 100644 --- a/src/ir/module-utils.h +++ b/src/ir/module-utils.h @@ -485,11 +485,8 @@ inline void collectHeapTypes(Module& wasm, for (auto& curr : wasm.functions) { counts.note(curr->sig); for (auto type : curr->vars) { - counts.maybeNote(type); - if (type.isTuple()) { - for (auto t : type) { - counts.maybeNote(t); - } + for (auto t : type) { + counts.maybeNote(t); } } } -- cgit v1.2.3