Repository: bytecodealliance/wasmtime (rust)

Issue:
Limit type-based recursion in the component model
Currently the component model has no limit to type-bsaed recursion other than the "width" of a type and the number of types the type section is allowed to have. The fuzzers have subsequently studiously been finding all the issues with that in the implementation of the component model within Wasmtime. Wasmtime has a number of methods right now which recursively process a type which can lead to stack overflow for deeply nested types such as:

* the `Arbitrary for Type` implementation
* The `{Lower,Lift} for Val` implementations
* The compilation of adapter trampolines

In each of these cases it's not 100% clear if there's an easy way to switch stack-based recursion to heap-based recursion. So far switching to heap-based recursion or alternative methods has been the go-to for fixing fuzz-bugs like this (https://github.com/bytecodealliance/wasmtime/pull/4657 https://github.com/bytecodealliance/wasmtime/pull/4658 https://github.com/bytecodealliance/wasmtime/pull/4708 https://github.com/bytecodealliance/wasmtime/pull/4694) but this seems over time like it's starting to be untenable.

To solve all these issues the conclusion that @fitzgen @lukewagner and I reached awhile back was to simply limit recursion of type hierarchies in the component model entirely. This is a big hammer to use but would definitely fix all of the related issues here, in addition to the recent crop of fuzz-bugs which are getting harder and harder to fix via alternative means. This also seems to mirror what the GC proposal for wasm is doing where limits are placed on the type recursion there as well.

One option to implement this would be an error from `wasmparser` during validation but I think for now it may be best represented as an error from Wasmtime itself due to that being where all the fuzz bugs are. If we feel it's necessary this could also be moved to `wasmparser` instead. 

One bit of trickiness here is that we'll need to update `Arbitrary for Type` to have some limited recursion, and I'm not sure how to do that with `#[derive]` without a thread-local based solution. This may be a case where it's better to have a custom method taking `Unstructured` with a `depth` where the `depth` filters out some possible types to generate.

Pull request description:
components: Limit the recursive size of types in Wasmtime
This commit is aimed at fixing #4814 by placing a hard limit on the
maximal recursive depth a type may have in the component model. The
component model theoretically allows for infinite recursion but many
various types of operations within the component model are naturally
written as recursion over the structure of a type which can lead to
stack overflow with deeply recursive types. Some examples of recursive
operations are:

* Lifting and lowering a type - currently the recursion here is modeled
  in Rust directly with `#[derive]` implementations as well as the
  implementations for the `Val` type.

* Compilation of adapter trampolines which iterates over the type
  structure recursively.

* Historically many various calculations like the size of a type, the
  flattened representation of a type, etc, were all done recursively.
  Many of these are more efficiently done via other means but it was
  still natural to implement these recursively initially.

By placing a hard limit on type recursion Wasmtime won't be able to load
some otherwise-valid modules. The hope, though, is that no human-written
program is likely to ever reach this limit. This limit can be revised
and/or the locations with recursion revised if it's ever reached.

The implementation of this feature is done by generalizing the current
flattened-representation calculation which now keeps track of a type's
depth and size. The size calculation isn't used just yet but I plan to
use it in fixing #4816 and it was natural enough to write here as well.
The depth is checked after a type is translated and if it exceeds the
maximum then an error is returned.

Additionally the `Arbitrary for Type` implementation was updated to
prevent generation of a type that's too-recursive.

Closes #4814

<!--

Please ensure that the following steps are all taken care of before submitting
the PR.

- [ ] This has been discussed in issue #..., or if not, please tell us why
  here.
- [ ] A short description of what this does, why it is needed; if the
  description becomes long, the matter should probably be discussed in an issue
  first.
- [ ] This PR contains test cases, if meaningful.
- [ ] A reviewer from the core maintainer team has been assigned for this PR.
  If you don't know who could review this, please indicate so. The list of
  suggested reviewers on the right can help you.

Please ensure all communication adheres to the [code of
conduct](https://github.com/bytecodealliance/wasmtime/blob/master/CODE_OF_CONDUCT.md).
-->


Patch:
diff --git a/crates/environ/src/component/types.rs b/crates/environ/src/component/types.rs
index eab476d94..e6ec9f7c0 100644
--- a/crates/environ/src/component/types.rs
+++ b/crates/environ/src/component/types.rs
@@ -14,6 +14,15 @@ use wasmparser::{
 };
 use wasmtime_component_util::{DiscriminantSize, FlagsSize};
 
+/// Maximum nesting depth of a type allowed in Wasmtime.
+///
+/// This constant isn't chosen via any scientific means and its main purpose is
+/// to enable most of Wasmtime to handle types via recursion without worrying
+/// about stack overflow.
+///
+/// Some more information about this can be found in #4814
+const MAX_TYPE_DEPTH: u32 = 100;
+
 macro_rules! indices {
     ($(
         $(#[$a:meta])*
@@ -75,10 +84,6 @@ indices! {
     /// as interface types.
     pub struct TypeFuncIndex(u32);
 
-    /// Index pointing to an interface type, used for recursive types such as
-    /// `List<T>`.
-    pub struct TypeInterfaceIndex(u32);
-
     /// Index pointing to a record type in the component model (aka a struct).
     pub struct TypeRecordIndex(u32);
     /// Index pointing to a variant type in the component model (aka an enum).
@@ -97,6 +102,8 @@ indices! {
     /// Index pointing to an result type in the component model (aka a
     /// `Result<T, E>`)
     pub struct TypeResultIndex(u32);
+    /// Index pointing to a list type in the component model.
+    pub struct TypeListIndex(u32);
 
     // ========================================================================
     // Index types used to identify modules and components during compilation.
@@ -207,7 +214,7 @@ pub struct ComponentTypes {
     components: PrimaryMap<TypeComponentIndex, TypeComponent>,
     component_instances: PrimaryMap<TypeComponentInstanceIndex, TypeComponentInstance>,
     functions: PrimaryMap<TypeFuncIndex, TypeFunc>,
-    interface_types: PrimaryMap<TypeInterfaceIndex, InterfaceType>,
+    lists: PrimaryMap<TypeListIndex, TypeList>,
     records: PrimaryMap<TypeRecordIndex, TypeRecord>,
     variants: PrimaryMap<TypeVariantIndex, TypeVariant>,
     tuples: PrimaryMap<TypeTupleIndex, TypeTuple>,
@@ -274,7 +281,6 @@ impl_index! {
     impl Index<TypeComponentIndex> for ComponentTypes { TypeComponent => components }
     impl Index<TypeComponentInstanceIndex> for ComponentTypes { TypeComponentInstance => component_instances }
     impl Index<TypeFuncIndex> for ComponentTypes { TypeFunc => functions }
-    impl Index<TypeInterfaceIndex> for ComponentTypes { InterfaceType => interface_types }
     impl Index<TypeRecordIndex> for ComponentTypes { TypeRecord => records }
     impl Index<TypeVariantIndex> for ComponentTypes { TypeVariant => variants }
     impl Index<TypeTupleIndex> for ComponentTypes { TypeTuple => tuples }
@@ -283,6 +289,7 @@ impl_index! {
     impl Index<TypeUnionIndex> for ComponentTypes { TypeUnion => unions }
     impl Index<TypeOptionIndex> for ComponentTypes { TypeOption => options }
     impl Index<TypeResultIndex> for ComponentTypes { TypeResult => results }
+    impl Index<TypeListIndex> for ComponentTypes { TypeList => lists }
 }
 
 // Additionally forward anything that can index `ModuleTypes` to `ModuleTypes`
@@ -305,7 +312,7 @@ where
 pub struct ComponentTypesBuilder {
     type_scopes: Vec<TypeScope>,
     functions: HashMap<TypeFunc, TypeFuncIndex>,
-    interface_types: HashMap<InterfaceType, TypeInterfaceIndex>,
+    lists: HashMap<TypeList, TypeListIndex>,
     records: HashMap<TypeRecord, TypeRecordIndex>,
     variants: HashMap<TypeVariant, TypeVariantIndex>,
     tuples: HashMap<TypeTuple, TypeTupleIndex>,
@@ -321,7 +328,7 @@ pub struct ComponentTypesBuilder {
     // Cache of what the "flat" representation of all types are which is only
     // used at compile-time and not used at runtime, hence the location here
     // as opposed to `ComponentTypes`.
-    flat: FlatTypesCache,
+    type_info: TypeInformationCache,
 }
 
 #[derive(Default)]
@@ -336,9 +343,9 @@ macro_rules! intern_and_fill_flat_types {
             return *idx;
         }
         let idx = $me.component_types.$name.push($val.clone());
-        let mut storage = FlatTypesStorage::new();
-        storage.$name($me, &$val);
-        let idx2 = $me.flat.$name.push(storage);
+        let mut info = TypeInformation::new();
+        info.$name($me, &$val);
+        let idx2 = $me.type_info.$name.push(info);
         assert_eq!(idx, idx2);
         $me.$name.insert($val, idx);
         return idx;
@@ -433,7 +440,7 @@ impl ComponentTypesBuilder {
     /// interning types along the way.
     pub fn intern_component_type(&mut self, ty: &wasmparser::ComponentType<'_>) -> Result<TypeDef> {
         Ok(match ty {
-            wasmparser::ComponentType::Defined(ty) => TypeDef::Interface(self.defined_type(ty)),
+            wasmparser::ComponentType::Defined(ty) => TypeDef::Interface(self.defined_type(ty)?),
             wasmparser::ComponentType::Func(ty) => TypeDef::ComponentFunc(self.func_type(ty)),
             wasmparser::ComponentType::Component(ty) => {
                 TypeDef::Component(self.component_type(ty)?)
@@ -644,8 +651,8 @@ impl ComponentTypesBuilder {
         self.add_func_type(ty)
     }
 
-    fn defined_type(&mut self, ty: &wasmparser::ComponentDefinedType<'_>) -> InterfaceType {
-        match ty {
+    fn defined_type(&mut self, ty: &wasmparser::ComponentDefinedType<'_>) -> Result<InterfaceType> {
+        let result = match ty {
             wasmparser::ComponentDefinedType::Primitive(ty) => ty.into(),
             wasmparser::ComponentDefinedType::Record(e) => {
                 InterfaceType::Record(self.record_type(e))
@@ -653,10 +660,7 @@ impl ComponentTypesBuilder {
             wasmparser::ComponentDefinedType::Variant(e) => {
                 InterfaceType::Variant(self.variant_type(e))
             }
-            wasmparser::ComponentDefinedType::List(e) => {
-                let ty = self.valtype(e);
-                InterfaceType::List(self.add_interface_type(ty))
-            }
+            wasmparser::ComponentDefinedType::List(e) => InterfaceType::List(self.list_type(e)),
             wasmparser::ComponentDefinedType::Tuple(e) => InterfaceType::Tuple(self.tuple_type(e)),
             wasmparser::ComponentDefinedType::Flags(e) => InterfaceType::Flags(self.flags_type(e)),
             wasmparser::ComponentDefinedType::Enum(e) => InterfaceType::Enum(self.enum_type(e)),
@@ -667,7 +671,12 @@ impl ComponentTypesBuilder {
             wasmparser::ComponentDefinedType::Result { ok, err } => {
                 InterfaceType::Result(self.result_type(ok, err))
             }
+        };
+        let info = self.type_information(&result);
+        if info.depth > MAX_TYPE_DEPTH {
+            bail!("type nesting is too deep");
         }
+        Ok(result)
     }
 
     fn valtype(&mut self, ty: &wasmparser::ComponentValType) -> InterfaceType {
@@ -780,6 +789,11 @@ impl ComponentTypesBuilder {
         self.add_result_type(TypeResult { ok, err, abi, info })
     }
 
+    fn list_type(&mut self, ty: &wasmparser::ComponentValType) -> TypeListIndex {
+        let element = self.valtype(ty);
+        self.add_list_type(TypeList { element })
+    }
+
     /// Interns a new function type within this type information.
     pub fn add_func_type(&mut self, ty: TypeFunc) -> TypeFuncIndex {
         intern(&mut self.functions, &mut self.component_types.functions, ty)
@@ -826,12 +840,8 @@ impl ComponentTypesBuilder {
     }
 
     /// Interns a new type within this type information.
-    pub fn add_interface_type(&mut self, ty: InterfaceType) -> TypeInterfaceIndex {
-        intern(
-            &mut self.interface_types,
-            &mut self.component_types.interface_types,
-            ty,
-        )
+    pub fn add_list_type(&mut self, ty: TypeList) -> TypeListIndex {
+        intern_and_fill_flat_types!(self, lists, ty)
     }
 
     /// Returns the canonical ABI information about the specified type.
@@ -845,6 +855,10 @@ impl ComponentTypesBuilder {
     /// Returns `None` if the type is too large to be represented via flat types
     /// in the canonical abi.
     pub fn flat_types(&self, ty: &InterfaceType) -> Option<FlatTypes<'_>> {
+        self.type_information(ty).flat.as_flat_types()
+    }
+
+    fn type_information(&self, ty: &InterfaceType) -> &TypeInformation {
         match ty {
             InterfaceType::U8
             | InterfaceType::S8
@@ -853,20 +867,36 @@ impl ComponentTypesBuilder {
             | InterfaceType::S16
             | InterfaceType::U32
             | InterfaceType::S32
-            | InterfaceType::Char => Some(FlatTypes::I32),
-            InterfaceType::U64 | InterfaceType::S64 => Some(FlatTypes::I64),
-            InterfaceType::Float32 => Some(FlatTypes::F32),
-            InterfaceType::Float64 => Some(FlatTypes::F64),
-            InterfaceType::String | InterfaceType::List(_) => Some(FlatTypes::POINTER_PAIR),
-
-            InterfaceType::Record(i) => self.flat.records[*i].as_flat_types(),
-            InterfaceType::Variant(i) => self.flat.variants[*i].as_flat_types(),
-            InterfaceType::Tuple(i) => self.flat.tuples[*i].as_flat_types(),
-            InterfaceType::Flags(i) => self.flat.flags[*i].as_flat_types(),
-            InterfaceType::Enum(i) => self.flat.enums[*i].as_flat_types(),
-            InterfaceType::Union(i) => self.flat.unions[*i].as_flat_types(),
-            InterfaceType::Option(i) => self.flat.options[*i].as_flat_types(),
-            InterfaceType::Result(i) => self.flat.results[*i].as_flat_types(),
+            | InterfaceType::Char => {
+                static INFO: TypeInformation = TypeInformation::primitive(FlatType::I32);
+                &INFO
+            }
+            InterfaceType::U64 | InterfaceType::S64 => {
+                static INFO: TypeInformation = TypeInformation::primitive(FlatType::I64);
+                &INFO
+            }
+            InterfaceType::Float32 => {
+                static INFO: TypeInformation = TypeInformation::primitive(FlatType::F32);
+                &INFO
+            }
+            InterfaceType::Float64 => {
+                static INFO: TypeInformation = TypeInformation::primitive(FlatType::F64);
+                &INFO
+            }
+            InterfaceType::String => {
+                static INFO: TypeInformation = TypeInformation::string();
+                &INFO
+            }
+
+            InterfaceType::List(i) => &self.type_info.lists[*i],
+            InterfaceType::Record(i) => &self.type_info.records[*i],
+            InterfaceType::Variant(i) => &self.type_info.variants[*i],
+            InterfaceType::Tuple(i) => &self.type_info.tuples[*i],
+            InterfaceType::Flags(i) => &self.type_info.flags[*i],
+            InterfaceType::Enum(i) => &self.type_info.enums[*i],
+            InterfaceType::Union(i) => &self.type_info.unions[*i],
+            InterfaceType::Option(i) => &self.type_info.options[*i],
+            InterfaceType::Result(i) => &self.type_info.results[*i],
         }
     }
 }
@@ -997,7 +1027,7 @@ pub enum InterfaceType {
     String,
     Record(TypeRecordIndex),
     Variant(TypeVariantIndex),
-    List(TypeInterfaceIndex),
+    List(TypeListIndex),
     Tuple(TypeTupleIndex),
     Flags(TypeFlagsIndex),
     Enum(TypeEnumIndex),
@@ -1484,6 +1514,13 @@ pub struct TypeResult {
     pub info: VariantInfo,
 }
 
+/// Shape of a "list" interface type.
+#[derive(Serialize, Deserialize, Clone, Hash, Eq, PartialEq, Debug)]
+pub struct TypeList {
+    /// The element type of the list.
+    pub element: InterfaceType,
+}
+
 const MAX_FLAT_TYPES: usize = if MAX_FLAT_PARAMS > MAX_FLAT_RESULTS {
     MAX_FLAT_PARAMS
 } else {
@@ -1529,22 +1566,6 @@ pub struct FlatTypes<'a> {
 
 #[allow(missing_docs)]
 impl FlatTypes<'_> {
-    pub const I32: FlatTypes<'static> = FlatTypes::new(&[FlatType::I32]);
-    pub const I64: FlatTypes<'static> = FlatTypes::new(&[FlatType::I64]);
-    pub const F32: FlatTypes<'static> = FlatTypes::new(&[FlatType::F32]);
-    pub const F64: FlatTypes<'static> = FlatTypes::new(&[FlatType::F64]);
-    pub const POINTER_PAIR: FlatTypes<'static> = FlatTypes {
-        memory32: &[FlatType::I32, FlatType::I32],
-        memory64: &[FlatType::I64, FlatType::I64],
-    };
-
-    const fn new(flat: &[FlatType]) -> FlatTypes<'_> {
-        FlatTypes {
-            memory32: flat,
-            memory64: flat,
-        }
-    }
-
     /// Returns the number of flat types used to represent this type.
     ///
     /// Note that this length is the same regardless to the size of memory.
@@ -1566,18 +1587,6 @@ pub enum FlatType {
     F64,
 }
 
-#[derive(Default)]
-struct FlatTypesCache {
-    records: PrimaryMap<TypeRecordIndex, FlatTypesStorage>,
-    variants: PrimaryMap<TypeVariantIndex, FlatTypesStorage>,
-    tuples: PrimaryMap<TypeTupleIndex, FlatTypesStorage>,
-    enums: PrimaryMap<TypeEnumIndex, FlatTypesStorage>,
-    flags: PrimaryMap<TypeFlagsIndex, FlatTypesStorage>,
-    unions: PrimaryMap<TypeUnionIndex, FlatTypesStorage>,
-    options: PrimaryMap<TypeOptionIndex, FlatTypesStorage>,
-    results: PrimaryMap<TypeResultIndex, FlatTypesStorage>,
-}
-
 struct FlatTypesStorage {
     // This could be represented as `Vec<FlatType>` but on 64-bit architectures
     // that's 24 bytes. Otherwise `FlatType` is 1 byte large and
@@ -1593,7 +1602,7 @@ struct FlatTypesStorage {
 }
 
 impl FlatTypesStorage {
-    fn new() -> FlatTypesStorage {
+    const fn new() -> FlatTypesStorage {
         FlatTypesStorage {
             memory32: [FlatType::I32; MAX_FLAT_TYPES],
             memory64: [FlatType::I32; MAX_FLAT_TYPES],
@@ -1636,21 +1645,82 @@ impl FlatTypesStorage {
             false
         }
     }
+}
+
+impl FlatType {
+    fn join(&mut self, other: FlatType) {
+        if *self == other {
+            return;
+        }
+        *self = match (*self, other) {
+            (FlatType::I32, FlatType::F32) | (FlatType::F32, FlatType::I32) => FlatType::I32,
+            _ => FlatType::I64,
+        };
+    }
+}
+
+#[derive(Default)]
+struct TypeInformationCache {
+    records: PrimaryMap<TypeRecordIndex, TypeInformation>,
+    variants: PrimaryMap<TypeVariantIndex, TypeInformation>,
+    tuples: PrimaryMap<TypeTupleIndex, TypeInformation>,
+    enums: PrimaryMap<TypeEnumIndex, TypeInformation>,
+    flags: PrimaryMap<TypeFlagsIndex, TypeInformation>,
+    unions: PrimaryMap<TypeUnionIndex, TypeInformation>,
+    options: PrimaryMap<TypeOptionIndex, TypeInformation>,
+    results: PrimaryMap<TypeResultIndex, TypeInformation>,
+    lists: PrimaryMap<TypeListIndex, TypeInformation>,
+}
+
+struct TypeInformation {
+    depth: u32,
+    flat: FlatTypesStorage,
+}
+
+impl TypeInformation {
+    const fn new() -> TypeInformation {
+        TypeInformation {
+            depth: 0,
+            flat: FlatTypesStorage::new(),
+        }
+    }
+
+    const fn primitive(flat: FlatType) -> TypeInformation {
+        let mut info = TypeInformation::new();
+        info.depth = 1;
+        info.flat.memory32[0] = flat;
+        info.flat.memory64[0] = flat;
+        info.flat.len = 1;
+        info
+    }
+
+    const fn string() -> TypeInformation {
+        let mut info = TypeInformation::new();
+        info.depth = 1;
+        info.flat.memory32[0] = FlatType::I32;
+        info.flat.memory32[1] = FlatType::I32;
+        info.flat.memory64[0] = FlatType::I64;
+        info.flat.memory64[1] = FlatType::I64;
+        info.flat.len = 2;
+        info
+    }
 
     /// Builds up all flat types internally using the specified representation
     /// for all of the component fields of the record.
-    fn build_record<'a>(&mut self, types: impl Iterator<Item = Option<FlatTypes<'a>>>) {
-        for ty in types {
-            let types = match ty {
-                Some(types) => types,
-                None => {
-                    self.len = u8::try_from(MAX_FLAT_TYPES + 1).unwrap();
-                    return;
+    fn build_record<'a>(&mut self, types: impl Iterator<Item = &'a TypeInformation>) {
+        self.depth = 1;
+        for info in types {
+            self.depth = self.depth.max(1 + info.depth);
+            match info.flat.as_flat_types() {
+                Some(types) => {
+                    for (t32, t64) in types.memory32.iter().zip(types.memory64) {
+                        if !self.flat.push(*t32, *t64) {
+                            break;
+                        }
+                    }
                 }
-            };
-            for (t32, t64) in types.memory32.iter().zip(types.memory64) {
-                if !self.push(*t32, *t64) {
-                    return;
+                None => {
+                    self.flat.len = u8::try_from(MAX_FLAT_TYPES + 1).unwrap();
                 }
             }
         }
@@ -1669,32 +1739,49 @@ impl FlatTypesStorage {
     ///   the types specified in the flat representation.
     fn build_variant<'a, I>(&mut self, cases: I)
     where
-        I: IntoIterator<Item = Option<Option<FlatTypes<'a>>>>,
+        I: IntoIterator<Item = Option<&'a TypeInformation>>,
     {
         let cases = cases.into_iter();
-        self.push(FlatType::I32, FlatType::I32);
+        self.flat.push(FlatType::I32, FlatType::I32);
+        self.depth = 1;
+
+        for info in cases {
+            let info = match info {
+                Some(info) => info,
+                // If this case doesn't have a payload then it doesn't change
+                // the depth/flat representation
+                None => continue,
+            };
+            self.depth = self.depth.max(1 + info.depth);
+
+            // If this variant is already unrepresentable in a flat
+            // representation then this can be skipped.
+            if usize::from(self.flat.len) > MAX_FLAT_TYPES {
+                continue;
+            }
 
-        for ty in cases {
-            let types = match ty {
-                Some(Some(types)) => types,
+            let types = match info.flat.as_flat_types() {
+                Some(types) => types,
                 // If this case isn't representable with a flat list of types
                 // then this variant also isn't representable.
-                Some(None) => {
-                    self.len = u8::try_from(MAX_FLAT_TYPES + 1).unwrap();
-                    return;
+                None => {
+                    self.flat.len = u8::try_from(MAX_FLAT_TYPES + 1).unwrap();
+                    continue;
                 }
-                // If this case doesn't have a payload then it doesn't change
-                // whether this is representable or not.
-                None => continue,
             };
             // If the case used all of the flat types then the discriminant
             // added for this variant means that this variant is no longer
             // representable.
             if types.memory32.len() >= MAX_FLAT_TYPES {
-                self.len = u8::try_from(MAX_FLAT_TYPES + 1).unwrap();
-                return;
+                self.flat.len = u8::try_from(MAX_FLAT_TYPES + 1).unwrap();
+                continue;
             }
-            let dst = self.memory32.iter_mut().zip(&mut self.memory64).skip(1);
+            let dst = self
+                .flat
+                .memory32
+                .iter_mut()
+                .zip(&mut self.flat.memory64)
+                .skip(1);
             for (i, ((t32, t64), (dst32, dst64))) in types
                 .memory32
                 .iter()
@@ -1702,7 +1789,7 @@ impl FlatTypesStorage {
                 .zip(dst)
                 .enumerate()
             {
-                if i + 1 < usize::from(self.len) {
+                if i + 1 < usize::from(self.flat.len) {
                     // If this index hs already been set by some previous case
                     // then the types are joined together.
                     dst32.join(*t32);
@@ -1712,7 +1799,7 @@ impl FlatTypesStorage {
                     // representation has gotten this large then the destination
                     // is simply whatever the type is. The length is also
                     // increased here to indicate this.
-                    self.len += 1;
+                    self.flat.len += 1;
                     *dst32 = *t32;
                     *dst64 = *t64;
                 }
@@ -1721,26 +1808,28 @@ impl FlatTypesStorage {
     }
 
     fn records(&mut self, types: &ComponentTypesBuilder, ty: &TypeRecord) {
-        self.build_record(ty.fields.iter().map(|f| types.flat_types(&f.ty)));
+        self.build_record(ty.fields.iter().map(|f| types.type_information(&f.ty)));
     }
 
     fn tuples(&mut self, types: &ComponentTypesBuilder, ty: &TypeTuple) {
-        self.build_record(ty.types.iter().map(|t| types.flat_types(t)));
+        self.build_record(ty.types.iter().map(|t| types.type_information(t)));
     }
 
     fn enums(&mut self, _types: &ComponentTypesBuilder, _ty: &TypeEnum) {
-        self.push(FlatType::I32, FlatType::I32);
+        self.depth = 1;
+        self.flat.push(FlatType::I32, FlatType::I32);
     }
 
     fn flags(&mut self, _types: &ComponentTypesBuilder, ty: &TypeFlags) {
+        self.depth = 1;
         match FlagsSize::from_count(ty.names.len()) {
             FlagsSize::Size0 => {}
             FlagsSize::Size1 | FlagsSize::Size2 => {
-                self.push(FlatType::I32, FlatType::I32);
+                self.flat.push(FlatType::I32, FlatType::I32);
             }
             FlagsSize::Size4Plus(n) => {
                 for _ in 0..n {
-                    self.push(FlatType::I32, FlatType::I32);
+                    self.flat.push(FlatType::I32, FlatType::I32);
                 }
             }
         }
@@ -1750,34 +1839,28 @@ impl FlatTypesStorage {
         self.build_variant(
             ty.cases
                 .iter()
-                .map(|c| c.ty.as_ref().map(|ty| types.flat_types(ty))),
+                .map(|c| c.ty.as_ref().map(|ty| types.type_information(ty))),
         )
     }
 
     fn unions(&mut self, types: &ComponentTypesBuilder, ty: &TypeUnion) {
-        self.build_variant(ty.types.iter().map(|t| Some(types.flat_types(t))))
+        self.build_variant(ty.types.iter().map(|t| Some(types.type_information(t))))
     }
 
     fn results(&mut self, types: &ComponentTypesBuilder, ty: &TypeResult) {
         self.build_variant([
-            ty.ok.as_ref().map(|ty| types.flat_types(ty)),
-            ty.err.as_ref().map(|ty| types.flat_types(ty)),
+            ty.ok.as_ref().map(|ty| types.type_information(ty)),
+            ty.err.as_ref().map(|ty| types.type_information(ty)),
         ])
     }
 
     fn options(&mut self, types: &ComponentTypesBuilder, ty: &TypeOption) {
-        self.build_variant([None, Some(types.flat_types(&ty.ty))]);
+        self.build_variant([None, Some(types.type_information(&ty.ty))]);
     }
-}
 
-impl FlatType {
-    fn join(&mut self, other: FlatType) {
-        if *self == other {
-            return;
-        }
-        *self = match (*self, other) {
-            (FlatType::I32, FlatType::F32) | (FlatType::F32, FlatType::I32) => FlatType::I32,
-            _ => FlatType::I64,
-        };
+    fn lists(&mut self, types: &ComponentTypesBuilder, ty: &TypeList) {
+        *self = TypeInformation::string();
+        let info = types.type_information(&ty.element);
+        self.depth += info.depth;
     }
 }
diff --git a/crates/environ/src/fact/trampoline.rs b/crates/environ/src/fact/trampoline.rs
index 127d49829..70255f990 100644
--- a/crates/environ/src/fact/trampoline.rs
+++ b/crates/environ/src/fact/trampoline.rs
@@ -17,7 +17,7 @@
 
 use crate::component::{
     CanonicalAbiInfo, ComponentTypesBuilder, FlatType, InterfaceType, StringEncoding,
-    TypeEnumIndex, TypeFlagsIndex, TypeInterfaceIndex, TypeOptionIndex, TypeRecordIndex,
+    TypeEnumIndex, TypeFlagsIndex, TypeListIndex, TypeOptionIndex, TypeRecordIndex,
     TypeResultIndex, TypeTupleIndex, TypeUnionIndex, TypeVariantIndex, VariantInfo, FLAG_MAY_ENTER,
     FLAG_MAY_LEAVE, MAX_FLAT_PARAMS, MAX_FLAT_RESULTS,
 };
@@ -1723,14 +1723,14 @@ impl Compiler<'_, '_> {
 
     fn translate_list(
         &mut self,
-        src_ty: TypeInterfaceIndex,
+        src_ty: TypeListIndex,
         src: &Source<'_>,
         dst_ty: &InterfaceType,
         dst: &Destination,
     ) {
-        let src_element_ty = &self.types[src_ty];
+        let src_element_ty = &self.types[src_ty].element;
         let dst_element_ty = match dst_ty {
-            InterfaceType::List(r) => &self.types[*r],
+            InterfaceType::List(r) => &self.types[*r].element,
             _ => panic!("expected a list"),
         };
         let src_opts = src.opts();
diff --git a/crates/misc/component-fuzz-util/src/lib.rs b/crates/misc/component-fuzz-util/src/lib.rs
index db963e200..1d9d29697 100644
--- a/crates/misc/component-fuzz-util/src/lib.rs
+++ b/crates/misc/component-fuzz-util/src/lib.rs
@@ -19,6 +19,9 @@ const MAX_FLAT_PARAMS: usize = 16;
 const MAX_FLAT_RESULTS: usize = 1;
 const MAX_ARITY: u32 = 5;
 
+// Wasmtime allows up to 100 type depth so limit this to just under that.
+const MAX_TYPE_DEPTH: u32 = 99;
+
 /// The name of the imported host function which the generated component will call
 pub const IMPORT_FUNCTION: &str = "echo";
 
@@ -77,17 +80,26 @@ impl<'a, const L: usize, const H: usize> Arbitrary<'a> for UsizeInRange<L, H> {
 #[derive(Debug, Clone)]
 pub struct VecInRange<T, const L: u32, const H: u32>(Vec<T>);
 
-impl<'a, T: Arbitrary<'a>, const L: u32, const H: u32> Arbitrary<'a> for VecInRange<T, L, H> {
-    fn arbitrary(input: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
+impl<T, const L: u32, const H: u32> VecInRange<T, L, H> {
+    fn new<'a>(
+        input: &mut Unstructured<'a>,
+        gen: impl Fn(&mut Unstructured<'a>) -> arbitrary::Result<T>,
+    ) -> arbitrary::Result<Self> {
         let mut ret = Vec::new();
         input.arbitrary_loop(Some(L), Some(H), |input| {
-            ret.push(input.arbitrary()?);
+            ret.push(gen(input)?);
             Ok(std::ops::ControlFlow::Continue(()))
         })?;
         Ok(Self(ret))
     }
 }
 
+impl<'a, T: Arbitrary<'a>, const L: u32, const H: u32> Arbitrary<'a> for VecInRange<T, L, H> {
+    fn arbitrary(input: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
+        VecInRange::new(input, |input| input.arbitrary())
+    }
+}
+
 impl<T, const L: u32, const H: u32> Deref for VecInRange<T, L, H> {
     type Target = [T];
 
@@ -98,7 +110,7 @@ impl<T, const L: u32, const H: u32> Deref for VecInRange<T, L, H> {
 
 /// Represents a component model interface type
 #[allow(missing_docs)]
-#[derive(Arbitrary, Debug, Clone)]
+#[derive(Debug, Clone)]
 pub enum Type {
     Bool,
     S8,
@@ -143,6 +155,63 @@ pub enum Type {
     Flags(UsizeInRange<0, 65>),
 }
 
+impl Type {
+    fn generate(u: &mut Unstructured<'_>, depth: u32) -> arbitrary::Result<Type> {
+        let max = if depth == 0 { 12 } else { 21 };
+        Ok(match u.int_in_range(0..=max)? {
+            0 => Type::Bool,
+            1 => Type::S8,
+            2 => Type::U8,
+            3 => Type::S16,
+            4 => Type::U16,
+            5 => Type::S32,
+            6 => Type::U32,
+            7 => Type::S64,
+            8 => Type::U64,
+            9 => Type::Float32,
+            10 => Type::Float64,
+            11 => Type::Char,
+            12 => Type::String,
+            // ^-- if you add something here update the `depth == 0` case above
+            13 => Type::List(Box::new(Type::generate(u, depth - 1)?)),
+            14 => Type::Record(Type::generate_list(u, depth - 1)?),
+            15 => Type::Tuple(Type::generate_list(u, depth - 1)?),
+            16 => Type::Variant(VecInRange::new(u, |u| Type::generate_opt(u, depth - 1))?),
+            17 => Type::Enum(u.arbitrary()?),
+            18 => Type::Union(Type::generate_list(u, depth - 1)?),
+            19 => Type::Option(Box::new(Type::generate(u, depth - 1)?)),
+            20 => Type::Result {
+                ok: Type::generate_opt(u, depth - 1)?.map(Box::new),
+                err: Type::generate_opt(u, depth - 1)?.map(Box::new),
+            },
+            21 => Type::Flags(u.arbitrary()?),
+            // ^-- if you add something here update the `depth != 0` case above
+            _ => unreachable!(),
+        })
+    }
+
+    fn generate_opt(u: &mut Unstructured<'_>, depth: u32) -> arbitrary::Result<Option<Type>> {
+        Ok(if u.arbitrary()? {
+            Some(Type::generate(u, depth)?)
+        } else {
+            None
+        })
+    }
+
+    fn generate_list<const L: u32, const H: u32>(
+        u: &mut Unstructured<'_>,
+        depth: u32,
+    ) -> arbitrary::Result<VecInRange<Type, L, H>> {
+        VecInRange::new(u, |u| Type::generate(u, depth))
+    }
+}
+
+impl<'a> Arbitrary<'a> for Type {
+    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Type> {
+        Type::generate(u, MAX_TYPE_DEPTH)
+    }
+}
+
 fn lower_record<'a>(types: impl Iterator<Item = &'a Type>, vec: &mut Vec<CoreType>) {
     for ty in types {
         ty.lower(vec);
diff --git a/crates/wasmtime/src/component/func/typed.rs b/crates/wasmtime/src/component/func/typed.rs
index bc88fb0ab..8cff6b1ac 100644
--- a/crates/wasmtime/src/component/func/typed.rs
+++ b/crates/wasmtime/src/component/func/typed.rs
@@ -1114,7 +1114,7 @@ where
 
     fn typecheck(ty: &InterfaceType, types: &ComponentTypes) -> Result<()> {
         match ty {
-            InterfaceType::List(t) => T::typecheck(&types[*t], types),
+            InterfaceType::List(t) => T::typecheck(&types[*t].element, types),
             other => bail!("expected `list` found `{}`", desc(other)),
         }
     }
@@ -1322,10 +1322,7 @@ unsafe impl<T: ComponentType> ComponentType for WasmList<T> {
     const ABI: CanonicalAbiInfo = CanonicalAbiInfo::POINTER_PAIR;
 
     fn typecheck(ty: &InterfaceType, types: &ComponentTypes) -> Result<()> {
-        match ty {
-            InterfaceType::List(t) => T::typecheck(&types[*t], types),
-            other => bail!("expected `list` found `{}`", desc(other)),
-        }
+        <[T] as ComponentType>::typecheck(ty, types)
     }
 }
 
diff --git a/crates/wasmtime/src/component/types.rs b/crates/wasmtime/src/component/types.rs
index a1dacacbc..99d3f3583 100644
--- a/crates/wasmtime/src/component/types.rs
+++ b/crates/wasmtime/src/component/types.rs
@@ -7,9 +7,9 @@ use std::mem;
 use std::ops::Deref;
 use std::sync::Arc;
 use wasmtime_environ::component::{
-    CanonicalAbiInfo, ComponentTypes, InterfaceType, TypeEnumIndex, TypeFlagsIndex,
-    TypeInterfaceIndex, TypeOptionIndex, TypeRecordIndex, TypeResultIndex, TypeTupleIndex,
-    TypeUnionIndex, TypeVariantIndex, VariantInfo,
+    CanonicalAbiInfo, ComponentTypes, InterfaceType, TypeEnumIndex, TypeFlagsIndex, TypeListIndex,
+    TypeOptionIndex, TypeRecordIndex, TypeResultIndex, TypeTupleIndex, TypeUnionIndex,
+    TypeVariantIndex, VariantInfo,
 };
 
 #[derive(Clone)]
@@ -39,7 +39,7 @@ impl<T: Eq> Eq for Handle<T> {}
 
 /// A `list` interface type
 #[derive(Clone, PartialEq, Eq, Debug)]
-pub struct List(Handle<TypeInterfaceIndex>);
+pub struct List(Handle<TypeListIndex>);
 
 impl List {
     /// Instantiate this type with the specified `values`.
@@ -49,7 +49,7 @@ impl List {
 
     /// Retreive the element type of this `list`.
     pub fn ty(&self) -> Type {
-        Type::from(&self.0.types[self.0.index], &self.0.types)
+        Type::from(&self.0.types[self.0.index].element, &self.0.types)
     }
 }
 


Test patch:
diff --git a/tests/misc_testsuite/component-model/types.wast b/tests/misc_testsuite/component-model/types.wast
index eef65f7aa..010fee3ec 100644
--- a/tests/misc_testsuite/component-model/types.wast
+++ b/tests/misc_testsuite/component-model/types.wast
@@ -140,3 +140,109 @@
 (assert_return (invoke "i-to-s16" (u32.const 0)) (s16.const 0))
 (assert_return (invoke "i-to-s16" (u32.const 1)) (s16.const 1))
 (assert_return (invoke "i-to-s16" (u32.const 0xffffffff)) (s16.const -1))
+
+(assert_invalid
+  (component
+    (type $t1 string)
+    (type $t2 (list $t1))
+    (type $t3 (list $t2))
+    (type $t4 (list $t3))
+    (type $t5 (list $t4))
+    (type $t6 (list $t5))
+    (type $t7 (list $t6))
+    (type $t8 (list $t7))
+    (type $t9 (list $t8))
+    (type $t10 (list $t9))
+    (type $t11 (list $t10))
+    (type $t12 (list $t11))
+    (type $t13 (list $t12))
+    (type $t14 (list $t13))
+    (type $t15 (list $t14))
+    (type $t16 (list $t15))
+    (type $t17 (list $t16))
+    (type $t18 (list $t17))
+    (type $t19 (list $t18))
+    (type $t20 (list $t19))
+    (type $t21 (list $t20))
+    (type $t22 (list $t21))
+    (type $t23 (list $t22))
+    (type $t24 (list $t23))
+    (type $t25 (list $t24))
+    (type $t26 (list $t25))
+    (type $t27 (list $t26))
+    (type $t28 (list $t27))
+    (type $t29 (list $t28))
+    (type $t30 (list $t29))
+    (type $t31 (list $t30))
+    (type $t32 (list $t31))
+    (type $t33 (list $t32))
+    (type $t34 (list $t33))
+    (type $t35 (list $t34))
+    (type $t36 (list $t35))
+    (type $t37 (list $t36))
+    (type $t38 (list $t37))
+    (type $t39 (list $t38))
+    (type $t40 (list $t39))
+    (type $t41 (list $t40))
+    (type $t42 (list $t41))
+    (type $t43 (list $t42))
+    (type $t44 (list $t43))
+    (type $t45 (list $t44))
+    (type $t46 (list $t45))
+    (type $t47 (list $t46))
+    (type $t48 (list $t47))
+    (type $t49 (list $t48))
+    (type $t50 (list $t49))
+    (type $t51 (list $t50))
+    (type $t52 (list $t51))
+    (type $t53 (list $t52))
+    (type $t54 (list $t53))
+    (type $t55 (list $t54))
+    (type $t56 (list $t55))
+    (type $t57 (list $t56))
+    (type $t58 (list $t57))
+    (type $t59 (list $t58))
+    (type $t60 (list $t59))
+    (type $t61 (list $t60))
+    (type $t62 (list $t61))
+    (type $t63 (list $t62))
+    (type $t64 (list $t63))
+    (type $t65 (list $t64))
+    (type $t66 (list $t65))
+    (type $t67 (list $t66))
+    (type $t68 (list $t67))
+    (type $t69 (list $t68))
+    (type $t70 (list $t69))
+    (type $t71 (list $t70))
+    (type $t72 (list $t71))
+    (type $t73 (list $t72))
+    (type $t74 (list $t73))
+    (type $t75 (list $t74))
+    (type $t76 (list $t75))
+    (type $t77 (list $t76))
+    (type $t78 (list $t77))
+    (type $t79 (list $t78))
+    (type $t80 (list $t79))
+    (type $t81 (list $t80))
+    (type $t82 (list $t81))
+    (type $t83 (list $t82))
+    (type $t84 (list $t83))
+    (type $t85 (list $t84))
+    (type $t86 (list $t85))
+    (type $t87 (list $t86))
+    (type $t88 (list $t87))
+    (type $t89 (list $t88))
+    (type $t90 (list $t89))
+    (type $t91 (list $t90))
+    (type $t92 (list $t91))
+    (type $t93 (list $t92))
+    (type $t94 (list $t93))
+    (type $t95 (list $t94))
+    (type $t96 (list $t95))
+    (type $t97 (list $t96))
+    (type $t98 (list $t97))
+    (type $t99 (list $t98))
+    (type $t100 (list $t99))
+    (type $t101 (list $t100))
+  )
+  "type nesting is too deep")