Quellcode-Bibliothek core.rs   Sprache: unbekannt

//! Generating arbitary core Wasm modules.

mod code_builder;
pub(crate) mod encode;
mod terminate;

use crate::{arbitrary_loop, limited_string, unique_string, Config};
use arbitrary::{Arbitrary, Result, Unstructured};
use code_builder::CodeBuilderAllocations;
use flagset::{flags, FlagSet};
use std::collections::{HashMap, HashSet};
use std::fmt;
use std::mem;
use std::ops::Range;
use std::rc::Rc;
use std::str::{self, FromStr};
use wasm_encoder::{
    AbstractHeapType, ArrayType, BlockType, ConstExpr, ExportKind, FieldType, HeapType, RefType,
    StorageType, StructType, ValType,
};
pub(crate) use wasm_encoder::{GlobalType, MemoryType, TableType};

// NB: these constants are used to control the rate at which various events
// occur. For more information see where these constants are used. Their values
// are somewhat random in the sense that they're not scientifically determined
// or anything like that, I just threw a bunch of random data at wasm-smith and
// measured various rates of ooms/traps/etc and adjusted these so abnormal
// events were ~1% of the time.
const CHANCE_OFFSET_INBOUNDS: usize = 10; // bigger = less traps
const CHANCE_SEGMENT_ON_EMPTY: usize = 10; // bigger = less traps
const PCT_INBOUNDS: f64 = 0.995; // bigger = less traps

type Instruction = wasm_encoder::Instruction<'static>;

/// A pseudo-random WebAssembly module.
///
/// Construct instances of this type (with default configuration) with [the
/// `Arbitrary`
/// trait](https://docs.rs/arbitrary/*/arbitrary/trait.Arbitrary.html).
///
/// ## Configuring Generated Modules
///
/// To configure the shape of generated module, create a
/// [`Config`][crate::Config] and then call [`Module::new`][crate::Module::new]
/// with it.
pub struct Module {
    config: Config,
    duplicate_imports_behavior: DuplicateImportsBehavior,
    valtypes: Vec<ValType>,

    /// All types locally defined in this module (available in the type index
    /// space).
    types: Vec<SubType>,

    /// Non-overlapping ranges within `types` that belong to the same rec
    /// group. All of `types` is covered by these ranges. When GC is not
    /// enabled, these are all single-element ranges.
    rec_groups: Vec<Range<usize>>,

    /// A map from a super type to all of its sub types.
    super_to_sub_types: HashMap<u32, Vec<u32>>,

    /// Indices within `types` that are not final types.
    can_subtype: Vec<u32>,

    /// Whether we should encode a types section, even if `self.types` is empty.
    should_encode_types: bool,

    /// All of this module's imports. These don't have their own index space,
    /// but instead introduce entries to each imported entity's associated index
    /// space.
    imports: Vec<Import>,

    /// Whether we should encode an imports section, even if `self.imports` is
    /// empty.
    should_encode_imports: bool,

    /// Indices within `types` that are array types.
    array_types: Vec<u32>,

    /// Indices within `types` that are function types.
    func_types: Vec<u32>,

    /// Indices within `types that are struct types.
    struct_types: Vec<u32>,

    /// Number of imported items into this module.
    num_imports: usize,

    /// The number of tags defined in this module (not imported or
    /// aliased).
    num_defined_tags: usize,

    /// The number of functions defined in this module (not imported or
    /// aliased).
    num_defined_funcs: usize,

    /// Initialization expressions for all defined tables in this module.
    defined_tables: Vec<Option<ConstExpr>>,

    /// The number of memories defined in this module (not imported or
    /// aliased).
    num_defined_memories: usize,

    /// The indexes and initialization expressions of globals defined in this
    /// module.
    defined_globals: Vec<(u32, ConstExpr)>,

    /// All tags available to this module, sorted by their index. The list
    /// entry is the type of each tag.
    tags: Vec<TagType>,

    /// All functions available to this module, sorted by their index. The list
    /// entry points to the index in this module where the function type is
    /// defined (if available) and provides the type of the function.
    funcs: Vec<(u32, Rc<FuncType>)>,

    /// All tables available to this module, sorted by their index. The list
    /// entry is the type of each table.
    tables: Vec<TableType>,

    /// All globals available to this module, sorted by their index. The list
    /// entry is the type of each global.
    globals: Vec<GlobalType>,

    /// All memories available to this module, sorted by their index. The list
    /// entry is the type of each memory.
    memories: Vec<MemoryType>,

    exports: Vec<(String, ExportKind, u32)>,
    start: Option<u32>,
    elems: Vec<ElementSegment>,
    code: Vec<Code>,
    data: Vec<DataSegment>,

    /// The predicted size of the effective type of this module, based on this
    /// module's size of the types of imports/exports.
    type_size: u32,

    /// Names currently exported from this module.
    export_names: HashSet<String>,

    /// Reusable buffer in `self.arbitrary_const_expr` to amortize the cost of
    /// allocation.
    const_expr_choices: Vec<Box<dyn Fn(&mut Unstructured, ValType) -> Result<ConstExpr>>>,

    /// What the maximum type index that can be referenced is.
    max_type_limit: MaxTypeLimit,

    /// Some known-interesting values, such as powers of two, values just before
    /// or just after a memory size, etc...
    interesting_values32: Vec<u32>,
    interesting_values64: Vec<u64>,
}

impl<'a> Arbitrary<'a> for Module {
    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
        Module::new(Config::default(), u)
    }
}

