Commit 6aa04fa
authored
Equirecursive type canonicalization (WebAssembly#3717)
* Equirecursive type canonicalization
Use Hopcroft's DFA minimization algorithm to properly canonicalize and
deduplicate recursive types. Type canonicalization has two stages:
1. Shape canonicalization
- The top-level structure of HeapTypes is used to split the declared HeapTypes
into their initial partitions.
- Hopcroft's algorithm refines the partitions such that all pairs of
distinguishable types end up in different partitions.
- A fresh HeapTypeInfo is created for each final partition. Each new
HeapTypeInfo is linked to other new HeapTypeInfos to create a minimal type
definition graph that defines the same types as the original graph.
2. Global canonicalization
- Each new minimal HeapTypeInfo that does not have the same finite
shape as an existing globally canonical HeapTypeInfo is moved to the
global heap type store to become the new canonical HeapTypeInfo.
- Each temporary Type referenced by the newly canonical HeapTypeInfos is
replaced in-place with the equivalent canonical Type to avoid leaking
temporary Types into the global stores.1 parent f2abcbc commit 6aa04fa
4 files changed
Lines changed: 768 additions & 375 deletions
0 commit comments