Repository: bytecodealliance/wasmtime
Pull request #8595 (2024-05-10 23:13:06)

Wasmtime(gc): Add support for supertypes and finality
This is the final type system change for Wasm GC: the ability to explicitly declare supertypes and finality. A final type may not be a supertype of another type. A concrete heap type matches another concrete heap type if its concrete type is a subtype (potentially transitively) of the other heap type's concrete type.

Next, I'll begin support for allocating GC structs and arrays at runtime.

I've also implemented `O(1)` subtype checking in the types registry:

In a type system with single inheritance, the subtyping relationships between all types form a set of trees. The root of each tree is a type that has no supertype; each node's immediate children are the types that directly subtype that node.

For example, consider these types:

    class Base {}
    class A subtypes Base {}
    class B subtypes Base {}
    class C subtypes A {}
    class D subtypes A {}
    class E subtypes C {}

These types produce the following tree:

               Base
              /    \
             A      B
            / \
           C   D
          /
         E

Note the following properties:

1. If `sub` is a subtype of `sup` (either directly or transitively) then `sup` *must* be on the path from `sub` up to the root of `sub`'s tree.

2. Additionally, `sup` *must* be the `i`th node down from the root in that path, where `i` is the length of the path from `sup` to its tree's root.

Therefore, if we maintain a vector containing the path to the root for each type, then we can simply check if `sup` is at index `supertypes(sup).len()` within `supertypes(sub)`.

<!--
Please make sure you include the following information:

- If this work has been discussed elsewhere, please include a link to that
  conversation. If it was discussed in an issue, just mention "issue #...".

- Explain why this change is needed. If the details are in an issue already,
  this can be brief.

Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.html

Please ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->


github-actions[bot]: #### Subscribe to Label Action

cc @saulecabrera

<details>
This issue or pull request has been labeled: "wasmtime:api", "winch"

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

* saulecabrera: winch

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

[Learn more.](https://github.com/bytecodealliance/subscribe-to-label-action)
</details>
jeffparsons: > Therefore, if we maintain a vector containing the path to the root for each type, then we can simply check if sup is at index supertypes(sup).len() within supertypes(sub).

This means that the storage for the vecs in each tree is, in total, in `O(N log N)`, right? 

I think there's a cheaper `O(N)` storage per tree way to do it, that still offers `O(1)` subtype checking: 

- Store nodes of the tree in a vec where all descendents of a node occur after that node and before any non-descendent node.
- Each node stores the index of its last descendent. If it has none, then the index will be its own index.
- To test whether `sub` is a subtype of `sup`:
    - Look up trees and indexes of both types.
    - If they live in different trees, then there is no subtype relationship. 
    - Otherwise, look up `sup`'s node. If `sup_index < sub_index && sub_index <= sup_last_descendent` then we have a subtype.

There's a good chance I've misunderstood something (e.g. how the trees are updated?), but if there's nothing else special about these trees then maybe this optimisation is applicable! 🙏
fitzgen: @jeffparsons, thanks for digging in here! Always appreciate a second pair of eyes.

> This means that the storage for the vecs in each tree is, in total, in `O(N log N)`, right?

It is indeed a time-space tradeoff, but as-implemented it can actually be even worse than `O(n log n)`: consider a chain where each type is a subtype of its predecessor: `a; b <: a; c <: b; d <: c; ...`. The `i`th type's supertype array will be of length `i - 1`, and this forms the classic "triangle" shape that indicates `O(n * n)` behavior. This particular case could be resolved (although the implementation would be a bit awkward in the presence of type canonicalization across modules) by defining the supertype arrays in sub-to-supertype order and then using a subslice of a subtype's supertype's vector, when one is present, instead of allocating a new vector. Then I think we would be at `O(n log n)`.

However, implementations are allowed to define their own limits on the maximum depth a subtyping chain may have. And for JS embeddings, it is additionally tightened from "some implementation limit" to `63`; for maximum cross-engine compatibility, we've always matched the JS embedding limits.

https://webassembly.github.io/gc/js-api/index.html#limits

Anyways, the point is that this limit provides bounds on the total memory overhead associated with these supertype vectors, preventing worst-case scenarios.

Finally, my understanding is that it is pretty much expected that engines implement subtyping checks with this technique, FWIW. For example, here is SpiderMonkey's docs about doing this same thing: https://searchfox.org/mozilla-central/rev/ee2ad260c25310a9fbf96031de05bbc0e94394cc/js/src/wasm/WasmTypeDef.h#480-541

This is a good reminder to double check that we are actually enforcing the subtyping depth limits in validation, though :-p

> I think there's a cheaper O(N) storage per tree way to do it, that still offers `O(1)` subtype checking:

If I understand correctly, this is storing the entry and exit indices of a depth-first traversal of the tree and then subtype checking checks that (a) we are looking at the same tree and (b) that the subtype's index (doesn't matter if we check entry vs exit index) is within the supertype's range, correct?

This would indeed work very nicely in the context of a single Wasm module and a static set of types.

But, as you alluded to, things get problematic when we consider updates. GC objects can be passed between modules, and a non-final type from module A can be subtyped by another type in module B and then an instance of that subtype can be passed from B to A, and A might want to do subtyping checks on this instance even though it never defined the exact type of that instance. This necessitates canonicalizing types across modules. So, even though from a single Wasm module's perspective the type set is static, from an engine perspective we are constantly dynamically adding and removing types from the same deduplicated, canonicalized types registry as modules are loaded or unloaded (or when the host defines/drops types via the public Wasmtime API). And therefore our type hierarchies and their trees aren't static, and must support having subtrees grafted on and pruned away at any moment. That means we would need to recompute potentially all those depth-first traversal indices on every mutation, an `O(n)` operation for each new type definition, which is already too expensive on its own, but also leads to `O(n * n)` behavior when defining `n` new types.

So I don't think this approach is something we can use in this case, unfortunately.


Patch:
diff --git a/crates/cranelift/src/func_environ.rs b/crates/cranelift/src/func_environ.rs
index c24e274a1..949097362 100644
--- a/crates/cranelift/src/func_environ.rs
+++ b/crates/cranelift/src/func_environ.rs
@@ -1642,6 +1642,11 @@ impl TypeConvert for FuncEnvironment<'_> {
     fn lookup_heap_type(&self, ty: wasmparser::UnpackedIndex) -> WasmHeapType {
         wasmtime_environ::WasmparserTypeConverter::new(self.types, self.module).lookup_heap_type(ty)
     }
+
+    fn lookup_type_index(&self, index: wasmparser::UnpackedIndex) -> EngineOrModuleTypeIndex {
+        wasmtime_environ::WasmparserTypeConverter::new(self.types, self.module)
+            .lookup_type_index(index)
+    }
 }
 
 impl<'module_environment> TargetEnvironment for FuncEnvironment<'module_environment> {
diff --git a/crates/environ/src/compile/module_environ.rs b/crates/environ/src/compile/module_environ.rs
index 274d4a15f..639883b18 100644
--- a/crates/environ/src/compile/module_environ.rs
+++ b/crates/environ/src/compile/module_environ.rs
@@ -965,6 +965,13 @@ impl TypeConvert for ModuleEnvironment<'_, '_> {
     fn lookup_heap_type(&self, index: wasmparser::UnpackedIndex) -> WasmHeapType {
         WasmparserTypeConverter::new(&self.types, &self.result.module).lookup_heap_type(index)
     }
+
+    fn lookup_type_index(
+        &self,
+        index: wasmparser::UnpackedIndex,
+    ) -> wasmtime_types::EngineOrModuleTypeIndex {
+        WasmparserTypeConverter::new(&self.types, &self.result.module).lookup_type_index(index)
+    }
 }
 
 impl ModuleTranslation<'_> {
diff --git a/crates/environ/src/compile/module_types.rs b/crates/environ/src/compile/module_types.rs
index cf66a169d..da8751e2f 100644
--- a/crates/environ/src/compile/module_types.rs
+++ b/crates/environ/src/compile/module_types.rs
@@ -113,7 +113,7 @@ impl ModuleTypesBuilder {
             let ty = &validator_types[id];
             let wasm_ty = WasmparserTypeConverter::new(self, module)
                 .with_rec_group(validator_types, rec_group_id)
-                .convert_sub_type(ty)?;
+                .convert_sub_type(ty);
             self.wasm_sub_type_in_rec_group(id, wasm_ty);
         }
 
@@ -161,6 +161,8 @@ impl ModuleTypesBuilder {
                 // `trampoline_types` so we can reuse it in the future.
                 Cow::Owned(f) => {
                     let idx = self.types.push(WasmSubType {
+                        is_final: true,
+                        supertype: None,
                         composite_type: WasmCompositeType::Func(f.clone()),
                     });
 
@@ -435,4 +437,19 @@ impl TypeConvert for WasmparserTypeConverter<'_> {
             UnpackedIndex::RecGroup(_) => unreachable!(),
         }
     }
+
+    fn lookup_type_index(&self, index: wasmparser::UnpackedIndex) -> EngineOrModuleTypeIndex {
+        match index {
+            UnpackedIndex::Id(id) => {
+                let interned = self.types.wasmparser_to_wasmtime[&id];
+                EngineOrModuleTypeIndex::Module(interned)
+            }
+            UnpackedIndex::Module(module_index) => {
+                let module_index = TypeIndex::from_u32(module_index);
+                let interned = self.module.types[module_index];
+                EngineOrModuleTypeIndex::Module(interned)
+            }
+            UnpackedIndex::RecGroup(_) => unreachable!(),
+        }
+    }
 }