impl fmt::Debug for Module {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Module")
            .field("config", &self.config)
            .field(&"...", &"...")
            .finish()
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum DuplicateImportsBehavior {
    Allowed,
    Disallowed,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum AllowEmptyRecGroup {
    Yes,
    No,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum MaxTypeLimit {
    ModuleTypes,
    Num(u32),
}

impl Module {
    /// Returns a reference to the internal configuration.
    pub fn config(&self) -> &Config {
        &self.config
    }

    /// Creates a new `Module` with the specified `config` for
    /// configuration and `Unstructured` for the DNA of this module.
    pub fn new(config: Config, u: &mut Unstructured<'_>) -> Result<Self> {
        Self::new_internal(config, u, DuplicateImportsBehavior::Allowed)
    }

    pub(crate) fn new_internal(
        config: Config,
        u: &mut Unstructured<'_>,
        duplicate_imports_behavior: DuplicateImportsBehavior,
    ) -> Result<Self> {
        let mut module = Module::empty(config, duplicate_imports_behavior);
        module.build(u)?;
        Ok(module)
    }

    fn empty(mut config: Config, duplicate_imports_behavior: DuplicateImportsBehavior) -> Self {
        config.sanitize();
        Module {
            config,
            duplicate_imports_behavior,
            valtypes: Vec::new(),
            types: Vec::new(),
            rec_groups: Vec::new(),
            can_subtype: Vec::new(),
            super_to_sub_types: HashMap::new(),
            should_encode_types: false,
            imports: Vec::new(),
            should_encode_imports: false,
            array_types: Vec::new(),
            func_types: Vec::new(),
            struct_types: Vec::new(),
            num_imports: 0,
            num_defined_tags: 0,
            num_defined_funcs: 0,
            defined_tables: Vec::new(),
            num_defined_memories: 0,
            defined_globals: Vec::new(),
            tags: Vec::new(),
            funcs: Vec::new(),
            tables: Vec::new(),
            globals: Vec::new(),
            memories: Vec::new(),
            exports: Vec::new(),
            start: None,
            elems: Vec::new(),
            code: Vec::new(),
            data: Vec::new(),
            type_size: 0,
            export_names: HashSet::new(),
            const_expr_choices: Vec::new(),
            max_type_limit: MaxTypeLimit::ModuleTypes,
            interesting_values32: Vec::new(),
            interesting_values64: Vec::new(),
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) struct SubType {
    pub(crate) is_final: bool,
    pub(crate) supertype: Option<u32>,
    pub(crate) composite_type: CompositeType,
}

impl SubType {
    fn unwrap_struct(&self) -> &StructType {
        self.composite_type.unwrap_struct()
    }

    fn unwrap_func(&self) -> &Rc<FuncType> {
        self.composite_type.unwrap_func()
    }

    fn unwrap_array(&self) -> &ArrayType {
        self.composite_type.unwrap_array()
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) struct CompositeType {
    pub inner: CompositeInnerType,
    pub shared: bool,
}

impl CompositeType {
    #[cfg(any(feature = "component-model", feature = "wasmparser"))]
    pub(crate) fn new_func(func: Rc<FuncType>, shared: bool) -> Self {
        Self {
            inner: CompositeInnerType::Func(func),
            shared,
        }
    }

    fn unwrap_func(&self) -> &Rc<FuncType> {
        match &self.inner {
            CompositeInnerType::Func(f) => f,
            _ => panic!("not a func"),
        }
    }

    fn unwrap_array(&self) -> &ArrayType {
        match &self.inner {
            CompositeInnerType::Array(a) => a,
            _ => panic!("not an array"),
        }
    }

    fn unwrap_struct(&self) -> &StructType {
        match &self.inner {
            CompositeInnerType::Struct(s) => s,
            _ => panic!("not a struct"),
        }
    }
}

impl From<&CompositeType> for wasm_encoder::CompositeType {
    fn from(ty: &CompositeType) -> Self {
        let inner = match &ty.inner {
            CompositeInnerType::Array(a) => wasm_encoder::CompositeInnerType::Array(*a),
            CompositeInnerType::Func(f) => wasm_encoder::CompositeInnerType::Func(
                wasm_encoder::FuncType::new(f.params.iter().cloned(), f.results.iter().cloned()),
            ),
            CompositeInnerType::Struct(s) => wasm_encoder::CompositeInnerType::Struct(s.clone()),
        };
        wasm_encoder::CompositeType {
            shared: ty.shared,
            inner,
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) enum CompositeInnerType {
    Array(ArrayType),
    Func(Rc<FuncType>),
    Struct(StructType),
}

/// A function signature.
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub(crate) struct FuncType {
    /// Types of the parameter values.
    pub(crate) params: Vec<ValType>,
    /// Types of the result values.
    pub(crate) results: Vec<ValType>,
}

/// An import of an entity provided externally or by a component.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) struct Import {
    /// The name of the module providing this entity.
    pub(crate) module: String,
    /// The name of the entity.
    pub(crate) field: String,
    /// The type of this entity.
    pub(crate) entity_type: EntityType,
}

/// Type of an entity.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) enum EntityType {
    /// A global entity.
    Global(GlobalType),
    /// A table entity.
    Table(TableType),
    /// A memory entity.
    Memory(MemoryType),
    /// A tag entity.
    Tag(TagType),
    /// A function entity.
    Func(u32, Rc<FuncType>),
}

/// Type of a tag.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) struct TagType {
    /// Index of the function type.
    func_type_idx: u32,
    /// Type of the function.
    func_type: Rc<FuncType>,
}

#[derive(Debug)]
struct ElementSegment {
    kind: ElementKind,
    ty: RefType,
    items: Elements,
}

#[derive(Debug)]
enum ElementKind {
    Passive,
    Declared,
    Active {
        table: Option<u32>, // None == table 0 implicitly
        offset: Offset,
    },
}

#[derive(Debug)]
enum Elements {
    Functions(Vec<u32>),
    Expressions(Vec<ConstExpr>),
}

#[derive(Debug)]
struct Code {
    locals: Vec<ValType>,
    instructions: Instructions,
}

#[derive(Debug)]
enum Instructions {
    Generated(Vec<Instruction>),
    Arbitrary(Vec<u8>),
}

#[derive(Debug)]
struct DataSegment {
    kind: DataSegmentKind,
    init: Vec<u8>,
}

#[derive(Debug)]
enum DataSegmentKind {
    Passive,
    Active { memory_index: u32, offset: Offset },
}

#[derive(Debug)]
pub(crate) enum Offset {
    Const32(i32),
    Const64(i64),
    Global(u32),
}

impl Module {
    fn build(&mut self, u: &mut Unstructured) -> Result<()> {
        self.valtypes = configured_valtypes(&self.config);

        // We attempt to figure out our available imports *before* creating the types section here,
        // because the types for the imports are already well-known (specified by the user) and we
        // must have those populated for all function/etc. imports, no matter what.
        //
        // This can affect the available capacity for types and such.
        if self.arbitrary_imports_from_available(u)? {
            self.arbitrary_types(u)?;
        } else {
            self.arbitrary_types(u)?;
            self.arbitrary_imports(u)?;
        }

        self.should_encode_imports = !self.imports.is_empty() || u.arbitrary()?;

        self.arbitrary_tags(u)?;
        self.arbitrary_funcs(u)?;
        self.arbitrary_tables(u)?;
        self.arbitrary_memories(u)?;
        self.arbitrary_globals(u)?;
        if !self.required_exports(u)? {
            self.arbitrary_exports(u)?;
        };
        self.should_encode_types = !self.types.is_empty() || u.arbitrary()?;
        self.arbitrary_start(u)?;
        self.arbitrary_elems(u)?;
        self.arbitrary_data(u)?;
        self.arbitrary_code(u)?;
        Ok(())
    }

    #[inline]
    fn val_type_is_sub_type(&self, a: ValType, b: ValType) -> bool {
        match (a, b) {
            (a, b) if a == b => true,
            (ValType::Ref(a), ValType::Ref(b)) => self.ref_type_is_sub_type(a, b),
            _ => false,
        }
    }

    /// Is `a` a subtype of `b`?
    fn ref_type_is_sub_type(&self, a: RefType, b: RefType) -> bool {
        if a == b {
            return true;
        }

        if a.nullable && !b.nullable {
            return false;
        }

        self.heap_type_is_sub_type(a.heap_type, b.heap_type)
    }

    fn heap_type_is_sub_type(&self, a: HeapType, b: HeapType) -> bool {
        use AbstractHeapType::*;
        use CompositeInnerType as CT;
        use HeapType as HT;
        match (a, b) {
            (a, b) if a == b => true,

            (
                HT::Abstract {
                    shared: a_shared,
                    ty: a_ty,
                },
                HT::Abstract {
                    shared: b_shared,
                    ty: b_ty,
                },
            ) => {
                a_shared == b_shared
                    && match (a_ty, b_ty) {
                        (Eq | I31 | Struct | Array | None, Any) => true,
                        (I31 | Struct | Array | None, Eq) => true,
                        (NoExtern, Extern) => true,
                        (NoFunc, Func) => true,
                        (None, I31 | Array | Struct) => true,
                        (NoExn, Exn) => true,
                        _ => false,
                    }
            }

            (HT::Concrete(a), HT::Abstract { shared, ty }) => {
                let a_ty = &self.ty(a).composite_type;
                if a_ty.shared == shared {
                    return false;
                }
                match ty {
                    Eq | Any => matches!(a_ty.inner, CT::Array(_) | CT::Struct(_)),
                    Struct => matches!(a_ty.inner, CT::Struct(_)),
                    Array => matches!(a_ty.inner, CT::Array(_)),
                    Func => matches!(a_ty.inner, CT::Func(_)),
                    _ => false,
                }
            }

            (HT::Abstract { shared, ty }, HT::Concrete(b)) => {
                let b_ty = &self.ty(b).composite_type;
                if shared == b_ty.shared {
                    return false;
                }
                match ty {
                    None => matches!(b_ty.inner, CT::Array(_) | CT::Struct(_)),
                    NoFunc => matches!(b_ty.inner, CT::Func(_)),
                    _ => false,
                }
            }

            (HT::Concrete(mut a), HT::Concrete(b)) => loop {
                if a == b {
                    return true;
                }
                if let Some(supertype) = self.ty(a).supertype {
                    a = supertype;
                } else {
                    return false;
                }
            },
        }
    }

    fn arbitrary_types(&mut self, u: &mut Unstructured) -> Result<()> {
        assert!(self.config.min_types <= self.config.max_types);
        while self.types.len() < self.config.min_types {
            self.arbitrary_rec_group(u, AllowEmptyRecGroup::No)?;
        }
        while self.types.len() < self.config.max_types {
            let keep_going = u.arbitrary().unwrap_or(false);
            if !keep_going {
                break;
            }
            self.arbitrary_rec_group(u, AllowEmptyRecGroup::Yes)?;
        }
        Ok(())
    }

    fn add_type(&mut self, ty: SubType) -> u32 {
        let index = u32::try_from(self.types.len()).unwrap();

        if let Some(supertype) = ty.supertype {
            self.super_to_sub_types
                .entry(supertype)
                .or_default()
                .push(index);
        }

        let list = match &ty.composite_type.inner {
            CompositeInnerType::Array(_) => &mut self.array_types,
            CompositeInnerType::Func(_) => &mut self.func_types,
            CompositeInnerType::Struct(_) => &mut self.struct_types,
        };
        list.push(index);

        if !ty.is_final {
            self.can_subtype.push(index);
        }

        self.types.push(ty);
        index
    }

    fn arbitrary_rec_group(
        &mut self,
        u: &mut Unstructured,
        kind: AllowEmptyRecGroup,
    ) -> Result<()> {
        let rec_group_start = self.types.len();

        assert!(matches!(self.max_type_limit, MaxTypeLimit::ModuleTypes));

        if self.config.gc_enabled {
            // With small probability, clone an existing rec group.
            if self.clonable_rec_groups(kind).next().is_some() && u.ratio(1, u8::MAX)? {
                return self.clone_rec_group(u, kind);
            }

            // Otherwise, create a new rec group with multiple types inside.
            let max_rec_group_size = self.config.max_types - self.types.len();
            let min_rec_group_size = match kind {
                AllowEmptyRecGroup::Yes => 0,
                AllowEmptyRecGroup::No => 1,
            };
            let rec_group_size = u.int_in_range(min_rec_group_size..=max_rec_group_size)?;
            let type_ref_limit = u32::try_from(self.types.len() + rec_group_size).unwrap();
            self.max_type_limit = MaxTypeLimit::Num(type_ref_limit);
            for _ in 0..rec_group_size {
                let ty = self.arbitrary_sub_type(u)?;
                self.add_type(ty);
            }
        } else {
            let type_ref_limit = u32::try_from(self.types.len()).unwrap();
            self.max_type_limit = MaxTypeLimit::Num(type_ref_limit);
            let ty = self.arbitrary_sub_type(u)?;
            self.add_type(ty);
        }

        self.max_type_limit = MaxTypeLimit::ModuleTypes;

        self.rec_groups.push(rec_group_start..self.types.len());
        Ok(())
    }

    /// Returns an iterator of rec groups that we could currently clone while
    /// still staying within the max types limit.
    fn clonable_rec_groups(
        &self,
        kind: AllowEmptyRecGroup,
    ) -> impl Iterator<Item = Range<usize>> + '_ {
        self.rec_groups
            .iter()
            .filter(move |r| {
                match kind {
                    AllowEmptyRecGroup::Yes => {}
                    AllowEmptyRecGroup::No => {
                        if r.is_empty() {
                            return false;
                        }
                    }
                }
                r.end - r.start <= self.config.max_types.saturating_sub(self.types.len())
            })
            .cloned()
    }

    fn clone_rec_group(&mut self, u: &mut Unstructured, kind: AllowEmptyRecGroup) -> Result<()> {
        // NB: this does *not* guarantee that the cloned rec group will
        // canonicalize the same as the original rec group and be
        // deduplicated. That would reqiure a second pass over the cloned types
        // to rewrite references within the original rec group to be references
        // into the new rec group. That might make sense to do one day, but for
        // now we don't do it. That also means that we can't mark the new types
        // as "subtypes" of the old types and vice versa.
        let candidates: Vec<_> = self.clonable_rec_groups(kind).collect();
        let group = u.choose(&candidates)?.clone();
        let new_rec_group_start = self.types.len();
        for index in group {
            let orig_ty_index = u32::try_from(index).unwrap();
            let ty = self.ty(orig_ty_index).clone();
            self.add_type(ty);
        }
        self.rec_groups.push(new_rec_group_start..self.types.len());
        Ok(())
    }

    fn arbitrary_sub_type(&mut self, u: &mut Unstructured) -> Result<SubType> {
        if !self.config.gc_enabled {
            let composite_type = CompositeType {
                inner: CompositeInnerType::Func(self.arbitrary_func_type(u)?),
                shared: false,
            };
            return Ok(SubType {
                is_final: true,
                supertype: None,
                composite_type,
            });
        }

        if !self.can_subtype.is_empty() && u.ratio(1, 32_u8)? {
            self.arbitrary_sub_type_of_super_type(u)
        } else {
            Ok(SubType {
                is_final: u.arbitrary()?,
                supertype: None,
                composite_type: self.arbitrary_composite_type(u)?,
            })
        }
    }

    fn arbitrary_sub_type_of_super_type(&mut self, u: &mut Unstructured) -> Result<SubType> {
        let supertype = *u.choose(&self.can_subtype)?;
        let mut composite_type = self.types[usize::try_from(supertype).unwrap()]
            .composite_type
            .clone();
        match &mut composite_type.inner {
            CompositeInnerType::Array(a) => {
                a.0 = self.arbitrary_matching_field_type(u, a.0)?;
            }
            CompositeInnerType::Func(f) => {
                *f = self.arbitrary_matching_func_type(u, f)?;
            }
            CompositeInnerType::Struct(s) => {
                *s = self.arbitrary_matching_struct_type(u, s)?;
            }
        }
        Ok(SubType {
            is_final: u.arbitrary()?,
            supertype: Some(supertype),
            composite_type,
        })
    }

    fn arbitrary_matching_struct_type(
        &mut self,
        u: &mut Unstructured,
        ty: &StructType,
    ) -> Result<StructType> {
        let len_extra_fields = u.int_in_range(0..=5)?;
        let mut fields = Vec::with_capacity(ty.fields.len() + len_extra_fields);
        for field in ty.fields.iter() {
            fields.push(self.arbitrary_matching_field_type(u, *field)?);
        }
        for _ in 0..len_extra_fields {
            fields.push(self.arbitrary_field_type(u)?);
        }
        Ok(StructType {
            fields: fields.into_boxed_slice(),
        })
    }

    fn arbitrary_matching_field_type(
        &mut self,
        u: &mut Unstructured,
        ty: FieldType,
    ) -> Result<FieldType> {
        Ok(FieldType {
            element_type: self.arbitrary_matching_storage_type(u, ty.element_type)?,
            mutable: if ty.mutable { u.arbitrary()? } else { false },
        })
    }

    fn arbitrary_matching_storage_type(
        &mut self,
        u: &mut Unstructured,
        ty: StorageType,
    ) -> Result<StorageType> {
        match ty {
            StorageType::I8 => Ok(StorageType::I8),
            StorageType::I16 => Ok(StorageType::I16),
            StorageType::Val(ty) => Ok(StorageType::Val(self.arbitrary_matching_val_type(u, ty)?)),
        }
    }

    fn arbitrary_matching_val_type(
        &mut self,
        u: &mut Unstructured,
        ty: ValType,
    ) -> Result<ValType> {
        match ty {
            ValType::I32 => Ok(ValType::I32),
            ValType::I64 => Ok(ValType::I64),
            ValType::F32 => Ok(ValType::F32),
            ValType::F64 => Ok(ValType::F64),
            ValType::V128 => Ok(ValType::V128),
            ValType::Ref(ty) => Ok(ValType::Ref(self.arbitrary_matching_ref_type(u, ty)?)),
        }
    }

    fn arbitrary_matching_ref_type(&self, u: &mut Unstructured, ty: RefType) -> Result<RefType> {
        Ok(RefType {
            nullable: ty.nullable,
            heap_type: self.arbitrary_matching_heap_type(u, ty.heap_type)?,
        })
    }

    fn arbitrary_matching_heap_type(&self, u: &mut Unstructured, ty: HeapType) -> Result<HeapType> {
        if !self.config.gc_enabled {
            return Ok(ty);
        }
        use CompositeInnerType as CT;
        use HeapType as HT;
        let mut choices = vec![ty];
        match ty {
            HT::Abstract { shared, ty } => {
                use AbstractHeapType::*;
                let ht = |ty| HT::Abstract { shared, ty };
                match ty {
                    Any => {
                        choices.extend([ht(Eq), ht(Struct), ht(Array), ht(I31), ht(None)]);
                        choices.extend(self.array_types.iter().copied().map(HT::Concrete));
                        choices.extend(self.struct_types.iter().copied().map(HT::Concrete));
                    }
                    Eq => {
                        choices.extend([ht(Struct), ht(Array), ht(I31), ht(None)]);
                        choices.extend(self.array_types.iter().copied().map(HT::Concrete));
                        choices.extend(self.struct_types.iter().copied().map(HT::Concrete));
                    }
                    Struct => {
                        choices.extend([ht(Struct), ht(None)]);
                        choices.extend(self.struct_types.iter().copied().map(HT::Concrete));
                    }
                    Array => {
                        choices.extend([ht(Array), ht(None)]);
                        choices.extend(self.array_types.iter().copied().map(HT::Concrete));
                    }
                    I31 => {
                        choices.push(ht(None));
                    }
                    Func => {
                        choices.extend(self.func_types.iter().copied().map(HT::Concrete));
                        choices.push(ht(NoFunc));
                    }
                    Extern => {
                        choices.push(ht(NoExtern));
                    }
                    Exn | NoExn | None | NoExtern | NoFunc | Cont | NoCont => {}
                }
            }
            HT::Concrete(idx) => {
                if let Some(subs) = self.super_to_sub_types.get(&idx) {
                    choices.extend(subs.iter().copied().map(HT::Concrete));
                }
                match self
                    .types
                    .get(usize::try_from(idx).unwrap())
                    .map(|ty| (ty.composite_type.shared, &ty.composite_type.inner))
                {
                    Some((shared, CT::Array(_) | CT::Struct(_))) => choices.push(HT::Abstract {
                        shared,
                        ty: AbstractHeapType::None,
                    }),
                    Some((shared, CT::Func(_))) => choices.push(HT::Abstract {
                        shared,
                        ty: AbstractHeapType::NoFunc,
                    }),
                    None => {
                        // The referenced type might be part of this same rec
                        // group we are currently generating, but not generated
                        // yet. In this case, leave `choices` as it is, and we
                        // will just end up choosing the original type again
                        // down below, which is fine.
                    }
                }
            }
        }
        Ok(*u.choose(&choices)?)
    }

    fn arbitrary_matching_func_type(
        &mut self,
        u: &mut Unstructured,
        ty: &FuncType,
    ) -> Result<Rc<FuncType>> {
        // Note: parameters are contravariant, results are covariant. See
        // https://github.com/bytecodealliance/wasm-tools/blob/0616ef196a183cf137ee06b4a5993b7d590088bf/crates/wasmparser/src/readers/core/types/matches.rs#L137-L174
        // for details.
        let mut params = Vec::with_capacity(ty.params.len());
        for param in &ty.params {
            params.push(self.arbitrary_super_type_of_val_type(u, *param)?);
        }
        let mut results = Vec::with_capacity(ty.results.len());
        for result in &ty.results {
            results.push(self.arbitrary_matching_val_type(u, *result)?);
        }
        Ok(Rc::new(FuncType { params, results }))
    }

    fn arbitrary_super_type_of_val_type(
        &mut self,
        u: &mut Unstructured,
        ty: ValType,
    ) -> Result<ValType> {
        match ty {
            ValType::I32 => Ok(ValType::I32),
            ValType::I64 => Ok(ValType::I64),
            ValType::F32 => Ok(ValType::F32),
            ValType::F64 => Ok(ValType::F64),
            ValType::V128 => Ok(ValType::V128),
            ValType::Ref(ty) => Ok(ValType::Ref(self.arbitrary_super_type_of_ref_type(u, ty)?)),
        }
    }

    fn arbitrary_super_type_of_ref_type(
        &self,
        u: &mut Unstructured,
        ty: RefType,
    ) -> Result<RefType> {
        Ok(RefType {
            // TODO: For now, only create allow nullable reference
            // types. Eventually we should support non-nullable reference types,
            // but this means that we will also need to recognize when it is
            // impossible to create an instance of the reference (eg `(ref
            // nofunc)` has no instances, and self-referential types that
            // contain a non-null self-reference are also impossible to create).
            nullable: true,
            heap_type: self.arbitrary_super_type_of_heap_type(u, ty.heap_type)?,
        })
    }

    fn arbitrary_super_type_of_heap_type(
        &self,
        u: &mut Unstructured,
        ty: HeapType,
    ) -> Result<HeapType> {
        if !self.config.gc_enabled {
            return Ok(ty);
        }
        use CompositeInnerType as CT;
        use HeapType as HT;
        let mut choices = vec![ty];
        match ty {
            HT::Abstract { shared, ty } => {
                use AbstractHeapType::*;
                let ht = |ty| HT::Abstract { shared, ty };
                match ty {
                    None => {
                        choices.extend([ht(Any), ht(Eq), ht(Struct), ht(Array), ht(I31)]);
                        choices.extend(self.array_types.iter().copied().map(HT::Concrete));
                        choices.extend(self.struct_types.iter().copied().map(HT::Concrete));
                    }
                    NoExtern => {
                        choices.push(ht(Extern));
                    }
                    NoFunc => {
                        choices.extend(self.func_types.iter().copied().map(HT::Concrete));
                        choices.push(ht(Func));
                    }
                    NoExn => {
                        choices.push(ht(Exn));
                    }
                    Struct | Array | I31 => {
                        choices.extend([ht(Any), ht(Eq)]);
                    }
                    Eq => {
                        choices.push(ht(Any));
                    }
                    NoCont => {
                        choices.push(ht(Cont));
                    }
                    Exn | Any | Func | Extern | Cont => {}
                }
            }
            HT::Concrete(mut idx) => {
                if let Some(sub_ty) = &self.types.get(usize::try_from(idx).unwrap()) {
                    let ht = |ty| HT::Abstract {
                        shared: sub_ty.composite_type.shared,
                        ty,
                    };
                    match &sub_ty.composite_type.inner {
                        CT::Array(_) => {
                            choices.extend([
                                ht(AbstractHeapType::Any),
                                ht(AbstractHeapType::Eq),
                                ht(AbstractHeapType::Array),
                            ]);
                        }
                        CT::Func(_) => {
                            choices.push(ht(AbstractHeapType::Func));
                        }
                        CT::Struct(_) => {
                            choices.extend([
                                ht(AbstractHeapType::Any),
                                ht(AbstractHeapType::Eq),
                                ht(AbstractHeapType::Struct),
                            ]);
                        }
                    }
                } else {
                    // Same as in `arbitrary_matching_heap_type`: this was a
                    // forward reference to a concrete type that is part of
                    // this same rec group we are generating right now, and
                    // therefore we haven't generated that type yet. Just
                    // leave `choices` as it is and we will choose the
                    // original type again down below.
                }
                while let Some(supertype) = self
                    .types
                    .get(usize::try_from(idx).unwrap())
                    .and_then(|ty| ty.supertype)
                {
                    choices.push(HT::Concrete(supertype));
                    idx = supertype;
                }
            }
        }
        Ok(*u.choose(&choices)?)
    }

    fn arbitrary_composite_type(&mut self, u: &mut Unstructured) -> Result<CompositeType> {
        use CompositeInnerType as CT;
        let shared = false; // TODO: handle shared
        if !self.config.gc_enabled {
            return Ok(CompositeType {
                shared,
                inner: CT::Func(self.arbitrary_func_type(u)?),
            });
        }

        match u.int_in_range(0..=2)? {
            0 => Ok(CompositeType {
                shared,
                inner: CT::Array(ArrayType(self.arbitrary_field_type(u)?)),
            }),
            1 => Ok(CompositeType {
                shared,
                inner: CT::Func(self.arbitrary_func_type(u)?),
            }),
            2 => Ok(CompositeType {
                shared,
                inner: CT::Struct(self.arbitrary_struct_type(u)?),
            }),
            _ => unreachable!(),
        }
    }

    fn arbitrary_struct_type(&mut self, u: &mut Unstructured) -> Result<StructType> {
        let len = u.int_in_range(0..=20)?;
        let mut fields = Vec::with_capacity(len);
        for _ in 0..len {
            fields.push(self.arbitrary_field_type(u)?);
        }
        Ok(StructType {
            fields: fields.into_boxed_slice(),
        })
    }

    fn arbitrary_field_type(&mut self, u: &mut Unstructured) -> Result<FieldType> {
        Ok(FieldType {
            element_type: self.arbitrary_storage_type(u)?,
            mutable: u.arbitrary()?,
        })
    }

    fn arbitrary_storage_type(&mut self, u: &mut Unstructured) -> Result<StorageType> {
        match u.int_in_range(0..=2)? {
            0 => Ok(StorageType::I8),
            1 => Ok(StorageType::I16),
            2 => Ok(StorageType::Val(self.arbitrary_valtype(u)?)),
            _ => unreachable!(),
        }
    }

    fn arbitrary_ref_type(&self, u: &mut Unstructured) -> Result<RefType> {
        if !self.config.reference_types_enabled {
            return Ok(RefType::FUNCREF);
        }
        Ok(RefType {
            nullable: true,
            heap_type: self.arbitrary_heap_type(u)?,
        })
    }

    fn arbitrary_heap_type(&self, u: &mut Unstructured) -> Result<HeapType> {
        assert!(self.config.reference_types_enabled);

        let concrete_type_limit = match self.max_type_limit {
            MaxTypeLimit::Num(n) => n,
            MaxTypeLimit::ModuleTypes => u32::try_from(self.types.len()).unwrap(),
        };

        if self.config.gc_enabled && concrete_type_limit > 0 && u.arbitrary()? {
            let idx = u.int_in_range(0..=concrete_type_limit - 1)?;
            return Ok(HeapType::Concrete(idx));
        }

        use AbstractHeapType::*;
        let mut choices = vec![Func, Extern];
        if self.config.exceptions_enabled {
            choices.push(Exn);
        }
        if self.config.gc_enabled {
            choices.extend(
                [Any, None, NoExtern, NoFunc, Eq, Struct, Array, I31]
                    .iter()
                    .copied(),
            );
        }

        Ok(HeapType::Abstract {
            shared: false, // TODO: turn on shared attribute with shared-everything-threads.
            ty: *u.choose(&choices)?,
        })
    }

    fn arbitrary_func_type(&mut self, u: &mut Unstructured) -> Result<Rc<FuncType>> {
        let mut params = vec![];
        let mut results = vec![];
        let max_params = 20;
        arbitrary_loop(u, 0, max_params, |u| {
            params.push(self.arbitrary_valtype(u)?);
            Ok(true)
        })?;
        let max_results = if self.config.multi_value_enabled {
            max_params
        } else {
            1
        };
        arbitrary_loop(u, 0, max_results, |u| {
            results.push(self.arbitrary_valtype(u)?);
            Ok(true)
        })?;
        Ok(Rc::new(FuncType { params, results }))
    }

    fn can_add_local_or_import_tag(&self) -> bool {
        self.config.exceptions_enabled
            && self.has_tag_func_types()
            && self.tags.len() < self.config.max_tags
    }

    fn can_add_local_or_import_func(&self) -> bool {
        !self.func_types.is_empty() && self.funcs.len() < self.config.max_funcs
    }

    fn can_add_local_or_import_table(&self) -> bool {
        self.tables.len() < self.config.max_tables
    }

    fn can_add_local_or_import_global(&self) -> bool {
        self.globals.len() < self.config.max_globals
    }

    fn can_add_local_or_import_memory(&self) -> bool {
        self.memories.len() < self.config.max_memories
    }

    fn arbitrary_imports(&mut self, u: &mut Unstructured) -> Result<()> {
        if self.config.max_type_size < self.type_size {
            return Ok(());
        }

        let mut import_strings = HashSet::new();
        let mut choices: Vec<fn(&mut Unstructured, &mut Module) -> Result<EntityType>> =
            Vec::with_capacity(5);
        let min = self.config.min_imports.saturating_sub(self.num_imports);
        let max = self.config.max_imports.saturating_sub(self.num_imports);
        arbitrary_loop(u, min, max, |u| {
            choices.clear();
            if self.can_add_local_or_import_tag() {
                choices.push(|u, m| {
                    let ty = m.arbitrary_tag_type(u)?;
                    Ok(EntityType::Tag(ty))
                });
            }
            if self.can_add_local_or_import_func() {
                choices.push(|u, m| {
                    let idx = *u.choose(&m.func_types)?;
                    let ty = m.func_type(idx).clone();
                    Ok(EntityType::Func(idx, ty))
                });
            }
            if self.can_add_local_or_import_global() {
                choices.push(|u, m| {
                    let ty = m.arbitrary_global_type(u)?;
                    Ok(EntityType::Global(ty))
                });
            }
            if self.can_add_local_or_import_memory() {
                choices.push(|u, m| {
                    let ty = arbitrary_memtype(u, m.config())?;
                    Ok(EntityType::Memory(ty))
                });
            }
            if self.can_add_local_or_import_table() {
                choices.push(|u, m| {
                    let ty = arbitrary_table_type(u, m.config(), Some(m))?;
                    Ok(EntityType::Table(ty))
                });
            }

            if choices.is_empty() {
                // We are out of choices. If we have not have reached the
                // minimum yet, then we have no way to satisfy the constraint,
                // but we follow max-constraints before the min-import
                // constraint.
                return Ok(false);
            }

            // Generate a type to import, but only actually add the item if the
            // type size budget allows us to.
            let f = u.choose(&choices)?;
            let entity_type = f(u, self)?;
            let budget = self.config.max_type_size - self.type_size;
            if entity_type.size() + 1 > budget {
                return Ok(false);
            }
            self.type_size += entity_type.size() + 1;

            // Generate an arbitrary module/name pair to name this import.
            let mut import_pair = unique_import_strings(1_000, u)?;
            if self.duplicate_imports_behavior == DuplicateImportsBehavior::Disallowed {
                while import_strings.contains(&import_pair) {
                    use std::fmt::Write;
                    write!(&mut import_pair.1, "{}", import_strings.len()).unwrap();
                }
                import_strings.insert(import_pair.clone());
            }
            let (module, field) = import_pair;

            // Once our name is determined, then we push the typed item into the
            // appropriate namespace.
            match &entity_type {
                EntityType::Tag(ty) => self.tags.push(ty.clone()),
                EntityType::Func(idx, ty) => self.funcs.push((*idx, ty.clone())),
                EntityType::Global(ty) => self.globals.push(*ty),
                EntityType::Table(ty) => self.tables.push(*ty),
                EntityType::Memory(ty) => self.memories.push(*ty),
            }

            self.num_imports += 1;
            self.imports.push(Import {
                module,
                field,
                entity_type,
            });
            Ok(true)
        })?;

        Ok(())
    }

    /// Generate some arbitrary imports from the list of available imports.
    ///
    /// Returns `true` if there was a list of available imports
    /// configured. Otherwise `false` and the caller should generate arbitrary
    /// imports.
    fn arbitrary_imports_from_available(&mut self, u: &mut Unstructured) -> Result<bool> {
        let example_module = if let Some(wasm) = self.config.available_imports.take() {
            wasm
        } else {
            return Ok(false);
        };

        #[cfg(feature = "wasmparser")]
        {
            self._arbitrary_imports_from_available(u, &example_module)?;
            Ok(true)
        }
        #[cfg(not(feature = "wasmparser"))]
        {
            let _ = (example_module, u);
            panic!("support for `available_imports` was disabled at compile time");
        }
    }

    #[cfg(feature = "wasmparser")]
    fn _arbitrary_imports_from_available(
        &mut self,
        u: &mut Unstructured,
        example_module: &[u8],
    ) -> Result<()> {
        // First, parse the module-by-example to collect the types and imports.
        //
        // `available_types` will map from a signature index (which is the same as the index into
        // this vector) as it appears in the parsed code, to the type itself as well as to the
        // index in our newly generated module. Initially the option is `None` and will become a
        // `Some` when we encounter an import that uses this signature in the next portion of this
        // function. See also the `make_func_type` closure below.
        let mut available_types = Vec::new();
        let mut available_imports = Vec::<wasmparser::Import>::new();
        for payload in wasmparser::Parser::new(0).parse_all(&example_module) {
            match payload.expect("could not parse the available import payload") {
                wasmparser::Payload::TypeSection(type_reader) => {
                    for ty in type_reader.into_iter_err_on_gc_types() {
                        let ty = ty.expect("could not parse type section");
                        available_types.push((ty, None));
                    }
                }
                wasmparser::Payload::ImportSection(import_reader) => {
                    for im in import_reader {
                        let im = im.expect("could not read import");
                        // We can immediately filter whether this is an import we want to
                        // use.
                        let use_import = u.arbitrary().unwrap_or(false);
                        if !use_import {
                            continue;
                        }
                        available_imports.push(im);
                    }
                }
                _ => {}
            }
        }

        // In this function we need to place imported function/tag types in the types section and
        // generate import entries (which refer to said types) at the same time.
        let max_types = self.config.max_types;
        let multi_value_enabled = self.config.multi_value_enabled;
        let mut new_imports = Vec::with_capacity(available_imports.len());
        let first_type_index = self.types.len();
        let mut new_types = Vec::<SubType>::new();

        // Returns the index to the translated type in the to-be type section, and the reference to
        // the type itself.
        let mut make_func_type = |parsed_sig_idx: u32| {
            let serialized_sig_idx = match available_types.get_mut(parsed_sig_idx as usize) {
                None => panic!("signature index refers to a type out of bounds"),
                Some((_, Some(idx))) => *idx as usize,
                Some((func_type, index_store)) => {
                    let multi_value_required = func_type.results().len() > 1;
                    let new_index = first_type_index + new_types.len();
                    if new_index >= max_types || (multi_value_required && !multi_value_enabled) {
                        return None;
                    }
                    let func_type = Rc::new(FuncType {
                        params: func_type
                            .params()
                            .iter()
                            .map(|t| (*t).try_into().unwrap())
                            .collect(),
                        results: func_type
                            .results()
                            .iter()
                            .map(|t| (*t).try_into().unwrap())
                            .collect(),
                    });
                    index_store.replace(new_index as u32);
                    new_types.push(SubType {
                        is_final: true,
                        supertype: None,
                        composite_type: CompositeType::new_func(Rc::clone(&func_type), false), // TODO: handle shared
                    });
                    new_index
                }
            };
            match &new_types[serialized_sig_idx - first_type_index]
                .composite_type
                .inner
            {
                CompositeInnerType::Func(f) => Some((serialized_sig_idx as u32, Rc::clone(f))),
                _ => unimplemented!(),
            }
        };

        for import in available_imports {
            let type_size_budget = self.config.max_type_size - self.type_size;
            let entity_type = match &import.ty {
                wasmparser::TypeRef::Func(sig_idx) => {
                    if self.funcs.len() >= self.config.max_funcs {
                        continue;
                    } else if let Some((sig_idx, func_type)) = make_func_type(*sig_idx) {
                        let entity = EntityType::Func(sig_idx as u32, Rc::clone(&func_type));
                        if type_size_budget < entity.size() {
                            continue;
                        }
                        self.funcs.push((sig_idx, func_type));
                        entity
                    } else {
                        continue;
                    }
                }

                wasmparser::TypeRef::Tag(wasmparser::TagType { func_type_idx, .. }) => {
                    let can_add_tag = self.tags.len() < self.config.max_tags;
                    if !self.config.exceptions_enabled || !can_add_tag {
                        continue;
                    } else if let Some((sig_idx, func_type)) = make_func_type(*func_type_idx) {
                        let tag_type = TagType {
                            func_type_idx: sig_idx,
                            func_type,
                        };
                        let entity = EntityType::Tag(tag_type.clone());
                        if type_size_budget < entity.size() {
                            continue;
                        }
                        self.tags.push(tag_type);
                        entity
                    } else {
                        continue;
                    }
                }

                wasmparser::TypeRef::Table(table_ty) => {
                    let table_ty = TableType::try_from(*table_ty).unwrap();
                    let entity = EntityType::Table(table_ty);
                    let type_size = entity.size();
                    if type_size_budget < type_size || !self.can_add_local_or_import_table() {
                        continue;
                    }
                    self.type_size += type_size;
                    self.tables.push(table_ty);
                    entity
                }

                wasmparser::TypeRef::Memory(memory_ty) => {
                    let memory_ty = MemoryType::try_from(*memory_ty).unwrap();
                    let entity = EntityType::Memory(memory_ty);
                    let type_size = entity.size();
                    if type_size_budget < type_size || !self.can_add_local_or_import_memory() {
                        continue;
                    }
                    self.type_size += type_size;
                    self.memories.push(memory_ty);
                    entity
                }

                wasmparser::TypeRef::Global(global_ty) => {
                    let global_ty = (*global_ty).try_into().unwrap();
                    let entity = EntityType::Global(global_ty);
                    let type_size = entity.size();
                    if type_size_budget < type_size || !self.can_add_local_or_import_global() {
                        continue;
                    }
                    self.type_size += type_size;
                    self.globals.push(global_ty);
                    entity
                }
            };
            new_imports.push(Import {
                module: import.module.to_string(),
                field: import.name.to_string(),
                entity_type,
            });
            self.num_imports += 1;
        }

        // Finally, add the entities we just generated.
        for ty in new_types {
            self.rec_groups.push(self.types.len()..self.types.len() + 1);
            self.add_type(ty);
        }
        self.imports.extend(new_imports);

        Ok(())
    }

    fn type_of(&self, kind: ExportKind, index: u32) -> EntityType {
        match kind {
            ExportKind::Global => EntityType::Global(self.globals[index as usize]),
            ExportKind::Memory => EntityType::Memory(self.memories[index as usize]),
            ExportKind::Table => EntityType::Table(self.tables[index as usize]),
            ExportKind::Func => {
                let (_idx, ty) = &self.funcs[index as usize];
                EntityType::Func(u32::max_value(), ty.clone())
            }
            ExportKind::Tag => EntityType::Tag(self.tags[index as usize].clone()),
        }
    }

    fn ty(&self, idx: u32) -> &SubType {
        &self.types[idx as usize]
    }

    fn func_types(&self) -> impl Iterator<Item = (u32, &FuncType)> + '_ {
        self.func_types
            .iter()
            .copied()
            .map(move |type_i| (type_i, &**self.func_type(type_i)))
    }

    fn func_type(&self, idx: u32) -> &Rc<FuncType> {
        match &self.ty(idx).composite_type.inner {
            CompositeInnerType::Func(f) => f,
            _ => panic!("types[{idx}] is not a func type"),
        }
    }

    fn tags(&self) -> impl Iterator<Item = (u32, &TagType)> + '_ {
        self.tags
            .iter()
            .enumerate()
            .map(move |(i, ty)| (i as u32, ty))
    }

    fn funcs(&self) -> impl Iterator<Item = (u32, &Rc<FuncType>)> + '_ {
        self.funcs
            .iter()
            .enumerate()
            .map(move |(i, (_, ty))| (i as u32, ty))
    }

    fn has_tag_func_types(&self) -> bool {
        self.tag_func_types().next().is_some()
    }

    fn tag_func_types(&self) -> impl Iterator<Item = u32> + '_ {
        self.func_types
            .iter()
            .copied()
            .filter(move |i| self.func_type(*i).results.is_empty())
    }

