Repository: bytecodealliance/wasmtime
Pull request #8608 (2024-05-13 19:25:28)

Change `MemoryStyle::Static` to store bytes, not pages
This commit is inspired by me looking at some configuration in the pooling allocator and noticing that configuration of wasm pages vs bytes of linear memory is somewhat inconsistent in `Config`. In the end I'd like to remove or update the `memory_pages` configuration in the pooling allocator to being bytes of linear memory instead to be more consistent with `Config` (and additionally anticipate the custom-page-sizes wasm proposal where terms-of-pages will become ambiguous). The first step in this change is to update one of the lowest layered usages of pages, the `MemoryStyle::Static` configuration.

Note that this is not a trivial conversion because the purpose of carrying around pages instead of bytes is that bytes may overflow where overflow-with-pages typically happens during validation. This means that extra care is taken to handle errors related to overflow to ensure that everything is still reported at the same time.

<!--
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
-->



Patch:
diff --git a/crates/cranelift/src/func_environ.rs b/crates/cranelift/src/func_environ.rs
index c24e274a1..b8319cbfe 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> {
@@ -2132,12 +2137,14 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
                     )
                 }
                 MemoryPlan {
-                    style: MemoryStyle::Static { bound: bound_pages },
+                    style:
+                        MemoryStyle::Static {
+                            byte_reservation: bound_bytes,
+                        },
                     offset_guard_size,
                     pre_guard_size: _,
                     memory: _,
                 } => {
-                    let bound_bytes = u64::from(bound_pages) * u64::from(WASM_PAGE_SIZE);
                     let (base_fact, data_mt) = if let Some(ptr_memtype) = ptr_memtype {
                         // Create a memtype representing the untyped memory region.
                         let data_mt = func.create_memory_type(ir::MemoryTypeData::Memory {
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/environ/src/lib.rs b/crates/environ/src/lib.rs
index 6a7a36f93..ab5e2e339 100644
--- a/crates/environ/src/lib.rs
+++ b/crates/environ/src/lib.rs
@@ -147,15 +147,5 @@ pub mod fact;
 pub use cranelift_entity::*;
 pub use wasmtime_types::*;
 
-/// WebAssembly page sizes are defined to be 64KiB.
-pub const WASM_PAGE_SIZE: u32 = 0x10000;
-
-/// The number of pages (for 32-bit modules) we can have before we run out of
-/// byte index space.
-pub const WASM32_MAX_PAGES: u64 = 1 << 16;
-/// The number of pages (for 64-bit modules) we can have before we run out of
-/// byte index space.
-pub const WASM64_MAX_PAGES: u64 = 1 << 48;
-
 /// Version number of this crate.
 pub const VERSION: &str = env!("CARGO_PKG_VERSION");
diff --git a/crates/environ/src/module.rs b/crates/environ/src/module.rs
index 36868e23a..9e25280ef 100644
--- a/crates/environ/src/module.rs
+++ b/crates/environ/src/module.rs
@@ -18,39 +18,44 @@ pub enum MemoryStyle {
     },
     /// Address space is allocated up front.
     Static {
-        /// The number of mapped and unmapped pages.
-        bound: u64,
+        /// The number of bytes which are reserved for this linear memory. Only
+        /// the lower bytes which represent the actual linear memory need be
+        /// mapped, but other bytes must be guaranteed to be unmapped.
+        byte_reservation: u64,
     },
 }
 
 impl MemoryStyle {
     /// Decide on an implementation style for the given `Memory`.
     pub fn for_memory(memory: Memory, tunables: &Tunables) -> (Self, u64) {
-        // A heap with a maximum that doesn't exceed the static memory bound specified by the
-        // tunables make it static.
-        //
-        // If the module doesn't declare an explicit maximum treat it as 4GiB when not
-        // requested to use the static memory bound itself as the maximum.
-        let absolute_max_pages = if memory.memory64 {
-            crate::WASM64_MAX_PAGES
-        } else {
-            crate::WASM32_MAX_PAGES
+        let static_memory_bound = tunables
+            .static_memory_bound
+            .checked_mul(u64::from(WASM_PAGE_SIZE))
+            .unwrap();
+
+        let is_static = match memory.maximum_byte_size() {
+            Ok(mut maximum) => {
+                if tunables.static_memory_bound_is_maximum {
+                    maximum = maximum.min(static_memory_bound);
+                }
+
+                // Ensure the minimum is less than the maximum; the minimum might exceed the maximum
+                // when the memory is artificially bounded via `static_memory_bound_is_maximum` above
+                memory.minimum_byte_size().unwrap() <= maximum && maximum <= static_memory_bound
+            }
+
+            // If the maximum size of this memory is not representable with
+            // `u64` then use the `static_memory_bound_is_maximum` to indicate
+            // whether it's a static memory or not. It should be ok to discard
+            // the linear memory's maximum size here as growth to the maximum is
+            // always fallible and never guaranteed.
+            Err(_) => tunables.static_memory_bound_is_maximum,
         };
-        let maximum = core::cmp::min(
-            memory.maximum.unwrap_or(absolute_max_pages),
-            if tunables.static_memory_bound_is_maximum {
-                core::cmp::min(tunables.static_memory_bound, absolute_max_pages)
-            } else {
-                absolute_max_pages
-            },
-        );
 
-        // Ensure the minimum is less than the maximum; the minimum might exceed the maximum
-        // when the memory is artificially bounded via `static_memory_bound_is_maximum` above
-        if memory.minimum <= maximum && maximum <= tunables.static_memory_bound {
+        if is_static {
             return (
                 Self::Static {
-                    bound: tunables.static_memory_bound,
+                    byte_reservation: static_memory_bound,
                 },
                 tunables.static_memory_offset_guard_size,
             );
diff --git a/crates/types/src/lib.rs b/crates/types/src/lib.rs
index 1d9de647a..91de8d239 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)
     }
 }
@@ -1463,6 +1489,87 @@ pub struct Memory {
     pub memory64: bool,
 }
 
+/// WebAssembly page sizes are defined to be 64KiB.
+pub const WASM_PAGE_SIZE: u32 = 0x10000;
+
+/// Maximum size, in bytes, of 32-bit memories (4G)
+pub const WASM32_MAX_SIZE: u64 = 1 << 32;
+
+/// Maximum size, in bytes, of 64-bit memories.
+///
+/// Note that the true maximum size of a 64-bit linear memory, in bytes, cannot
+/// be represented in a `u64`. That would require a u65 to store `1<<64`.
+/// Despite that no system can actually allocate a full 64-bit linear memory so
+/// this is instead emulated as "what if the kernel fit in a single wasm page
+/// of linear memory". Shouldn't ever actually be possible but it provides a
+/// number to serve as an effective maximum.
+pub const WASM64_MAX_SIZE: u64 = 0u64.wrapping_sub(0x10000);
+
+impl Memory {
+    /// Returns the minimum size, in bytes, that this memory must be.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the calculation of the minimum size overflows the
+    /// `u64` return type. This means that the memory can't be allocated but
+    /// it's deferred to the caller to how to deal with that.
+    pub fn minimum_byte_size(&self) -> Result<u64, SizeOverflow> {
+        self.minimum
+            .checked_mul(u64::from(WASM_PAGE_SIZE))
+            .ok_or(SizeOverflow)
+    }
+
+    /// Returns the maximum size, in bytes, that this memory is allowed to be.
+    ///
+    /// Note that the return value here is not an `Option` despite the maximum
+    /// size of a linear memory being optional in wasm. If a maximum size
+    /// is not present in the memory's type then a maximum size is selected for
+    /// it. For example the maximum size of a 32-bit memory is `1<<32`. The
+    /// maximum size of a 64-bit linear memory is chosen to be a value that
+    /// won't ever be allowed at runtime.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the calculation of the maximum size overflows the
+    /// `u64` return type. This means that the memory can't be allocated but
+    /// it's deferred to the caller to how to deal with that.
+    pub fn maximum_byte_size(&self) -> Result<u64, SizeOverflow> {
+        match self.maximum {
+            Some(max) => max
+                .checked_mul(u64::from(WASM_PAGE_SIZE))
+                .ok_or(SizeOverflow),
+            None => {
+                let min = self.minimum_byte_size()?;
+                Ok(min.max(self.max_size_based_on_index_type()))
+            }
+        }
+    }
+
+    /// Returns the maximum size memory is allowed to be only based on the
+    /// index type used by this memory.
+    ///
+    /// For example 32-bit linear memories return `1<<32` from this method.
+    pub fn max_size_based_on_index_type(&self) -> u64 {
+        if self.memory64 {
+            WASM64_MAX_SIZE
+        } else {
+            WASM32_MAX_SIZE
+        }
+    }
+}
+
+#[derive(Copy, Clone, Debug)]
+pub struct SizeOverflow;
+
+impl fmt::Display for SizeOverflow {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str("size overflow calculating memory size")
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for SizeOverflow {}
+
 impl From<wasmparser::MemoryType> for Memory {
     fn from(ty: wasmparser::MemoryType) -> Memory {
         Memory {
@@ -1513,27 +1620,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 +1730,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/trampoline/memory.rs b/crates/wasmtime/src/runtime/trampoline/memory.rs
index 9afffeec1..981f769dd 100644
--- a/crates/wasmtime/src/runtime/trampoline/memory.rs
+++ b/crates/wasmtime/src/runtime/trampoline/memory.rs
@@ -15,7 +15,7 @@ use anyhow::{anyhow, Result};
 use core::ops::Range;
 use wasmtime_environ::{
     DefinedMemoryIndex, DefinedTableIndex, EntityIndex, HostPtr, MemoryPlan, MemoryStyle, Module,
-    VMOffsets, WASM_PAGE_SIZE,
+    VMOffsets,
 };
 
 #[cfg(feature = "component-model")]
@@ -129,8 +129,8 @@ impl RuntimeMemoryCreator for MemoryCreatorProxy {
     ) -> Result<Box<dyn RuntimeLinearMemory>> {
         let ty = MemoryType::from_wasmtime_memory(&plan.memory);
         let reserved_size_in_bytes = match plan.style {
-            MemoryStyle::Static { bound } => {
-                Some(usize::try_from(bound * (WASM_PAGE_SIZE as u64)).unwrap())
+            MemoryStyle::Static { byte_reservation } => {
+                Some(usize::try_from(byte_reservation).unwrap())
             }
             MemoryStyle::Dynamic { .. } => None,
         };
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/crates/wasmtime/src/runtime/vm/cow.rs b/crates/wasmtime/src/runtime/vm/cow.rs
index c511b64bb..057561c6f 100644
--- a/crates/wasmtime/src/runtime/vm/cow.rs
+++ b/crates/wasmtime/src/runtime/vm/cow.rs
@@ -738,7 +738,9 @@ mod test {
 
     #[test]
     fn instantiate_no_image() {
-        let plan = dummy_memory_plan(MemoryStyle::Static { bound: 4 << 30 });
+        let plan = dummy_memory_plan(MemoryStyle::Static {
+            byte_reservation: 4 << 30,
+        });
         // 4 MiB mmap'd area, not accessible
         let mut mmap = Mmap::accessible_reserved(0, 4 << 20).unwrap();
         // Create a MemoryImageSlot on top of it
@@ -771,7 +773,9 @@ mod test {
 
     #[test]
     fn instantiate_image() {
-        let plan = dummy_memory_plan(MemoryStyle::Static { bound: 4 << 30 });
+        let plan = dummy_memory_plan(MemoryStyle::Static {
+            byte_reservation: 4 << 30,
+        });
         // 4 MiB mmap'd area, not accessible
         let mut mmap = Mmap::accessible_reserved(0, 4 << 20).unwrap();
         // Create a MemoryImageSlot on top of it
@@ -819,7 +823,9 @@ mod test {
     #[test]
     #[cfg(target_os = "linux")]
     fn memset_instead_of_madvise() {
-        let plan = dummy_memory_plan(MemoryStyle::Static { bound: 100 });
+        let plan = dummy_memory_plan(MemoryStyle::Static {
+            byte_reservation: 100 << 16,
+        });
         let mut mmap = Mmap::accessible_reserved(0, 4 << 20).unwrap();
         let mut memfd = MemoryImageSlot::create(mmap.as_mut_ptr() as *mut _, 0, 4 << 20);
         memfd.no_clear_on_drop();
diff --git a/crates/wasmtime/src/runtime/vm/instance/allocator/pooling/memory_pool.rs b/crates/wasmtime/src/runtime/vm/instance/allocator/pooling/memory_pool.rs
index 6615707bb..5e15a536d 100644
--- a/crates/wasmtime/src/runtime/vm/instance/allocator/pooling/memory_pool.rs
+++ b/crates/wasmtime/src/runtime/vm/instance/allocator/pooling/memory_pool.rs
@@ -270,11 +270,13 @@ impl MemoryPool {
             .skip(module.num_imported_memories)
         {
             match plan.style {
-                MemoryStyle::Static { bound } => {
-                    if self.layout.pages_to_next_stripe_slot() < bound {
+                MemoryStyle::Static { byte_reservation } => {
+                    if u64::try_from(self.layout.bytes_to_next_stripe_slot()).unwrap()
+                        < byte_reservation
+                    {
                         bail!(
                             "memory size allocated per-memory is too small to \
-                             satisfy static bound of {bound:#x} pages"
+                             satisfy static bound of {byte_reservation:#x} bytes"
                         );
                     }
                 }
@@ -336,8 +338,11 @@ impl MemoryPool {
             // should be returned as an error through `validate_memory_plans`
             // but double-check here to be sure.
             match memory_plan.style {
-                MemoryStyle::Static { bound } => {
-                    assert!(bound <= self.layout.pages_to_next_stripe_slot());
+                MemoryStyle::Static { byte_reservation } => {
+                    assert!(
+                        byte_reservation
+                            <= u64::try_from(self.layout.bytes_to_next_stripe_slot()).unwrap()
+                    );
                 }
                 MemoryStyle::Dynamic { .. } => {}
             }
@@ -642,13 +647,6 @@ impl SlabLayout {
     fn bytes_to_next_stripe_slot(&self) -> usize {
         self.slot_bytes * self.num_stripes
     }
-
-    /// Same as `bytes_to_next_stripe_slot` but in Wasm pages.
-    fn pages_to_next_stripe_slot(&self) -> u64 {
-        let bytes = self.bytes_to_next_stripe_slot();
-        let pages = bytes / WASM_PAGE_SIZE as usize;
-        u64::try_from(pages).unwrap()
-    }
 }
 
 fn calculate(constraints: &SlabConstraints) -> Result<SlabLayout> {
diff --git a/crates/wasmtime/src/runtime/vm/memory.rs b/crates/wasmtime/src/runtime/vm/memory.rs
index cf84bc120..fcfb774b4 100644
--- a/crates/wasmtime/src/runtime/vm/memory.rs
+++ b/crates/wasmtime/src/runtime/vm/memory.rs
@@ -14,10 +14,9 @@ use anyhow::{bail, format_err, Result};
 use core::ops::Range;
 use core::ptr::NonNull;
 use core::time::Duration;
-use wasmtime_environ::{MemoryPlan, MemoryStyle, Trap, WASM32_MAX_PAGES, WASM64_MAX_PAGES};
+use wasmtime_environ::{MemoryPlan, MemoryStyle, Trap, WASM32_MAX_SIZE, WASM64_MAX_SIZE};
 
 const WASM_PAGE_SIZE: usize = wasmtime_environ::WASM_PAGE_SIZE as usize;
-const WASM_PAGE_SIZE_U64: u64 = wasmtime_environ::WASM_PAGE_SIZE as u64;
 
 /// A memory allocator
 pub trait RuntimeMemoryCreator: Send + Sync {
@@ -219,10 +218,9 @@ impl MmapMemory {
             // Note that the `maximum` is adjusted here to whatever the smaller
             // of the two is, the `maximum` given or the `bound` specified for
             // this memory.
-            MemoryStyle::Static { bound } => {
-                assert!(bound >= plan.memory.minimum);
-                let bound_bytes =
-                    usize::try_from(bound.checked_mul(WASM_PAGE_SIZE_U64).unwrap()).unwrap();
+            MemoryStyle::Static { byte_reservation } => {
+                assert!(byte_reservation >= plan.memory.minimum_byte_size().unwrap());
+                let bound_bytes = usize::try_from(byte_reservation).unwrap();
                 maximum = Some(bound_bytes.min(maximum.unwrap_or(usize::MAX)));
                 (bound_bytes, 0)
             }
@@ -522,12 +520,16 @@ impl Memory {
     ) -> Result<(usize, Option<usize>)> {
         // Sanity-check what should already be true from wasm module validation.
         let absolute_max = if plan.memory.memory64 {
-            WASM64_MAX_PAGES
+            WASM64_MAX_SIZE
         } else {
-            WASM32_MAX_PAGES
+            WASM32_MAX_SIZE
         };
-        assert!(plan.memory.minimum <= absolute_max);
-        assert!(plan.memory.maximum.is_none() || plan.memory.maximum.unwrap() <= absolute_max);
+        if let Ok(size) = plan.memory.minimum_byte_size() {
+            assert!(size <= absolute_max);
+        }
+        if let Ok(max) = plan.memory.maximum_byte_size() {
+            assert!(max <= absolute_max);
+        }
 
         // This is the absolute possible maximum that the module can try to
         // allocate, which is our entire address space minus a wasm page. That
@@ -548,31 +550,21 @@ impl Memory {
         // happening.
         let minimum = plan
             .memory
-            .minimum
-            .checked_mul(WASM_PAGE_SIZE_U64)
+            .minimum_byte_size()
+            .ok()
             .and_then(|m| usize::try_from(m).ok());
 
         // The plan stores the maximum size in units of wasm pages, but we
         // use units of bytes. Unlike for the `minimum` size we silently clamp
-        // the effective maximum size to `absolute_max` above if the maximum is
-        // too large. This should be ok since as a wasm runtime we get to
-        // arbitrarily decide the actual maximum size of memory, regardless of
-        // what's actually listed on the memory itself.
-        let mut maximum = plan.memory.maximum.map(|max| {
-            usize::try_from(max)
-                .ok()
-                .and_then(|m| m.checked_mul(WASM_PAGE_SIZE))
-                .unwrap_or(absolute_max)
-        });
-
-        // If this is a 32-bit memory and no maximum is otherwise listed then we
-        // need to still specify a maximum size of 4GB. If the host platform is
-        // 32-bit then there's no need to limit the maximum this way since no
-        // allocation of 4GB can succeed, but for 64-bit platforms this is
-        // required to limit memories to 4GB.
-        if !plan.memory.memory64 && maximum.is_none() {
-            maximum = usize::try_from(1u64 << 32).ok();
-        }
+        // the effective maximum size to the limits of what we can track. If the
+        // maximum size exceeds `usize` or `u64` then there's no need to further
+        // keep track of it as some sort of runtime limit will kick in long
+        // before we reach the statically declared maximum size.
+        let maximum = plan
+            .memory
+            .maximum_byte_size()
+            .ok()
+            .and_then(|m| usize::try_from(m).ok());
 
         // Inform the store's limiter what's about to happen. This will let the
         // limiter reject anything if necessary, and this also guarantees that
diff --git a/winch/codegen/src/codegen/env.rs b/winch/codegen/src/codegen/env.rs
index a571f2b38..4e8504f65 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> {
@@ -405,12 +413,12 @@ impl<'a, 'data> TypeConverter<'a, 'data> {
 fn heap_style_and_offset_guard_size(plan: &MemoryPlan) -> (HeapStyle, u64) {
     match plan {
         MemoryPlan {
-            style: MemoryStyle::Static { bound },
+            style: MemoryStyle::Static { byte_reservation },
             offset_guard_size,
             ..
         } => (
             HeapStyle::Static {
-                bound: bound * u64::from(WASM_PAGE_SIZE),
+                bound: *byte_reservation,
             },
             *offset_guard_size,
         ),


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/memory_creator.rs b/tests/all/memory_creator.rs
index 5e5dde978..e289ab895 100644
--- a/tests/all/memory_creator.rs
+++ b/tests/all/memory_creator.rs
@@ -1,7 +1,7 @@
 #[cfg(all(not(target_os = "windows"), not(miri)))]
 mod not_for_windows {
     use wasmtime::*;
-    use wasmtime_environ::{WASM32_MAX_PAGES, WASM_PAGE_SIZE};
+    use wasmtime_environ::{WASM32_MAX_SIZE, WASM_PAGE_SIZE};
 
     use rustix::mm::{mmap_anonymous, mprotect, munmap, MapFlags, MprotectFlags, ProtFlags};
 
@@ -114,9 +114,7 @@ mod not_for_windows {
             unsafe {
                 let mem = Box::new(CustomMemory::new(
                     minimum,
-                    maximum.unwrap_or(
-                        usize::try_from(WASM32_MAX_PAGES * u64::from(WASM_PAGE_SIZE)).unwrap(),
-                    ),
+                    maximum.unwrap_or(usize::try_from(WASM32_MAX_SIZE).unwrap()),
                     self.num_total_bytes.clone(),
                 ));
                 *self.num_created_memories.lock().unwrap() += 1;
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(())
+}