diff --git a/crates/environ/src/component/translate.rs b/crates/environ/src/component/translate.rs
index 0937dc9aa..625b84597 100644
--- a/crates/environ/src/component/translate.rs
+++ b/crates/environ/src/component/translate.rs
@@ -973,6 +973,13 @@ mod pre_inlining {
         fn lookup_heap_type(&self, index: wasmparser::UnpackedIndex) -> WasmHeapType {
             self.types.lookup_heap_type(index)
         }
+
+        fn lookup_type_index(
+            &self,
+            index: wasmparser::UnpackedIndex,
+        ) -> wasmtime_types::EngineOrModuleTypeIndex {
+            self.types.lookup_type_index(index)
+        }
     }
 }
 use pre_inlining::PreInliningComponentTypes;
diff --git a/crates/environ/src/component/types_builder.rs b/crates/environ/src/component/types_builder.rs
index 7d68b6ba2..0b7bb8b8d 100644
--- a/crates/environ/src/component/types_builder.rs
+++ b/crates/environ/src/component/types_builder.rs
@@ -703,6 +703,13 @@ impl TypeConvert for ComponentTypesBuilder {
     fn lookup_heap_type(&self, _index: wasmparser::UnpackedIndex) -> WasmHeapType {
         panic!("heap types are not supported yet")
     }
+
+    fn lookup_type_index(
+        &self,
+        _index: wasmparser::UnpackedIndex,
+    ) -> wasmtime_types::EngineOrModuleTypeIndex {
+        panic!("typed references are not supported yet")
+    }
 }
 
 fn intern<T, U>(map: &mut HashMap<T, U>, list: &mut PrimaryMap<U, T>, item: T) -> U
diff --git a/crates/types/src/lib.rs b/crates/types/src/lib.rs
index 1d9de647a..1ba81a8ae 100644
--- a/crates/types/src/lib.rs
+++ b/crates/types/src/lib.rs
@@ -326,11 +326,26 @@ pub enum EngineOrModuleTypeIndex {
 }
 
 impl From<ModuleInternedTypeIndex> for EngineOrModuleTypeIndex {
+    #[inline]
     fn from(i: ModuleInternedTypeIndex) -> Self {
         Self::Module(i)
     }
 }
 