    fn arbitrary_valtype(&self, u: &mut Unstructured) -> Result<ValType> {
        #[derive(PartialEq, Eq, PartialOrd, Ord)]
        enum ValTypeClass {
            I32,
            I64,
            F32,
            F64,
            V128,
            Ref,
        }

        let mut val_classes: Vec<_> = self
            .valtypes
            .iter()
            .map(|vt| match vt {
                ValType::I32 => ValTypeClass::I32,
                ValType::I64 => ValTypeClass::I64,
                ValType::F32 => ValTypeClass::F32,
                ValType::F64 => ValTypeClass::F64,
                ValType::V128 => ValTypeClass::V128,
                ValType::Ref(_) => ValTypeClass::Ref,
            })
            .collect();
        val_classes.sort_unstable();
        val_classes.dedup();

        match u.choose(&val_classes)? {
            ValTypeClass::I32 => Ok(ValType::I32),
            ValTypeClass::I64 => Ok(ValType::I64),
            ValTypeClass::F32 => Ok(ValType::F32),
            ValTypeClass::F64 => Ok(ValType::F64),
            ValTypeClass::V128 => Ok(ValType::V128),
            ValTypeClass::Ref => Ok(ValType::Ref(self.arbitrary_ref_type(u)?)),
        }
    }

