Stream: git-wasmtime

Topic: wasmtime / PR #12577 Add struct subtypes

Wasmtime GitHub notifications bot (Feb 12 2026 at 04:24):

khagankhan opened PR #12577 from khagankhan:struct-subtypes to bytecodealliance:main:

Add support for struct subtyping

This PR adds support for one struct type being a subtype of another.

Changes

• SubType now has:
  • supertype: Option<TypeId>
  • is_final: bool
• Mutators may:
  • Randomly assign an existing struct as supertype
  • Mark a type as final with 1/4 probability

Cycle Handling

• Types::merge_rec_groups_via_scc(...):
  • Finds cycles across rec-groups and merges them.
• Types::break_type_cycles_in_rec_groups(...):
  • Breaks cycles within a rec-group by clearing supertype.

Ordering

• Rec-groups are topologically sorted using Kahn topo-sort.
• Types are sorted via DFS (Enter/Exit enum) so supertypes come before subtypes.

Fixups

Handled in Types::fixup:

• If a subtype references a final supertype its supertype becomes None
• If a supertype is removed, its subtypes has no supertype anyome (becomes None)

Mutator Update

• duplicate_rec_group now actually duplicates.

New tests added.

cc @fitzgen @eeide

Wasmtime GitHub notifications bot (Feb 12 2026 at 04:24):

khagankhan requested wasmtime-fuzz-reviewers for a review on PR #12577.

Wasmtime GitHub notifications bot (Feb 12 2026 at 04:24):

khagankhan requested fitzgen for a review on PR #12577.

Wasmtime GitHub notifications bot (Feb 12 2026 at 04:48):

khagankhan updated PR #12577.

Wasmtime GitHub notifications bot (Feb 12 2026 at 06:04):

github-actions[bot] added the label fuzzing on PR #12577.

Wasmtime GitHub notifications bot (Feb 12 2026 at 07:04):

github-actions[bot] commented on PR #12577:

Subscribe to Label Action

cc @fitzgen

<details>
This issue or pull request has been labeled: "fuzzing"

Thus the following users have been cc'd because of the following labels:

• fitzgen: fuzzing

To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.

Learn more.
</details>

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen created PR review comment:

The DFS should handle this special case in a general way already, right? I think we can remove this.

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen created PR review comment:

Ah okay, great. Yeah we should make this DFS code generic and reuse in our various places where we need to do a DFS.

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen created PR review comment:

Allocating these things within this double-nested loop is going to thrash the allocator and be quite slow. I think this DFS could be refactored to be more sympathatic to the machine and look something like this:

// A map from `TypeId` to the DFS index when we started traversing that type.
let mut dfs_pre_index = BTreeMap::new();

// A map from `TypeId` to the DFS index when we finished traversing that type.
let mut dfs_post_index = BTreeMap::new();

enum DfsEvent {
    Enter,
    Exit,
}
use DfsEvent::*;

let mut stack = self
    .all_type_ids() // new method that returns `impl Iterator<Item = TypeId>`
    .map(|ty| (Enter, ty))
    .collect::<Vec<_>>();

let mut index = 0;
while let Some((event, ty)) = stack.pop() {
    match event {
        Enter => match dfs_pre_index.entry(ty) {
            Entry::Occupied(_) => {},
            Entry::Vacant(e) => {
                e.insert(index);
                index += 1;

                stack.push((Exit, ty));

                if let Some(sup_ty) = self.type_defs[ty].supertype {
                    if dfs_pre_index.contains_key(&sup_ty) && !dfs_post_index.contains_key(&sup_ty) {
                        // Cyclic subtyping! Break the cycle.
                        self.type_defs[ty].supertype = None;
                    } else {
                        stack.push((Event::Enter, sup_ty));
                    }
                }
            }
        }
        Exit => {
            let old = dfs_post_index.insert(ty, index);
            debug_assert!(old.is_none());
            index += 1;
        }
    }
}

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen created PR review comment:

It occurs to me that we don't actually even need SCCs yet, since subtyping doesn't care about rec group boundaries so long as the supertype is defined before the subtype. So I think we can delay all this stuff until we actually have struct fields (or array elements). This is nice because it means that support for subtyping will be able to land before we make the existing SCC algorithm reusable and all that.

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen created PR review comment:

I already talked about how we can remove the SCC stuff in this PR, but for the future: this method should sort in place, rather than allocating and returning a new vector.

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen created PR review comment:

I think we will want to move our existing SCC implementation somewhere that it can be reused so that we don't have forks of the same code in the same tree.

I can do this and let you know when to rebase.

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen created PR review comment:

I don't think we should need to think about rec groups at all while breaking supertype cycles. The only constraint on a type's supertype is that the supertype is already defined at the point of the type's definition.

After breaking cycles, it should be sufficient to reorder types within a rec group as necessary, as a follow up fixup pass.

I bring this up because we don't want to, for example, artificially disallow a type subtyping another type defined earlier in its rec group. (We should have a test that defines a rec group of two types, where the first is the supertype of the second, and then calls fixup and make sure that the subtyping is preserved.)

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen submitted PR review:

Thanks! Feedback inline below.

Wasmtime GitHub notifications bot (Feb 12 2026 at 22:13):

fitzgen created PR review comment:

And we should probably make generic and reuse the DFS code from my last comment to do this topo sorting as well (although rec groups form a DAG, not a tree, but I think the code should work just fine for this case, perhaps with some minimal tweaks, as well).

Wasmtime GitHub notifications bot (Feb 13 2026 at 21:13):

fitzgen commented on PR #12577:

@khagankhan I just put a PR to make Wasmtime's existing SCC computation and DFS traversal stuff reusable, and I think this PR can be rebased on top of it: https://github.com/bytecodealliance/wasmtime/pull/12590

Last updated: Feb 24 2026 at 04:36 UTC