+impl From<VMSharedTypeIndex> for EngineOrModuleTypeIndex {
+    #[inline]
+    fn from(i: VMSharedTypeIndex) -> Self {
+        Self::Engine(i)
+    }
+}
+
+impl From<RecGroupRelativeTypeIndex> for EngineOrModuleTypeIndex {
+    #[inline]
+    fn from(i: RecGroupRelativeTypeIndex) -> Self {
+        Self::RecGroup(i)
+    }
+}
+
 impl fmt::Display for EngineOrModuleTypeIndex {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
@@ -868,8 +883,13 @@ impl TypeTrace for WasmCompositeType {
 /// A concrete, user-defined (or host-defined) Wasm type.
 #[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
 pub struct WasmSubType {
-    // TODO: is_final, supertype
-    //
+    /// Whether this type is forbidden from being the supertype of any other
+    /// type.
+    pub is_final: bool,
+
+    /// This type's supertype, if any.
+    pub supertype: Option<EngineOrModuleTypeIndex>,
+
     /// The array, function, or struct that is defined.
     pub composite_type: WasmCompositeType,
 }
@@ -926,6 +946,9 @@ impl TypeTrace for WasmSubType {
     where
         F: FnMut(EngineOrModuleTypeIndex) -> Result<(), E>,
     {
+        if let Some(sup) = self.supertype {
+            func(sup)?;
+        }
         self.composite_type.trace(func)
     }
 
@@ -933,6 +956,9 @@ impl TypeTrace for WasmSubType {
     where
         F: FnMut(&mut EngineOrModuleTypeIndex) -> Result<(), E>,
     {
+        if let Some(sup) = self.supertype.as_mut() {
+            func(sup)?;
+        }
         self.composite_type.trace_mut(func)
     }
 }
@@ -1513,27 +1539,24 @@ pub trait TypeConvert {
         })
     }
 
-    fn convert_sub_type(&self, ty: &wasmparser::SubType) -> WasmResult<WasmSubType> {
-        if ty.supertype_idx.is_some() {
-            return Err(wasm_unsupported!("wasm gc: explicit subtyping"));
+    fn convert_sub_type(&self, ty: &wasmparser::SubType) -> WasmSubType {
+        WasmSubType {
+            is_final: ty.is_final,
+            supertype: ty.supertype_idx.map(|i| self.lookup_type_index(i.unpack())),
+            composite_type: self.convert_composite_type(&ty.composite_type),
         }
-        let composite_type = self.convert_composite_type(&ty.composite_type)?;
-        Ok(WasmSubType { composite_type })
     }
 
-    fn convert_composite_type(
-        &self,
-        ty: &wasmparser::CompositeType,
-    ) -> WasmResult<WasmCompositeType> {
+    fn convert_composite_type(&self, ty: &wasmparser::CompositeType) -> WasmCompositeType {
         match ty {
             wasmparser::CompositeType::Func(f) => {
-                Ok(WasmCompositeType::Func(self.convert_func_type(f)))
+                WasmCompositeType::Func(self.convert_func_type(f))
             }
             wasmparser::CompositeType::Array(a) => {
-                Ok(WasmCompositeType::Array(self.convert_array_type(a)))
+                WasmCompositeType::Array(self.convert_array_type(a))
             }
             wasmparser::CompositeType::Struct(s) => {
-                Ok(WasmCompositeType::Struct(self.convert_struct_type(s)))
+                WasmCompositeType::Struct(self.convert_struct_type(s))
             }
         }
     }
@@ -1626,4 +1649,8 @@ pub trait TypeConvert {
     /// Converts the specified type index from a heap type into a canonicalized
     /// heap type.
     fn lookup_heap_type(&self, index: wasmparser::UnpackedIndex) -> WasmHeapType;
+
+    /// Converts the specified type index from a heap type into a canonicalized
+    /// heap type.
+    fn lookup_type_index(&self, index: wasmparser::UnpackedIndex) -> EngineOrModuleTypeIndex;
 }
diff --git a/crates/wasmtime/src/runtime/component/types.rs b/crates/wasmtime/src/runtime/component/types.rs
index d6d2335bc..92fb4dccc 100644
--- a/crates/wasmtime/src/runtime/component/types.rs
+++ b/crates/wasmtime/src/runtime/component/types.rs
@@ -871,10 +871,15 @@ impl ComponentItem {
             TypeDef::ComponentFunc(idx) => Self::ComponentFunc(ComponentFunc::from(*idx, ty)),
             TypeDef::Interface(iface_ty) => Self::Type(Type::from(iface_ty, ty)),
             TypeDef::Module(idx) => Self::Module(Module::from(*idx, ty)),
-            TypeDef::CoreFunc(idx) => Self::CoreFunc(FuncType::from_wasm_func_type(
-                engine,
-                ty.types[*idx].unwrap_func().clone(),
-            )),
+            TypeDef::CoreFunc(idx) => {
+                let subty = &ty.types[*idx];
+                Self::CoreFunc(FuncType::from_wasm_func_type(
+                    engine,
+                    subty.is_final,
+                    subty.supertype,
+                    subty.unwrap_func().clone(),
+                ))
+            }
             TypeDef::Resource(idx) => {
                 let resource_index = ty.types[*idx].ty;
                 let ty = match ty.resources.get(resource_index) {
diff --git a/crates/wasmtime/src/runtime/module.rs b/crates/wasmtime/src/runtime/module.rs
index 3d8f169c5..a361f918b 100644
--- a/crates/wasmtime/src/runtime/module.rs
+++ b/crates/wasmtime/src/runtime/module.rs
@@ -24,7 +24,7 @@ use std::path::Path;
 use wasmparser::{Parser, ValidPayload, Validator};
 use wasmtime_environ::{
     CompiledModuleInfo, DefinedFuncIndex, DefinedMemoryIndex, EntityIndex, HostPtr, ModuleTypes,
-    ObjectKind, VMOffsets, VMSharedTypeIndex,
+    ObjectKind, TypeTrace, VMOffsets, VMSharedTypeIndex,
 };
 mod registry;
 
@@ -687,7 +687,12 @@ impl Module {
         let engine = self.engine();
         module
             .imports()
-            .map(move |(module, field, ty)| ImportType::new(module, field, ty, types, engine))
+            .map(move |(imp_mod, imp_field, mut ty)| {
+                ty.canonicalize_for_runtime_usage(&mut |i| {
+                    self.signatures().shared_type(i).unwrap()
+                });
+                ImportType::new(imp_mod, imp_field, ty, types, engine)
+            })
             .collect::<Vec<_>>()
             .into_iter()
     }
diff --git a/crates/wasmtime/src/runtime/type_registry.rs b/crates/wasmtime/src/runtime/type_registry.rs
index 3d196520f..47c8dc262 100644
--- a/crates/wasmtime/src/runtime/type_registry.rs
+++ b/crates/wasmtime/src/runtime/type_registry.rs
@@ -456,6 +456,17 @@ struct TypeRegistryInner {
     // `RecGroupEntry`.
     type_to_rec_group: SecondaryMap<VMSharedTypeIndex, Option<RecGroupEntry>>,
 
+    // A map from a registered type to its complete list of supertypes.
+    //
+    // The supertypes are ordered from super- to subtype, i.e. the immediate
+    // parent supertype is the last element and the least-upper-bound of all
+    // supertypes is the first element.
+    //
+    // Types without any supertypes are omitted from this map. This means that
+    // we never allocate any backing storage for this map when Wasm GC is not in
+    // use.
+    type_to_supertypes: SecondaryMap<VMSharedTypeIndex, Option<Box<[VMSharedTypeIndex]>>>,
+
     // A map from each registered function type to its trampoline type.
     //
     // Note that when a function type is its own trampoline type, then we omit
@@ -634,6 +645,8 @@ impl TypeRegistryInner {
                         // registration, but at most once since trampoline
                         // function types are their own trampoline type.
                         let trampoline_entry = self.register_singleton_rec_group(WasmSubType {
+                            is_final: true,
+                            supertype: None,
                             composite_type: wasmtime_environ::WasmCompositeType::Func(trampoline),
                         });
                         let trampoline_index = trampoline_entry.0.shared_type_indices[0];
@@ -689,15 +702,42 @@ impl TypeRegistryInner {
             "type is not canonicalized for runtime usage: {ty:?}"
         );
 
+        // Add the type to our slab.
         let id = self.types.alloc(Arc::new(ty));
         let engine_index = slab_id_to_shared_type_index(id);
         log::trace!(
             "registered type {module_index:?} as {engine_index:?} = {:?}",
             &self.types[id]
         );
+
+        // Create the supertypes list for this type.
+        if let Some(supertype) = self.types[id].supertype {
+            let supertype = supertype.unwrap_engine_type_index();
+            let supers_supertypes = self.supertypes(supertype);
+            let mut supertypes = Vec::with_capacity(supers_supertypes.len() + 1);
+            supertypes.extend(
+                supers_supertypes
+                    .iter()
+                    .copied()
+                    .chain(iter::once(supertype)),
+            );
+            self.type_to_supertypes[engine_index] = Some(supertypes.into_boxed_slice());
+        }
+
         engine_index
     }
 
+    /// Get the supertypes list for the given type.
+    ///
+    /// The supertypes are listed in super-to-sub order. `ty` itself is not
+    /// included in the list.
+    fn supertypes(&self, ty: VMSharedTypeIndex) -> &[VMSharedTypeIndex] {
+        self.type_to_supertypes
+            .get(ty)
+            .and_then(|s| s.as_deref())
+            .unwrap_or(&[])
+    }
+
     /// Register a rec group consisting of a single type.
     ///
     /// The type must already be canonicalized for runtime usage in this
@@ -800,6 +840,7 @@ impl TypeRegistryInner {
                 let removed_entry = self.type_to_rec_group[ty].take();
                 debug_assert_eq!(removed_entry.unwrap(), entry);
 
+                // Remove the associated trampoline type, if any.
                 if let Some(trampoline_ty) =
                     self.type_to_trampoline.get(ty).and_then(|x| x.expand())
                 {
@@ -812,6 +853,14 @@ impl TypeRegistryInner {
                     }
                 }
 
+                // Remove the type's supertypes list, if any. Take care to guard
+                // this assignment so that we don't accidentally force the
+                // secondary map to allocate even when we never actually use
+                // Wasm GC.
+                if self.type_to_supertypes.get(ty).is_some() {
+                    self.type_to_supertypes[ty] = None;
+                }
+
                 let id = shared_type_index_to_slab_id(ty);
                 self.types.dealloc(id);
             }
@@ -831,6 +880,7 @@ impl Drop for TypeRegistryInner {
             hash_consing_map,
             types,
             type_to_rec_group,
+            type_to_supertypes,
             type_to_trampoline,
             drop_stack,
         } = self;
@@ -846,6 +896,10 @@ impl Drop for TypeRegistryInner {
             type_to_rec_group.is_empty() || type_to_rec_group.values().all(|x| x.is_none()),
             "type registry not empty: type-to-rec-group map is not empty: {type_to_rec_group:#?}"
         );
+        assert!(
+            type_to_supertypes.is_empty() || type_to_supertypes.values().all(|x| x.is_none()),
+            "type registry not empty: type-to-supertypes map is not empty: {type_to_supertypes:#?}"
+        );
         assert!(
             type_to_trampoline.is_empty() || type_to_trampoline.values().all(|x| x.is_none()),
             "type registry not empty: type-to-trampoline map is not empty: {type_to_trampoline:#?}"
@@ -907,4 +961,55 @@ impl TypeRegistry {
         log::trace!("TypeRegistry::trampoline_type({index:?}) -> {trampoline_ty:?}");
         trampoline_ty
     }
+
+    /// Is type `sub` a subtype of `sup`?
+    pub fn is_subtype(&self, sub: VMSharedTypeIndex, sup: VMSharedTypeIndex) -> bool {
+        if sub == sup {
+            return true;
+        }
+
+        // Do the O(1) subtype checking trick:
+        //
+        // In a type system with single inheritance, the subtyping relationships
+        // between all types form a set of trees. The root of each tree is a
+        // type that has no supertype; each node's immediate children are the
+        // types that directly subtype that node.
+        //
+        // For example, consider these types:
+        //
+        //     class Base {}
+        //     class A subtypes Base {}
+        //     class B subtypes Base {}
+        //     class C subtypes A {}
+        //     class D subtypes A {}
+        //     class E subtypes C {}
+        //
+        // These types produce the following tree:
+        //
+        //                Base
+        //               /    \
+        //              A      B
+        //             / \
+        //            C   D
+        //           /
+        //          E
+        //
+        // Note the following properties:
+        //
+        // 1. If `sub` is a subtype of `sup` (either directly or transitively)
+        //    then `sup` *must* be on the path from `sub` up to the root of
+        //    `sub`'s tree.
+        //
+        // 2. Additionally, `sup` *must* be the `i`th node down from the root in
+        //    that path, where `i` is the length of the path from `sup` to its
+        //    tree's root.
+        //
+        // Therefore, if we have the path to the root for each type (we do) then
+        // we can simply check if `sup` is at index `supertypes(sup).len()`
+        // within `supertypes(sub)`.
+        let inner = self.0.read();
+        let sub_supertypes = inner.supertypes(sub);
+        let sup_supertypes = inner.supertypes(sup);
+        sub_supertypes.get(sup_supertypes.len()) == Some(&sup)
+    }
 }
diff --git a/crates/wasmtime/src/runtime/types.rs b/crates/wasmtime/src/runtime/types.rs
index eb62df488..f890d0ece 100644
--- a/crates/wasmtime/src/runtime/types.rs
+++ b/crates/wasmtime/src/runtime/types.rs
@@ -1,6 +1,6 @@
 use crate::prelude::*;
 use anyhow::{bail, ensure, Result};
-use core::fmt::{self, Display};
+use core::fmt::{self, Display, Write};
 use wasmtime_environ::{
     EngineOrModuleTypeIndex, EntityType, Global, Memory, ModuleTypes, Table, TypeTrace,
     VMSharedTypeIndex, WasmArrayType, WasmCompositeType, WasmFieldType, WasmFuncType, WasmHeapType,
@@ -15,15 +15,57 @@ pub(crate) mod matching;
 
 // Type attributes
 
-/// Indicator of whether a global is mutable or not
+/// Indicator of whether a global value, struct's field, or array type's
+/// elements are mutable or not.
 #[derive(Debug, Clone, Copy, Hash, Eq, PartialEq)]
 pub enum Mutability {
-    /// The global is constant and its value does not change
+    /// The global value, struct field, or array elements are constant and the
+    /// value does not change.
     Const,
-    /// The value of the global can change over time
+    /// The value of the global, struct field, or array elements can change over
+    /// time.
     Var,
 }
 
+impl Mutability {
+    /// Is this constant?
+    #[inline]
+    pub fn is_const(&self) -> bool {
+        *self == Self::Const
+    }
+
+    /// Is this variable?
+    #[inline]
+    pub fn is_var(&self) -> bool {
+        *self == Self::Var
+    }
+}
+
+/// Indicator of whether a type is final or not.
+///
+/// Final types may not be the supertype of other types.
+#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq)]
+pub enum Finality {
+    /// The associated type is final.
+    Final,
+    /// The associated type is not final.
+    NonFinal,
+}
+
+impl Finality {
+    /// Is this final?
+    #[inline]
+    pub fn is_final(&self) -> bool {
+        *self == Self::Final
+    }
+
+    /// Is this non-final?
+    #[inline]
+    pub fn is_non_final(&self) -> bool {
+        *self == Self::NonFinal
+    }
+}
+
 // Value Types
 
 /// A list of all possible value types in WebAssembly.
@@ -478,35 +520,8 @@ impl RefType {
 /// ```
 ///
 /// Additionally, some concrete function types are sub- or supertypes of other
-/// concrete function types. For simplicity, this isn't depicted in the diagram
-/// above. Specifically, this is based on their parameter and result types, and
-/// whether those types are in a subtyping relationship:
-///
-/// * Parameters are contravariant: `(func (param $a) (result $c))` is a subtype
-///   of `(func (param $b) (result $c))` when `$b` is a subtype of `$a`.
-///
-///   For example, we can substitute `(func (param $cat))` with `(func (param
-///   $animal))` because `$cat` is a subtype of `$animal` and so the new
-///   function is still prepared to accept all `$cat` arguments that any caller
-///   might pass in.
-///
-///   We can't do the opposite and replace `(func (param $animal))` with `(func
-///   (param $cat))`. What would the new function do when given a `$dog`? It is
-///   invalid.
-///
-/// * Results are covariant: `(func (result $a))` is a subtype of `(func (result
-///   $b))` when `$a` is a subtype of `$b`.
-///
-///   For example, we can substitute a `(func (result $animal))` with a
-///   `(func (result $cat))` because callers expect to be returned an
-///   `$animal` and all `$cat`s are `$animal`s.
-///
-///   We cannot do the opposite and substitute a `(func (result $cat))` with a
-///   `(func (result $animal))`, since callers expect a `$cat` but the new
-///   function could return a `$dog`.
-///
-/// As always, Wikipedia is also helpful:
-/// https:///en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)
+/// concrete function types, if that was declared in their definition. For
+/// simplicity, this isn't depicted in the diagram above.
 ///
 /// ## External
 ///
@@ -557,16 +572,9 @@ impl RefType {
 /// ```
 ///
 /// Additionally, concrete struct and array types can be subtypes of other
-/// concrete struct and array types respectively. Once again, this is omitted
-/// from the above diagram for simplicity. Specifically:
-///
-/// * Array types are covariant with their element type: `(array $a)` is a
-///   subtype of `(array $b)` if `$a` is a subtype of `$b`. For example, `(array
-///   $cat)` is a subtype of `(array $animal)`.
-///
-/// * Struct types are covariant with their field types, and subtypes may
-///   additionally have appended fields that do not appear in the supertype. For
-///   example, `(struct $cat $dog)` is a subtype of `(struct $animal)`.
+/// concrete struct and array types respectively, if that was declared in their
+/// definitions. Once again, this is omitted from the above diagram for
+/// simplicity.
 ///
 /// # Subtyping and Equality
 ///
@@ -695,6 +703,13 @@ impl From<ArrayType> for HeapType {
     }
 }
 
+impl From<StructType> for HeapType {
+    #[inline]
+    fn from(s: StructType) -> Self {
+        HeapType::ConcreteStruct(s)
+    }
+}
+
 impl HeapType {
     /// Is this the abstract `extern` heap type?
     pub fn is_extern(&self) -> bool {
@@ -867,7 +882,12 @@ impl HeapType {
             (HeapType::NoFunc, _) => false,
 
             (HeapType::ConcreteFunc(_), HeapType::Func) => true,
-            (HeapType::ConcreteFunc(a), HeapType::ConcreteFunc(b)) => a.matches(b),
+            (HeapType::ConcreteFunc(a), HeapType::ConcreteFunc(b)) => {
+                assert!(a.comes_from_same_engine(b.engine()));
+                a.engine()
+                    .signatures()
+                    .is_subtype(a.type_index(), b.type_index())
+            }
             (HeapType::ConcreteFunc(_), _) => false,
 
             (HeapType::Func, HeapType::Func) => true,
@@ -887,14 +907,24 @@ impl HeapType {
             (HeapType::None, _) => false,
 
             (HeapType::ConcreteArray(_), HeapType::Array | HeapType::Eq | HeapType::Any) => true,
-            (HeapType::ConcreteArray(a), HeapType::ConcreteArray(b)) => a.matches(b),
+            (HeapType::ConcreteArray(a), HeapType::ConcreteArray(b)) => {
+                assert!(a.comes_from_same_engine(b.engine()));
+                a.engine()
+                    .signatures()
+                    .is_subtype(a.type_index(), b.type_index())
+            }
             (HeapType::ConcreteArray(_), _) => false,
 
             (HeapType::Array, HeapType::Array | HeapType::Eq | HeapType::Any) => true,
             (HeapType::Array, _) => false,
 
             (HeapType::ConcreteStruct(_), HeapType::Struct | HeapType::Eq | HeapType::Any) => true,
-            (HeapType::ConcreteStruct(a), HeapType::ConcreteStruct(b)) => a.matches(b),
+            (HeapType::ConcreteStruct(a), HeapType::ConcreteStruct(b)) => {
+                assert!(a.comes_from_same_engine(b.engine()));
+                a.engine()
+                    .signatures()
+                    .is_subtype(a.type_index(), b.type_index())
+            }
             (HeapType::ConcreteStruct(_), _) => false,
 
             (HeapType::Struct, HeapType::Struct | HeapType::Eq | HeapType::Any) => true,
@@ -1112,7 +1142,14 @@ impl ExternType {
                     FuncType::from_shared_type_index(engine, *e).into()
                 }
                 EngineOrModuleTypeIndex::Module(m) => {
-                    FuncType::from_wasm_func_type(engine, types[*m].unwrap_func().clone()).into()
+                    let subty = &types[*m];
+                    FuncType::from_wasm_func_type(
+                        engine,
+                        subty.is_final,
+                        subty.supertype,
+                        subty.unwrap_func().clone(),
+                    )
+                    .into()
                 }
                 EngineOrModuleTypeIndex::RecGroup(_) => unreachable!(),
             },
@@ -1237,6 +1274,13 @@ impl StorageType {
         a.matches(b) && b.matches(a)
     }
 
+    pub(crate) fn comes_from_same_engine(&self, engine: &Engine) -> bool {
+        match self {
+            StorageType::I8 | StorageType::I16 => true,
+            StorageType::ValType(v) => v.comes_from_same_engine(engine),
+        }
+    }
+
     pub(crate) fn from_wasm_storage_type(engine: &Engine, ty: &WasmStorageType) -> Self {
         match ty {
             WasmStorageType::I8 => Self::I8,
@@ -1312,6 +1356,10 @@ impl FieldType {
         a.matches(b) && b.matches(a)
     }
 
+    pub(crate) fn comes_from_same_engine(&self, engine: &Engine) -> bool {
+        self.element_type.comes_from_same_engine(engine)
+    }
+
     pub(crate) fn from_wasm_field_type(engine: &Engine, ty: &WasmFieldType) -> Self {
         Self {
             mutability: if ty.mutable {
@@ -1347,16 +1395,17 @@ impl FieldType {
 /// however, you are in that 0.01% scenario where you need to check precise
 /// equality between types, you can use the [`StructType::eq`] method.
 //
-// TODO: Once we have array values, update above docs with a reference to the
-// future `Array::matches_ty` method
+// TODO: Once we have struct values, update above docs with a reference to the
+// future `Struct::matches_ty` method
 #[derive(Debug, Clone, Hash)]
 pub struct StructType {
     registered_type: RegisteredType,
 }
 
 impl StructType {
-    /// Construct a new `StructType` with the given field type's mutability and
-    /// storage type.
+    /// Construct a new `StructType` with the given field types.
+    ///
+    /// This `StructType` will be final and without a supertype.
     ///
     /// The result will be associated with the given engine, and attempts to use
     /// it with other engines will panic (for example, checking whether it is a
@@ -1365,24 +1414,84 @@ impl StructType {
     ///
     /// Returns an error if the number of fields exceeds the implementation
     /// limit.
+    ///
+    /// # Panics
+    ///
+    /// Panics if any given field type is not associated with the given engine.
     pub fn new(engine: &Engine, fields: impl IntoIterator<Item = FieldType>) -> Result<Self> {
+        Self::with_finality_and_supertype(engine, Finality::Final, None, fields)
+    }
+
+    /// Construct a new `StructType` with the given finality, supertype, and
+    /// fields.
+    ///
+    /// The result will be associated with the given engine, and attempts to use
+    /// it with other engines will panic (for example, checking whether it is a
+    /// subtype of another struct type that is associated with a different
+    /// engine).
+    ///
+    /// Returns an error if the number of fields exceeds the implementation
+    /// limit, if the supertype is final, or if this type does not match the
+    /// supertype.
+    ///
+    /// # Panics
+    ///
+    /// Panics if any given field type is not associated with the given engine.
+    pub fn with_finality_and_supertype(
+        engine: &Engine,
+        finality: Finality,
+        supertype: Option<&Self>,
+        fields: impl IntoIterator<Item = FieldType>,
+    ) -> Result<Self> {
+        let fields = fields.into_iter();
+
+        let mut wasmtime_fields = Vec::with_capacity({
+            let size_hint = fields.size_hint();
+            let cap = size_hint.1.unwrap_or(size_hint.0);
+            // Only reserve space if we have a supertype, as that is the only time
+            // that this vec is used.
+            supertype.is_some() as usize * cap
+        });
+
         // Same as in `FuncType::new`: we must prevent any `RegisteredType`s
         // from being reclaimed while constructing this struct type.
         let mut registrations = smallvec::SmallVec::<[_; 4]>::new();
 
         let fields = fields
-            .into_iter()
             .map(|ty: FieldType| {
+                assert!(ty.comes_from_same_engine(engine));
+
+                if supertype.is_some() {
+                    wasmtime_fields.push(ty.clone());
+                }
+
                 if let Some(r) = ty.element_type.as_val_type().and_then(|v| v.as_ref()) {
                     if let Some(r) = r.heap_type().as_registered_type() {
                         registrations.push(r.clone());
                     }
                 }
+
                 ty.to_wasm_field_type()
             })
             .collect();
 
-        Self::from_wasm_struct_type(engine, WasmStructType { fields })
+        if let Some(supertype) = supertype {
+            ensure!(
+                supertype.finality().is_non_final(),
+                "cannot create a subtype of a final supertype"
+            );
+            ensure!(
+                Self::fields_match(wasmtime_fields.into_iter(), supertype.fields()),
+                "struct fields must match their supertype's fields"
+            );
+        }
+
+        Self::from_wasm_struct_type(
+            engine,
+            finality.is_final(),
+            supertype.map(|ty| ty.type_index().into()),
+            WasmStructType { fields },
+        )
     }
 
     /// Get the engine that this struct type is associated with.
@@ -1390,6 +1499,21 @@ impl StructType {
         self.registered_type.engine()
     }
 
+    /// Get the finality of this struct type.
+    pub fn finality(&self) -> Finality {
+        match self.registered_type.is_final {
+            true => Finality::Final,
+            false => Finality::NonFinal,
+        }
+    }
+
+    /// Get the supertype of this struct type, if any.
+    pub fn supertype(&self) -> Option<Self> {
+        self.registered_type
+            .supertype
+            .map(|ty| Self::from_shared_type_index(self.engine(), ty.unwrap_engine_type_index()))
+    }
+
     /// Get the `i`th field type.
     ///
     /// Returns `None` if `i` is out of bounds.
@@ -1428,11 +1552,14 @@ impl StructType {
             return true;
         }
 
-        self.fields().len() >= other.fields().len()
-            && self
-                .fields()
-                .zip(other.fields())
-                .all(|(a, b)| a.matches(&b))
+        Self::fields_match(self.fields(), other.fields())
+    }
+
+    fn fields_match(
+        a: impl ExactSizeIterator<Item = FieldType>,
+        b: impl ExactSizeIterator<Item = FieldType>,
+    ) -> bool {
+        a.len() >= b.len() && a.zip(b).all(|(a, b)| a.matches(&b))
     }
 
     /// Is struct type `a` precisely equal to struct type `b`?
@@ -1471,7 +1598,12 @@ impl StructType {
     /// within a Wasm module's `ModuleTypes` since the Wasm module itself is
     /// holding a strong reference to all of its types, including any `(ref null
     /// <index>)` types used as the element type for this struct type.
-    pub(crate) fn from_wasm_struct_type(engine: &Engine, ty: WasmStructType) -> Result<StructType> {
+    pub(crate) fn from_wasm_struct_type(
+        engine: &Engine,
+        is_final: bool,
+        supertype: Option<EngineOrModuleTypeIndex>,
+        ty: WasmStructType,
+    ) -> Result<StructType> {
         const MAX_FIELDS: usize = 10_000;
         let fields_len = ty.fields.len();
         ensure!(
@@ -1484,10 +1616,8 @@ impl StructType {
         let ty = RegisteredType::new(
             engine,
             WasmSubType {
-                // TODO:
-                //
-                // is_final: true,
-                // supertype: None,
+                is_final,
+                supertype,
                 composite_type: WasmCompositeType::Struct(ty),
             },
         );
@@ -1533,11 +1663,53 @@ impl ArrayType {
     /// Construct a new `ArrayType` with the given field type's mutability and
     /// storage type.
     ///
+    /// The new `ArrayType` will be final and without a supertype.
+    ///
     /// The result will be associated with the given engine, and attempts to use
     /// it with other engines will panic (for example, checking whether it is a
     /// subtype of another array type that is associated with a different
     /// engine).
+    ///
+    /// # Panics
+    ///
+    /// Panics if the given field type is not associated with the given engine.
     pub fn new(engine: &Engine, field_type: FieldType) -> Self {
+        Self::with_finality_and_supertype(engine, Finality::Final, None, field_type)
+            .expect("cannot fail without a supertype")
+    }
+
+    /// Construct a new `StructType` with the given finality, supertype, and
+    /// fields.
+    ///
+    /// The result will be associated with the given engine, and attempts to use
+    /// it with other engines will panic (for example, checking whether it is a
+    /// subtype of another struct type that is associated with a different
+    /// engine).
+    ///
+    /// Returns an error if the supertype is final, or if this type does not
+    /// match the supertype.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the given field type is not associated with the given engine.
+    pub fn with_finality_and_supertype(
+        engine: &Engine,
+        finality: Finality,
+        supertype: Option<&Self>,
+        field_type: FieldType,
+    ) -> Result<Self> {
+        if let Some(supertype) = supertype {
+            assert!(supertype.comes_from_same_engine(engine));
+            ensure!(
+                supertype.finality().is_non_final(),
+                "cannot create a subtype of a final supertype"
+            );
+            ensure!(
+                field_type.matches(&supertype.field_type()),
+                "array field type must match its supertype's field type"
+            );
+        }
+
         // Same as in `FuncType::new`: we must prevent any `RegisteredType` in
         // `field_type` from being reclaimed while constructing this array type.
         let _registration = field_type
@@ -1546,8 +1718,15 @@ impl ArrayType {
             .and_then(|v| v.as_ref())
             .and_then(|r| r.heap_type().as_registered_type());
 
+        assert!(field_type.comes_from_same_engine(engine));
         let wasm_ty = WasmArrayType(field_type.to_wasm_field_type());
-        Self::from_wasm_array_type(engine, wasm_ty)
+
+        Ok(Self::from_wasm_array_type(
+            engine,
+            finality.is_final(),
+            supertype.map(|ty| ty.type_index().into()),
+            wasm_ty,
+        ))
     }
 
     /// Get the engine that this array type is associated with.
@@ -1555,6 +1734,21 @@ impl ArrayType {
         self.registered_type.engine()
     }
 
+    /// Get the finality of this array type.
+    pub fn finality(&self) -> Finality {
+        match self.registered_type.is_final {
+            true => Finality::Final,
+            false => Finality::NonFinal,
+        }
+    }
+
+    /// Get the supertype of this array type, if any.
+    pub fn supertype(&self) -> Option<Self> {
+        self.registered_type
+            .supertype
+            .map(|ty| Self::from_shared_type_index(self.engine(), ty.unwrap_engine_type_index()))
+    }
+
     /// Get this array's underlying field type.
     ///
     /// The field type contains information about both this array type's
@@ -1643,14 +1837,17 @@ impl ArrayType {
     /// within a Wasm module's `ModuleTypes` since the Wasm module itself is
     /// holding a strong reference to all of its types, including any `(ref null
     /// <index>)` types used as the element type for this array type.
-    pub(crate) fn from_wasm_array_type(engine: &Engine, ty: WasmArrayType) -> ArrayType {
+    pub(crate) fn from_wasm_array_type(
+        engine: &Engine,
+        is_final: bool,
+        supertype: Option<EngineOrModuleTypeIndex>,
+        ty: WasmArrayType,
+    ) -> ArrayType {
         let ty = RegisteredType::new(
             engine,
             WasmSubType {
-                // TODO:
-                //
-                // is_final: true,
-                // supertype: None,
+                is_final,
+                supertype,
                 composite_type: WasmCompositeType::Array(ty),
             },
         );
@@ -1711,15 +1908,61 @@ impl Display for FuncType {
 }
 
 impl FuncType {
-    /// Creates a new function descriptor from the given parameters and results.
+    /// Creates a new function type from the given parameters and results.
     ///
-    /// The function descriptor returned will represent a function which takes
+    /// The function type returned will represent a function which takes
     /// `params` as arguments and returns `results` when it is finished.
+    ///
+    /// The resulting function type will be final and without a supertype.
+    ///
+    /// # Panics
+    ///
+    /// Panics if any parameter or value type is not associated with the given
+    /// engine.
     pub fn new(
         engine: &Engine,
         params: impl IntoIterator<Item = ValType>,
         results: impl IntoIterator<Item = ValType>,
     ) -> FuncType {
+        Self::with_finality_and_supertype(engine, Finality::Final, None, params, results)
+            .expect("cannot fail without a supertype")
+    }
+
+    /// Create a new function type with the given finality, supertype, parameter
+    /// types, and result types.
+    ///
+    /// Returns an error if the supertype is final, or if this function type
+    /// does not match the supertype.
+    ///
+    /// # Panics
+    ///
+    /// Panics if any parameter or value type is not associated with the given
+    /// engine.
+    pub fn with_finality_and_supertype(
+        engine: &Engine,
+        finality: Finality,
+        supertype: Option<&Self>,
+        params: impl IntoIterator<Item = ValType>,
+        results: impl IntoIterator<Item = ValType>,
+    ) -> Result<Self> {
+        let params = params.into_iter();
+        let results = results.into_iter();
+
+        let mut wasmtime_params = Vec::with_capacity({
+            let size_hint = params.size_hint();
+            let cap = size_hint.1.unwrap_or(size_hint.0);
+            // Only reserve space if we have a supertype, as that is the only time
+            // that this vec is used.
+            supertype.is_some() as usize * cap
+        });
+
+        let mut wasmtime_results = Vec::with_capacity({
+            let size_hint = results.size_hint();
+            let cap = size_hint.1.unwrap_or(size_hint.0);
+            // Same as above.
+            supertype.is_some() as usize * cap
+        });
+
         // Keep any of our parameters' and results' `RegisteredType`s alive
         // across `Self::from_wasm_func_type`. If one of our given `ValType`s is
         // the only thing keeping a type in the registry, we don't want to
@@ -1727,22 +1970,75 @@ impl FuncType {
         // before we register our new `WasmFuncType` that will reference it.
         let mut registrations = smallvec::SmallVec::<[_; 4]>::new();
 
-        let mut to_wasm_type = |ty: ValType| {
+        let mut to_wasm_type = |ty: ValType, vec: &mut Vec<_>| {
+            assert!(ty.comes_from_same_engine(engine));
+
+            if supertype.is_some() {
+                vec.push(ty.clone());
+            }
+
             if let Some(r) = ty.as_ref() {
                 if let Some(r) = r.heap_type().as_registered_type() {
                     registrations.push(r.clone());
                 }
             }
+
             ty.to_wasm_type()
         };
 
-        Self::from_wasm_func_type(
+        let wasm_func_ty = WasmFuncType::new(
+            params
+                .map(|p| to_wasm_type(p, &mut wasmtime_params))
+                .collect(),
+            results
+                .map(|r| to_wasm_type(r, &mut wasmtime_results))
+                .collect(),
+        );
+
+        if let Some(supertype) = supertype {
+            assert!(supertype.comes_from_same_engine(engine));
+            ensure!(
+                supertype.finality().is_non_final(),
+                "cannot create a subtype of a final supertype"
+            );
+            ensure!(
+                Self::matches_impl(
+                    wasmtime_params.iter().cloned(),
+                    supertype.params(),
+                    wasmtime_results.iter().cloned(),
+                    supertype.results()
+                ),
+                "function type must match its supertype: found (func{params}{results}), expected \
+                 {supertype}",
+                params = if wasmtime_params.is_empty() {
+                    String::new()
+                } else {
+                    let mut s = format!(" (params");
+                    for p in &wasmtime_params {
+                        write!(&mut s, " {p}").unwrap();
+                    }
+                    s.push(')');
+                    s
+                },
+                results = if wasmtime_results.is_empty() {
+                    String::new()
+                } else {
+                    let mut s = format!(" (results");
+                    for r in &wasmtime_results {
+                        write!(&mut s, " {r}").unwrap();
+                    }
+                    s.push(')');
+                    s
+                },
+            );
+        }
+
+        Ok(Self::from_wasm_func_type(
             engine,
-            WasmFuncType::new(
-                params.into_iter().map(&mut to_wasm_type).collect(),
-                results.into_iter().map(&mut to_wasm_type).collect(),
-            ),
-        )
+            finality.is_final(),
+            supertype.map(|ty| ty.type_index().into()),
+            wasm_func_ty,
+        ))
     }
 
     /// Get the engine that this function type is associated with.
@@ -1750,6 +2046,21 @@ impl FuncType {
         self.registered_type.engine()
     }
 
+    /// Get the finality of this function type.
+    pub fn finality(&self) -> Finality {
+        match self.registered_type.is_final {
+            true => Finality::Final,
+            false => Finality::NonFinal,
+        }
+    }
+
+    /// Get the supertype of this function type, if any.
+    pub fn supertype(&self) -> Option<Self> {
+        self.registered_type
+            .supertype
+            .map(|ty| Self::from_shared_type_index(self.engine(), ty.unwrap_engine_type_index()))
+    }
+
     /// Get the `i`th parameter type.
     ///
     /// Returns `None` if `i` is out of bounds.
@@ -1813,18 +2124,30 @@ impl FuncType {
             return true;
         }
 
-        self.params().len() == other.params().len()
-            && self.results().len() == other.results().len()
+        Self::matches_impl(
+            self.params(),
+            other.params(),
+            self.results(),
+            other.results(),
+        )
+    }
+
+    fn matches_impl(
+        a_params: impl ExactSizeIterator<Item = ValType>,
+        b_params: impl ExactSizeIterator<Item = ValType>,
+        a_results: impl ExactSizeIterator<Item = ValType>,
+        b_results: impl ExactSizeIterator<Item = ValType>,
+    ) -> bool {
+        a_params.len() == b_params.len()
+            && a_results.len() == b_results.len()
             // Params are contravariant and results are covariant. For more
             // details and a refresher on variance, read
             // https://github.com/bytecodealliance/wasm-tools/blob/f1d89a4/crates/wasmparser/src/readers/core/types/matches.rs#L137-L174
-            && self
-                .params()
-                .zip(other.params())
+            && a_params
+                .zip(b_params)
                 .all(|(a, b)| b.matches(&a))
-            && self
-                .results()
-                .zip(other.results())
+            && a_results
+                .zip(b_results)
                 .all(|(a, b)| a.matches(&b))
     }
 
@@ -1868,14 +2191,17 @@ impl FuncType {
     /// within a Wasm module's `ModuleTypes` since the Wasm module itself is
     /// holding a strong reference to all of its types, including any `(ref null
     /// <index>)` types used in the function's parameters and results.
-    pub(crate) fn from_wasm_func_type(engine: &Engine, ty: WasmFuncType) -> FuncType {
+    pub(crate) fn from_wasm_func_type(
+        engine: &Engine,
+        is_final: bool,
+        supertype: Option<EngineOrModuleTypeIndex>,
+        ty: WasmFuncType,
+    ) -> FuncType {
         let ty = RegisteredType::new(
             engine,
             WasmSubType {
-                // TODO:
-                //
-                // is_final: true,
-                // supertype: None,
+                is_final,
+                supertype,
                 composite_type: WasmCompositeType::Func(ty),
             },
         );
@@ -2160,6 +2486,7 @@ impl<'module> ImportType<'module> {
         types: &'module ModuleTypes,
         engine: &'module Engine,
     ) -> ImportType<'module> {
+        assert!(ty.is_canonicalized_for_runtime_usage());
         ImportType {
             module,
             name,
diff --git a/winch/codegen/src/codegen/env.rs b/winch/codegen/src/codegen/env.rs
index a571f2b38..31af5b7cc 100644
--- a/winch/codegen/src/codegen/env.rs
+++ b/winch/codegen/src/codegen/env.rs
@@ -394,6 +394,14 @@ impl TypeConvert for TypeConverter<'_, '_> {
         wasmtime_environ::WasmparserTypeConverter::new(self.types, &self.translation.module)
             .lookup_heap_type(idx)
     }
+
+    fn lookup_type_index(
+        &self,
+        index: wasmparser::UnpackedIndex,
+    ) -> wasmtime_environ::EngineOrModuleTypeIndex {
+        wasmtime_environ::WasmparserTypeConverter::new(self.types, &self.translation.module)
+            .lookup_type_index(index)
+    }
 }
 
 impl<'a, 'data> TypeConverter<'a, 'data> {


Test patch:
diff --git a/tests/all/externals.rs b/tests/all/externals.rs
index d6e5878a8..a8b644199 100644
--- a/tests/all/externals.rs
+++ b/tests/all/externals.rs
@@ -421,34 +421,71 @@ fn dummy_funcs_and_subtypes(
 ) -> (FuncType, Func, FuncType, Func, FuncType, Func) {
     let engine = store.engine().clone();
 
-    let a_ty = FuncType::new(&engine, None, Some(ValType::NULLFUNCREF));
-    let a = Func::new(
+    let c_ty = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        [],
+        [ValType::FUNCREF],
+    )
+    .unwrap();
+    let c = Func::new(
         &mut *store,
-        a_ty.clone(),
+        c_ty.clone(),
         |_caller, _args, _results| unreachable!(),
     );
 
-    let b_ty = FuncType::new(
+    let b_ty = FuncType::with_finality_and_supertype(
         &engine,
-        None,
-        Some(ValType::Ref(RefType::new(
+        Finality::NonFinal,
+        Some(&c_ty),
+        [],
+        [ValType::Ref(RefType::new(
             true,
             HeapType::ConcreteFunc(FuncType::new(&engine, None, None)),
-        ))),
-    );
+        ))],
+    )
+    .unwrap();
     let b = Func::new(
         &mut *store,
         b_ty.clone(),
         |_caller, _args, _results| unreachable!(),
     );
 
-    let c_ty = FuncType::new(&engine, None, Some(ValType::FUNCREF));
-    let c = Func::new(
+    let a_ty = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&b_ty),
+        [],
+        [ValType::NULLFUNCREF],
+    )
+    .unwrap();
+    let a = Func::new(
         &mut *store,
-        c_ty.clone(),
+        a_ty.clone(),
         |_caller, _args, _results| unreachable!(),
     );
 
+    assert!(a_ty.matches(&a_ty));
+    assert!(a_ty.matches(&b_ty));
+    assert!(a_ty.matches(&c_ty));
+    assert!(!b_ty.matches(&a_ty));
+    assert!(b_ty.matches(&b_ty));
+    assert!(b_ty.matches(&c_ty));
+    assert!(!c_ty.matches(&a_ty));
+    assert!(!c_ty.matches(&b_ty));
+    assert!(c_ty.matches(&c_ty));
+
+    assert!(a.matches_ty(&store, &a_ty));
+    assert!(a.matches_ty(&store, &b_ty));
+    assert!(a.matches_ty(&store, &c_ty));
+    assert!(!b.matches_ty(&store, &a_ty));
+    assert!(b.matches_ty(&store, &b_ty));
+    assert!(b.matches_ty(&store, &c_ty));
+    assert!(!c.matches_ty(&store, &a_ty));
+    assert!(!c.matches_ty(&store, &b_ty));
+    assert!(c.matches_ty(&store, &c_ty));
+
     (a_ty, a, b_ty, b, c_ty, c)
 }
 
@@ -683,12 +720,14 @@ fn table_fill_func_subtyping() {
 
 #[test]
 fn table_copy_func_subtyping() {
+    let _ = env_logger::try_init();
+
     let engine = Engine::default();
     let mut store = Store::new(&engine, ());
 
     let (a_ty, a, b_ty, b, c_ty, c) = dummy_funcs_and_subtypes(&mut store);
 
-    for (table_ty, a_expected, b_expected, c_expected) in [
+    for (dst_ty, a_expected, b_expected, c_expected) in [
         // a <: a, b </: a, c </: a
         (a_ty.clone(), true, false, false),
         // a <: b, b <: b, c </: a
@@ -698,7 +737,7 @@ fn table_copy_func_subtyping() {
     ] {
         let dest_table = Table::new(
             &mut store,
-            TableType::new(RefType::new(true, table_ty.clone().into()), 10, None),
+            TableType::new(RefType::new(true, dst_ty.clone().into()), 10, None),
             Ref::Func(None),
         )
         .unwrap();
diff --git a/tests/all/func.rs b/tests/all/func.rs
index fa79d8a0c..f44e8532f 100644
--- a/tests/all/func.rs
+++ b/tests/all/func.rs
@@ -2206,11 +2206,7 @@ fn wasm_to_host_trampolines_and_subtyping() -> Result<()> {
         }),
     ];
 
-    let return_func_ty = FuncType::new(
-        &engine,
-        [],
-        [RefType::new(false, HeapType::ConcreteFunc(func_ty.clone())).into()],
-    );
+    let return_func_ty = module.imports().nth(1).unwrap().ty().unwrap_func().clone();
 
     for make_func in func_ctors {
         let mut store = Store::new(&engine, ());
diff --git a/tests/all/types.rs b/tests/all/types.rs
index f058f14d8..993a5354b 100644
--- a/tests/all/types.rs
+++ b/tests/all/types.rs
@@ -1,5 +1,16 @@
 use wasmtime::*;
 
+fn field(heap_ty: HeapType) -> FieldType {
+    FieldType::new(
+        Mutability::Var,
+        StorageType::ValType(RefType::new(true, heap_ty).into()),
+    )
+}
+
+fn valty(heap_ty: HeapType) -> ValType {
+    ValType::Ref(RefType::new(true, heap_ty))
+}
+
 #[test]
 fn basic_array_types() -> Result<()> {
     let engine = Engine::default();
@@ -70,13 +81,6 @@ fn basic_struct_types() -> Result<()> {
 fn struct_type_matches() -> Result<()> {
     let engine = Engine::default();
 
-    let field = |heap_ty| {
-        FieldType::new(
-            Mutability::Var,
-            StorageType::ValType(RefType::new(true, heap_ty).into()),
-        )
-    };
-
     let super_ty = StructType::new(&engine, [field(HeapType::Func)])?;
 
     // Depth.
@@ -101,3 +105,526 @@ fn struct_type_matches() -> Result<()> {
 
     Ok(())
 }
+
+#[test]
+fn struct_subtyping_fields_must_match() -> Result<()> {
+    let engine = Engine::default();
+    let a = StructType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        [field(HeapType::Any)],
+    )?;
+
+    for (expected, fields) in [
+        // Missing field.
+        (false, vec![]),
+        // Non-matching field.
+        (false, vec![field(HeapType::Extern)]),
+        // Exact match is okay.
+        (true, vec![field(HeapType::Any)]),
+        // Subtype of the field is okay.
+        (true, vec![field(HeapType::Eq)]),
+        // Extra fields are okay.
+        (true, vec![field(HeapType::Any), field(HeapType::Extern)]),
+    ] {
+        let actual =
+            StructType::with_finality_and_supertype(&engine, Finality::NonFinal, Some(&a), fields)
+                .is_ok();
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}
+
+#[test]
+fn struct_subtyping_supertype_and_finality() -> Result<()> {
+    let engine = Engine::default();
+
+    for (expected, finality) in [(true, Finality::NonFinal), (false, Finality::Final)] {
+        let a = StructType::with_finality_and_supertype(&engine, finality, None, [])?;
+        let actual =
+            StructType::with_finality_and_supertype(&engine, Finality::Final, Some(&a), []).is_ok();
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}
+
+#[test]
+fn struct_subtyping() -> Result<()> {
+    let engine = Engine::default();
+
+    // These types produce the following trees:
+    //
+    //                base               g
+    //               /    \             /
+    //              a      b           h
+    //             / \                /
+    //            c   d              i
+    //           /
+    //          e
+    //         /
+    //        f
+    let base = StructType::with_finality_and_supertype(&engine, Finality::NonFinal, None, [])?;
+    let a = StructType::with_finality_and_supertype(&engine, Finality::NonFinal, Some(&base), [])?;
+    let b = StructType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&base),
+        // Have to add a field so that `b` doesn't dedupe to `a`.
+        [field(HeapType::Any)],
+    )?;
+    let c = StructType::with_finality_and_supertype(&engine, Finality::NonFinal, Some(&a), [])?;
+    let d = StructType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&a),
+        // Have to add a field so that `d` doesn't dedupe to `c`.
+        [field(HeapType::Any)],
+    )?;
+    let e = StructType::with_finality_and_supertype(&engine, Finality::NonFinal, Some(&c), [])?;
+    let f = StructType::with_finality_and_supertype(&engine, Finality::NonFinal, Some(&e), [])?;
+    let g = StructType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        // Have to add a field so that `g` doesn't dedupe to `base`.
+        [field(HeapType::Any)],
+    )?;
+    let h = StructType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&g),
+        [field(HeapType::Any)],
+    )?;
+    let i = StructType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&h),
+        [field(HeapType::Any)],
+    )?;
+
+    for (expected, sub_name, sub, sup_name, sup) in [
+        // Identity, at root.
+        (true, "base", &base, "base", &base),
+        // Identity, in middle.
+        (true, "c", &c, "c", &c),
+        // Identity, at leaf.
+        (true, "f", &f, "f", &f),
+        // Direct, at root.
+        (true, "a", &a, "base", &base),
+        // Direct, in middle.
+        (true, "c", &c, "a", &a),
+        // Direct, at leaf.
+        (true, "f", &f, "e", &e),
+        // Transitive, at root.
+        (true, "c", &c, "base", &base),
+        // Transitive, in middle.
+        (true, "e", &e, "a", &a),
+        // Transitive, at leaf.
+        (true, "f", &f, "c", &c),
+        // Unrelated roots.
+        (false, "base", &base, "g", &g),
+        (false, "g", &g, "base", &base),
+        // Unrelated siblings.
+        (false, "a", &a, "b", &b),
+        (false, "b", &b, "a", &a),
+        (false, "c", &c, "d", &d),
+        (false, "d", &d, "c", &c),
+        // Unrelated root and middle.
+        (false, "base", &base, "h", &h),
+        (false, "h", &h, "base", &base),
+        // Unrelated root and leaf.
+        (false, "base", &base, "i", &i),
+        (false, "i", &i, "base", &base),
+        // Unrelated middles.
+        (false, "a", &a, "h", &h),
+        (false, "h", &h, "a", &a),
+        // Unrelated middle and leaf.
+        (false, "a", &a, "i", &i),
+        (false, "i", &i, "a", &a),
+    ] {
+        eprintln!("expect that `{sub_name} <: {sup_name}` is `{expected}`");
+        let sub = HeapType::ConcreteStruct(sub.clone());
+        let sup = HeapType::ConcreteStruct(sup.clone());
+        let actual = sub.matches(&sup);
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}
+
+#[test]
+fn array_subtyping_field_must_match() -> Result<()> {
+    let engine = Engine::default();
+
+    let a = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        field(HeapType::Any),
+    )?;
+
+    for (expected, field) in [
+        // Non-matching field.
+        (false, field(HeapType::Extern)),
+        // Exact match is okay.
+        (true, field(HeapType::Any)),
+        // Subtype of the field is okay.
+        (true, field(HeapType::Eq)),
+    ] {
+        let actual =
+            ArrayType::with_finality_and_supertype(&engine, Finality::NonFinal, Some(&a), field)
+                .is_ok();
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}
+
+#[test]
+fn array_subtyping_supertype_and_finality() -> Result<()> {
+    let engine = Engine::default();
+
+    for (expected, finality) in [(true, Finality::NonFinal), (false, Finality::Final)] {
+        let superty =
+            ArrayType::with_finality_and_supertype(&engine, finality, None, field(HeapType::Any))?;
+        let actual = ArrayType::with_finality_and_supertype(
+            &engine,
+            Finality::Final,
+            Some(&superty),
+            field(HeapType::Any),
+        )
+        .is_ok();
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}
+
+#[test]
+fn array_subtyping() -> Result<()> {
+    let engine = Engine::default();
+
+    // These types produce the following trees:
+    //
+    //                base               g
+    //               /    \             /
+    //              a      b           h
+    //             / \                /
+    //            c   d              i
+    //           /
+    //          e
+    //         /
+    //        f
+    let base = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        field(HeapType::Any),
+    )?;
+    let a = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&base),
+        field(HeapType::Any),
+    )?;
+    let b = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&base),
+        field(HeapType::Eq),
+    )?;
+    let c = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&a),
+        field(HeapType::Any),
+    )?;
+    let d = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&a),
+        field(HeapType::Eq),
+    )?;
+    let e = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&c),
+        field(HeapType::Any),
+    )?;
+    let f = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&e),
+        field(HeapType::Any),
+    )?;
+    let g = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        field(HeapType::Eq),
+    )?;
+    let h = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&g),
+        field(HeapType::Eq),
+    )?;
+    let i = ArrayType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&h),
+        field(HeapType::Eq),
+    )?;
+
+    for (expected, sub_name, sub, sup_name, sup) in [
+        // Identity, at root.
+        (true, "base", &base, "base", &base),
+        // Identity, in middle.
+        (true, "c", &c, "c", &c),
+        // Identity, at leaf.
+        (true, "f", &f, "f", &f),
+        // Direct, at root.
+        (true, "a", &a, "base", &base),
+        // Direct, in middle.
+        (true, "c", &c, "a", &a),
+        // Direct, at leaf.
+        (true, "f", &f, "e", &e),
+        // Transitive, at root.
+        (true, "c", &c, "base", &base),
+        // Transitive, in middle.
+        (true, "e", &e, "a", &a),
+        // Transitive, at leaf.
+        (true, "f", &f, "c", &c),
+        // Unrelated roots.
+        (false, "base", &base, "g", &g),
+        (false, "g", &g, "base", &base),
+        // Unrelated siblings.
+        (false, "a", &a, "b", &b),
+        (false, "b", &b, "a", &a),
+        (false, "c", &c, "d", &d),
+        (false, "d", &d, "c", &c),
+        // Unrelated root and middle.
+        (false, "base", &base, "h", &h),
+        (false, "h", &h, "base", &base),
+        // Unrelated root and leaf.
+        (false, "base", &base, "i", &i),
+        (false, "i", &i, "base", &base),
+        // Unrelated middles.
+        (false, "a", &a, "h", &h),
+        (false, "h", &h, "a", &a),
+        // Unrelated middle and leaf.
+        (false, "a", &a, "i", &i),
+        (false, "i", &i, "a", &a),
+    ] {
+        eprintln!("expect that `{sub_name} <: {sup_name}` is `{expected}`");
+        let sub = HeapType::ConcreteArray(sub.clone());
+        let sup = HeapType::ConcreteArray(sup.clone());
+        let actual = sub.matches(&sup);
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}
+
+#[test]
+fn func_subtyping_field_must_match() -> Result<()> {
+    let engine = Engine::default();
+
+    let superty = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        [valty(HeapType::Struct)],
+        [valty(HeapType::Any)],
+    )?;
+
+    for (expected, param, ret) in [
+        // Non-matching param type.
+        (false, valty(HeapType::Extern), valty(HeapType::Any)),
+        // Non-matching return type.
+        (false, valty(HeapType::Struct), valty(HeapType::Extern)),
+        // Exact match is okay.
+        (true, valty(HeapType::Struct), valty(HeapType::Any)),
+        // Subtype of the return type is okay.
+        (true, valty(HeapType::Struct), valty(HeapType::Eq)),
+        // Supertype of the param type is okay.
+        (true, valty(HeapType::Eq), valty(HeapType::Any)),
+    ] {
+        let actual = FuncType::with_finality_and_supertype(
+            &engine,
+            Finality::NonFinal,
+            Some(&superty),
+            [param],
+            [ret],
+        )
+        .is_ok();
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}
+
+#[test]
+fn func_subtyping_supertype_and_finality() -> Result<()> {
+    let engine = Engine::default();
+
+    for (expected, finality) in [(true, Finality::NonFinal), (false, Finality::Final)] {
+        let superty = FuncType::with_finality_and_supertype(
+            &engine,
+            finality,
+            None,
+            [],
+            [valty(HeapType::Any)],
+        )?;
+        let actual = FuncType::with_finality_and_supertype(
+            &engine,
+            Finality::Final,
+            Some(&superty),
+            [],
+            [valty(HeapType::Any)],
+        )
+        .is_ok();
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}
+
+#[test]
+fn func_subtyping() -> Result<()> {
+    let engine = Engine::default();
+
+    // These types produce the following trees:
+    //
+    //                base               g
+    //               /    \             /
+    //              a      b           h
+    //             / \                /
+    //            c   d              i
+    //           /
+    //          e
+    //         /
+    //        f
+    let base = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        [],
+        [valty(HeapType::Any)],
+    )?;
+    let a = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&base),
+        [],
+        [valty(HeapType::Any)],
+    )?;
+    let b = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&base),
+        [],
+        [valty(HeapType::Eq)],
+    )?;
+    let c = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&a),
+        [],
+        [valty(HeapType::Any)],
+    )?;
+    let d = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&a),
+        [],
+        [valty(HeapType::Eq)],
+    )?;
+    let e = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&c),
+        [],
+        [valty(HeapType::Any)],
+    )?;
+    let f = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&e),
+        [],
+        [valty(HeapType::Any)],
+    )?;
+    let g = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        None,
+        [],
+        [valty(HeapType::Eq)],
+    )?;
+    let h = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&g),
+        [],
+        [valty(HeapType::Eq)],
+    )?;
+    let i = FuncType::with_finality_and_supertype(
+        &engine,
+        Finality::NonFinal,
+        Some(&h),
+        [],
+        [valty(HeapType::Eq)],
+    )?;
+
+    for (expected, sub_name, sub, sup_name, sup) in [
+        // Identity, at root.
+        (true, "base", &base, "base", &base),
+        // Identity, in middle.
+        (true, "c", &c, "c", &c),
+        // Identity, at leaf.
+        (true, "f", &f, "f", &f),
+        // Direct, at root.
+        (true, "a", &a, "base", &base),
+        // Direct, in middle.
+        (true, "c", &c, "a", &a),
+        // Direct, at leaf.
+        (true, "f", &f, "e", &e),
+        // Transitive, at root.
+        (true, "c", &c, "base", &base),
+        // Transitive, in middle.
+        (true, "e", &e, "a", &a),
+        // Transitive, at leaf.
+        (true, "f", &f, "c", &c),
+        // Unrelated roots.
+        (false, "base", &base, "g", &g),
+        (false, "g", &g, "base", &base),
+        // Unrelated siblings.
+        (false, "a", &a, "b", &b),
+        (false, "b", &b, "a", &a),
+        (false, "c", &c, "d", &d),
+        (false, "d", &d, "c", &c),
+        // Unrelated root and middle.
+        (false, "base", &base, "h", &h),
+        (false, "h", &h, "base", &base),
+        // Unrelated root and leaf.
+        (false, "base", &base, "i", &i),
+        (false, "i", &i, "base", &base),
+        // Unrelated middles.
+        (false, "a", &a, "h", &h),
+        (false, "h", &h, "a", &a),
+        // Unrelated middle and leaf.
+        (false, "a", &a, "i", &i),
+        (false, "i", &i, "a", &a),
+    ] {
+        eprintln!("expect that `{sub_name} <: {sup_name}` is `{expected}`");
+        let sub = HeapType::ConcreteFunc(sub.clone());
+        let sup = HeapType::ConcreteFunc(sup.clone());
+        let actual = sub.matches(&sup);
+        assert_eq!(expected, actual);
+    }
+
+    Ok(())
+}