    fn arbitrary_global_type(&self, u: &mut Unstructured) -> Result<GlobalType> {
        Ok(GlobalType {
            val_type: self.arbitrary_valtype(u)?,
            mutable: u.arbitrary()?,
            shared: false,
        })
    }

    fn arbitrary_tag_type(&self, u: &mut Unstructured) -> Result<TagType> {
        let candidate_func_types: Vec<_> = self.tag_func_types().collect();
        arbitrary_tag_type(u, &candidate_func_types, |ty_idx| {
            self.func_type(ty_idx).clone()
        })
    }

    fn arbitrary_tags(&mut self, u: &mut Unstructured) -> Result<()> {
        if !self.config.exceptions_enabled || !self.has_tag_func_types() {
            return Ok(());
        }

        arbitrary_loop(u, self.config.min_tags, self.config.max_tags, |u| {
            if !self.can_add_local_or_import_tag() {
                return Ok(false);
            }
            self.tags.push(self.arbitrary_tag_type(u)?);
            self.num_defined_tags += 1;
            Ok(true)
        })
    }

    fn arbitrary_funcs(&mut self, u: &mut Unstructured) -> Result<()> {
        if self.func_types.is_empty() {
            return Ok(());
        }

        arbitrary_loop(u, self.config.min_funcs, self.config.max_funcs, |u| {
            if !self.can_add_local_or_import_func() {
                return Ok(false);
            }
            let max = self.func_types.len() - 1;
            let ty = self.func_types[u.int_in_range(0..=max)?];
            self.funcs.push((ty, self.func_type(ty).clone()));
            self.num_defined_funcs += 1;
            Ok(true)
        })
    }

    fn arbitrary_tables(&mut self, u: &mut Unstructured) -> Result<()> {
        arbitrary_loop(
            u,
            self.config.min_tables as usize,
            self.config.max_tables as usize,
            |u| {
                if !self.can_add_local_or_import_table() {
                    return Ok(false);
                }
                let ty = arbitrary_table_type(u, self.config(), Some(self))?;
                let init = self.arbitrary_table_init(u, ty.element_type)?;
                self.defined_tables.push(init);
                self.tables.push(ty);
                Ok(true)
            },
        )
    }

    /// Generates an arbitrary table initialization expression for a table whose
    /// element type is `ty`.
    ///
    /// Table initialization expressions were added by the GC proposal to
    /// initialize non-nullable tables.
    fn arbitrary_table_init(
        &mut self,
        u: &mut Unstructured,
        ty: RefType,
    ) -> Result<Option<ConstExpr>> {
        if !self.config.gc_enabled {
            assert!(ty.nullable);
            return Ok(None);
        }
        // Even with the GC proposal an initialization expression is not
        // required if the element type is nullable.
        if ty.nullable && u.arbitrary()? {
            return Ok(None);
        }
        let expr = self.arbitrary_const_expr(ValType::Ref(ty), u)?;
        Ok(Some(expr))
    }

    fn arbitrary_memories(&mut self, u: &mut Unstructured) -> Result<()> {
        arbitrary_loop(
            u,
            self.config.min_memories as usize,
            self.config.max_memories as usize,
            |u| {
                if !self.can_add_local_or_import_memory() {
                    return Ok(false);
                }
                self.num_defined_memories += 1;
                self.memories.push(arbitrary_memtype(u, self.config())?);
                Ok(true)
            },
        )
    }

    /// Add a new global of the given type and return its global index.
    fn add_arbitrary_global_of_type(
        &mut self,
        ty: GlobalType,
        u: &mut Unstructured,
    ) -> Result<u32> {
        let expr = self.arbitrary_const_expr(ty.val_type, u)?;
        let global_idx = self.globals.len() as u32;
        self.globals.push(ty);
        self.defined_globals.push((global_idx, expr));
        Ok(global_idx)
    }

    /// Generates an arbitrary constant expression of the type `ty`.
    fn arbitrary_const_expr(&mut self, ty: ValType, u: &mut Unstructured) -> Result<ConstExpr> {
        let mut choices = mem::take(&mut self.const_expr_choices);
        choices.clear();
        let num_funcs = self.funcs.len() as u32;

        // MVP wasm can `global.get` any immutable imported global in a
        // constant expression, and the GC proposal enables this for all
        // globals, so make all matching globals a candidate.
        for i in self.globals_for_const_expr(ty) {
            choices.push(Box::new(move |_, _| Ok(ConstExpr::global_get(i))));
        }

        // Another option for all types is to have an actual value of each type.
        // Change `ty` to any valid subtype of `ty` and then generate a matching
        // type of that value.
        let ty = self.arbitrary_matching_val_type(u, ty)?;
        match ty {
            ValType::I32 => choices.push(Box::new(|u, _| Ok(ConstExpr::i32_const(u.arbitrary()?)))),
            ValType::I64 => choices.push(Box::new(|u, _| Ok(ConstExpr::i64_const(u.arbitrary()?)))),
            ValType::F32 => choices.push(Box::new(|u, _| Ok(ConstExpr::f32_const(u.arbitrary()?)))),
            ValType::F64 => choices.push(Box::new(|u, _| Ok(ConstExpr::f64_const(u.arbitrary()?)))),
            ValType::V128 => {
                choices.push(Box::new(|u, _| Ok(ConstExpr::v128_const(u.arbitrary()?))))
            }

            ValType::Ref(ty) => {
                if ty.nullable {
                    choices.push(Box::new(move |_, _| Ok(ConstExpr::ref_null(ty.heap_type))));
                }

                match ty.heap_type {
                    HeapType::Abstract {
                        ty: AbstractHeapType::Func,
                        ..
                    } if num_funcs > 0 => {
                        choices.push(Box::new(move |u, _| {
                            let func = u.int_in_range(0..=num_funcs - 1)?;
                            Ok(ConstExpr::ref_func(func))
                        }));
                    }

                    HeapType::Concrete(ty) => {
                        for (i, fty) in self.funcs.iter().map(|(t, _)| *t).enumerate() {
                            if ty != fty {
                                continue;
                            }
                            choices.push(Box::new(move |_, _| Ok(ConstExpr::ref_func(i as u32))));
                        }
                    }

                    // TODO: fill out more GC types e.g `array.new` and
                    // `struct.new`
                    _ => {}
                }
            }
        }

        let f = u.choose(&choices)?;
        let ret = f(u, ty);
        self.const_expr_choices = choices;
        ret
    }

    fn arbitrary_globals(&mut self, u: &mut Unstructured) -> Result<()> {
        arbitrary_loop(u, self.config.min_globals, self.config.max_globals, |u| {
            if !self.can_add_local_or_import_global() {
                return Ok(false);
            }

            let ty = self.arbitrary_global_type(u)?;
            self.add_arbitrary_global_of_type(ty, u)?;

            Ok(true)
        })
    }

    fn required_exports(&mut self, u: &mut Unstructured) -> Result<bool> {
        let example_module = if let Some(wasm) = self.config.exports.clone() {
            wasm
        } else {
            return Ok(false);
        };

        #[cfg(feature = "wasmparser")]
        {
            self._required_exports(u, &example_module)?;
            Ok(true)
        }
        #[cfg(not(feature = "wasmparser"))]
        {
            let _ = (example_module, u);
            panic!("support for `exports` was disabled at compile time");
        }
    }

    #[cfg(feature = "wasmparser")]
    fn _required_exports(&mut self, u: &mut Unstructured, example_module: &[u8]) -> Result<()> {
        let mut required_exports: Vec<wasmparser::Export> = vec![];
        let mut validator = wasmparser::Validator::new();
        let exports_types = validator
            .validate_all(&example_module)
            .expect("Failed to validate `exports` Wasm");
        for payload in wasmparser::Parser::new(0).parse_all(&example_module) {
            match payload.expect("Failed to read `exports` Wasm") {
                wasmparser::Payload::ExportSection(export_reader) => {
                    required_exports = export_reader
                        .into_iter()
                        .collect::<Result<_, _>>()
                        .expect("Failed to read `exports` export section");
                }
                _ => {}
            }
        }

        // For each export, add necessary prerequisites to the module.
        let exports_types = exports_types.as_ref();
        for export in required_exports {
            let new_index = match exports_types
                .entity_type_from_export(&export)
                .unwrap_or_else(|| {
                    panic!(
                        "Unable to get type from export {:?} in `exports` Wasm",
                        export,
                    )
                }) {
                // For functions, add the type and a function with that type.
                wasmparser::types::EntityType::Func(id) => {
                    let subtype = exports_types.get(id).unwrap_or_else(|| {
                        panic!(
                            "Unable to get subtype for function {:?} in `exports` Wasm",
                            id
                        )
                    });
                    match &subtype.composite_type.inner {
                        wasmparser::CompositeInnerType::Func(func_type) => {
                            assert!(
                                subtype.is_final,
                                "Subtype {:?} from `exports` Wasm is not final",
                                subtype
                            );
                            assert!(
                                subtype.supertype_idx.is_none(),
                                "Subtype {:?} from `exports` Wasm has non-empty supertype",
                                subtype
                            );
                            let new_type = Rc::new(FuncType {
                                params: func_type
                                    .params()
                                    .iter()
                                    .copied()
                                    .map(|t| t.try_into().unwrap())
                                    .collect(),
                                results: func_type
                                    .results()
                                    .iter()
--> --------------------

--> maximum size reached

--> --------------------