lib.rs

//! A WebAssembly test case generator.
//!
//! ## Usage
//!
//! First, use [`cargo fuzz`](https://github.com/rust-fuzz/cargo-fuzz) to define
//! a new fuzz target:
//!
//! ```shell
//! $ cargo fuzz add my_wasm_smith_fuzz_target
//! ```
//!
//! Next, add `wasm-smith` to your dependencies:
//!
//! ```toml
//! # fuzz/Cargo.toml
//!
//! [dependencies]
//! wasm-smith = "0.4.0"
//! ```
//!
//! Then, define your fuzz target so that it takes arbitrary
//! `wasm_smith::Module`s as an argument, convert the module into serialized
//! Wasm bytes via the `to_bytes` method, and then feed it into your system:
//!
//! ```no_run
//! // fuzz/fuzz_targets/my_wasm_smith_fuzz_target.rs
//!
//! #![no_main]
//!
//! use libfuzzer_sys::fuzz_target;
//! use wasm_smith::Module;
//!
//! fuzz_target!(|module: Module| {
//!     let wasm_bytes = module.to_bytes();
//!
//!     // Your code here...
//! });
//! ```
//!
//! Finally, start fuzzing:
//!
//! ```shell
//! $ cargo fuzz run my_wasm_smith_fuzz_target
//! ```
//!
//! > **Note:** For a real world example, also check out [the `validate` fuzz
//! > target](https://github.com/fitzgen/wasm-smith/blob/main/fuzz/fuzz_targets/validate.rs)
//! > defined in this repository. Using the `wasmparser` crate, it checks that
//! > every module generated by `wasm-smith` validates successfully.

#![deny(missing_docs, missing_debug_implementations)]
// Needed for the `instructions!` macro in `src/code_builder.rs`.
#![recursion_limit = "256"]

mod code_builder;
mod config;
mod encode;
mod terminate;

use crate::code_builder::CodeBuilderAllocations;
use arbitrary::{Arbitrary, Result, Unstructured};
use std::collections::{HashMap, HashSet};
use std::rc::Rc;
use std::str;

pub use config::{Config, DefaultConfig, SwarmConfig};

/// A pseudo-random WebAssembly module.
///
/// Construct instances of this type with [the `Arbitrary`
/// trait](https://docs.rs/arbitrary/*/arbitrary/trait.Arbitrary.html).
///
/// ## Configuring Generated Modules
///
/// This uses the [`DefaultConfig`][crate::DefaultConfig] configuration. If you
/// want to customize the shape of generated modules, define your own
/// configuration type, implement the [`Config`][crate::Config] trait for it,
/// and use [`ConfiguredModule<YourConfigType>`][crate::ConfiguredModule]
/// instead of plain `Module`.
#[derive(Debug, Default, Arbitrary)]
pub struct Module {
    inner: ConfiguredModule<DefaultConfig>,
}

/// A pseudo-random generated WebAssembly file with custom configuration.
///
/// If you don't care about custom configuration, use [`Module`][crate::Module]
/// instead.
///
/// For details on configuring, see the [`Config`][crate::Config] trait.
#[derive(Debug, Default)]
pub struct ConfiguredModule<C>
where
    C: Config,
{
    config: C,
    valtypes: Vec<ValType>,

    /// Outer modules, if any (used for module linking)
    outers: Vec<Outer>,

    /// The initial sections of this wasm module, including types and imports.
    /// This is stored as a list-of-lists where each `InitialSection` represents
    /// a whole section, so this `initial_sections` list represents a list of
    /// sections.
    ///
    /// With the module linking proposal, types, imports, module, instance,
    /// and alias sections can come in any order and occur repeatedly at the
    /// start of a Wasm module. We want to generate interesting entities --
    /// entities that require multiple, interspersed occurrences of these
    /// sections -- and we don't want to always generate the "same shape" of
    /// these initial sections. Each entry in this initializers list is one of
    /// these initial sections, and we will directly encode each entry as a
    /// section when we serialize this module to bytes, which allows us to
    /// easily model the flexibility of the module linking proposal.
    initial_sections: Vec<InitialSection<C>>,

    /// A map of what import names have been generated. The key here is the
    /// name of the import and the value is `None` if it's a single-level
    /// import or `Some` if it's a two-level import with the set of
    /// second-level import names that have been generated so far.
    import_names: HashMap<String, Option<HashSet<String>>>,

    /// Where within the `instances` array each implicit instance's type is
    /// defined.
    implicit_instance_types: HashMap<String, usize>,

    /// All types locally defined in this module (available in the type index
    /// space).
    types: Vec<LocalType>,
    /// Indices within `types` that are function types.
    func_types: Vec<u32>,
    /// Indices within `types` that are module types.
    module_types: Vec<u32>,
    /// Indices within `types` that are instance types.
    instance_types: Vec<u32>,

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

    /// Number of items aliased into this module.
    num_aliases: usize,

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

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

    /// 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, Instruction)>,

    /// 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.
    ///
    /// Note that aliased functions may have types not defined in this module,
    /// hence the optional index type. All defined functions in this module,
    /// however, will have an index type specified.
    funcs: Vec<(Option<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>,

    /// All instances available to this module, sorted by their index. The list
    /// entry is the type of the instance.
    instances: Vec<Rc<InstanceType>>,

    /// All modules available to this module, sorted by their index. The list
    /// entry is the type of the module.
    modules: Vec<Rc<ModuleType>>,

    exports: Vec<(String, Export)>,
    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,
}

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

impl<'a, C: Config> Arbitrary<'a> for ConfiguredModule<C> {
    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
        let mut module = ConfiguredModule::<C>::default();
        module.build(u, false)?;
        Ok(module)
    }
}

/// Same as [`Module`], but may be invalid.
///
/// This module generates function bodies differnetly than `Module` to try to
/// better explore wasm decoders and such.
#[derive(Debug, Default)]
pub struct MaybeInvalidModule {
    module: Module,
}

impl MaybeInvalidModule {
    /// Encode this Wasm module into bytes.
    pub fn to_bytes(&self) -> Vec<u8> {
        self.module.to_bytes()
    }
}

impl<'a> Arbitrary<'a> for MaybeInvalidModule {
    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
        let mut module = Module::default();
        module.inner.build(u, true)?;
        Ok(MaybeInvalidModule { module })
    }
}

#[derive(Debug)]
enum InitialSection<C: Config> {
    Type(Vec<Type>),
    Import(Vec<(String, Option<String>, EntityType)>),
    Alias(Vec<Alias>),
    Instance(Vec<Instance>),
    Module(Vec<ConfiguredModule<C>>),
}

#[derive(Clone, Debug)]
enum Type {
    Func(Rc<FuncType>),
    Module(Rc<ModuleType>),
    Instance(Rc<InstanceType>),
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
struct FuncType {
    params: Vec<ValType>,
    results: Vec<ValType>,
}

#[derive(Clone, Debug, Default)]
struct InstanceType {
    type_size: u32,
    exports: indexmap::IndexMap<String, EntityType>,
}

#[derive(Clone, Debug)]
struct ModuleType {
    type_size: u32,
    imports: Vec<(String, Option<String>, EntityType)>,
    import_types: indexmap::IndexMap<String, EntityType>,
    /// The list of exports can be found in the `InstanceType` indirection here,
    /// and this struct layout is used to ease the instantiation process where
    /// we record an instance's signature.
    exports: Rc<InstanceType>,
}

#[derive(Clone, Debug)]
enum EntityType {
    Global(GlobalType),
    Table(TableType),
    Memory(MemoryType),
    Func(u32, Rc<FuncType>),
    Instance(u32, Rc<InstanceType>),
    Module(u32, Rc<ModuleType>),
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
enum ValType {
    I32,
    I64,
    F32,
    F64,
    FuncRef,
    ExternRef,
}

#[derive(Clone, Debug)]
struct TableType {
    limits: Limits,
    elem_ty: ValType,
}

#[derive(Clone, Debug)]
struct MemoryType {
    limits: Limits,
}

#[derive(Clone, Debug)]
struct Limits {
    min: u32,
    max: Option<u32>,
}

impl Limits {
    fn limited(u: &mut Unstructured, max_minimum: u32, max_required: bool) -> Result<Self> {
        let min = u.int_in_range(0..=max_minimum)?;
        let max = if max_required || u.arbitrary().unwrap_or(false) {
            Some(if min == max_minimum {
                max_minimum
            } else {
                u.int_in_range(min..=max_minimum)?
            })
        } else {
            None
        };
        Ok(Limits { min, max })
    }
}

#[derive(Clone, Debug, PartialEq)]
struct GlobalType {
    val_type: ValType,
    mutable: bool,
}

#[derive(Clone, Debug)]
enum Alias {
    InstanceExport {
        instance: u32,
        kind: ItemKind,
        name: String,
    },
    OuterType {
        depth: u32,
        index: u32,
    },
    OuterModule {
        depth: u32,
        index: u32,
    },
}

#[derive(Clone, Debug)]
struct Instance {
    module: u32,
    args: Vec<(String, Export)>,
}

#[derive(Copy, Clone, Debug)]
enum ItemKind {
    Func,
    Table,
    Memory,
    Global,
    Instance,
    Module,
}

#[derive(Copy, Clone, Debug)]
enum Export {
    Func(u32),
    Table(u32),
    Memory(u32),
    Global(u32),
    Instance(u32),
    Module(u32),
}

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

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

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

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

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

#[derive(Clone, Copy, Debug)]
enum BlockType {
    Empty,
    Result(ValType),
    FuncType(u32),
}

impl BlockType {
    fn params_results<C>(&self, module: &ConfiguredModule<C>) -> (Vec<ValType>, Vec<ValType>)
    where
        C: Config,
    {
        match self {
            BlockType::Empty => (vec![], vec![]),
            BlockType::Result(t) => (vec![], vec![*t]),
            BlockType::FuncType(ty) => {
                let ty = module.func_type(*ty);
                (ty.params.clone(), ty.results.clone())
            }
        }
    }
}

#[derive(Clone, Copy, Debug)]
struct MemArg {
    offset: u32,
    align: u32,
    memory_index: u32,
}

#[derive(Clone, Debug)]
#[allow(non_camel_case_types)]
enum Instruction {
    // Control instructions.
    Unreachable,
    Nop,
    Block(BlockType),
    Loop(BlockType),
    If(BlockType),
    Else,
    End,
    Br(u32),
    BrIf(u32),
    BrTable(Vec<u32>, u32),
    Return,
    Call(u32),
    CallIndirect { ty: u32, table: u32 },

    // Parametric instructions.
    Drop,
    Select,

    // Variable instructions.
    LocalGet(u32),
    LocalSet(u32),
    LocalTee(u32),
    GlobalGet(u32),
    GlobalSet(u32),

    // Memory instructions.
    I32Load(MemArg),
    I64Load(MemArg),
    F32Load(MemArg),
    F64Load(MemArg),
    I32Load8_S(MemArg),
    I32Load8_U(MemArg),
    I32Load16_S(MemArg),
    I32Load16_U(MemArg),
    I64Load8_S(MemArg),
    I64Load8_U(MemArg),
    I64Load16_S(MemArg),
    I64Load16_U(MemArg),
    I64Load32_S(MemArg),
    I64Load32_U(MemArg),
    I32Store(MemArg),
    I64Store(MemArg),
    F32Store(MemArg),
    F64Store(MemArg),
    I32Store8(MemArg),
    I32Store16(MemArg),
    I64Store8(MemArg),
    I64Store16(MemArg),
    I64Store32(MemArg),
    MemorySize(u32),
    MemoryGrow(u32),
    MemoryInit { mem: u32, data: u32 },
    DataDrop(u32),
    MemoryCopy { src: u32, dst: u32 },
    MemoryFill(u32),

    // Numeric instructions.
    I32Const(i32),
    I64Const(i64),
    F32Const(f32),
    F64Const(f64),
    I32Eqz,
    I32Eq,
    I32Neq,
    I32LtS,
    I32LtU,
    I32GtS,
    I32GtU,
    I32LeS,
    I32LeU,
    I32GeS,
    I32GeU,
    I64Eqz,
    I64Eq,
    I64Neq,
    I64LtS,
    I64LtU,
    I64GtS,
    I64GtU,
    I64LeS,
    I64LeU,
    I64GeS,
    I64GeU,
    F32Eq,
    F32Neq,
    F32Lt,
    F32Gt,
    F32Le,
    F32Ge,
    F64Eq,
    F64Neq,
    F64Lt,
    F64Gt,
    F64Le,
    F64Ge,
    I32Clz,
    I32Ctz,
    I32Popcnt,
    I32Add,
    I32Sub,
    I32Mul,
    I32DivS,
    I32DivU,
    I32RemS,
    I32RemU,
    I32And,
    I32Or,
    I32Xor,
    I32Shl,
    I32ShrS,
    I32ShrU,
    I32Rotl,
    I32Rotr,
    I64Clz,
    I64Ctz,
    I64Popcnt,
    I64Add,
    I64Sub,
    I64Mul,
    I64DivS,
    I64DivU,
    I64RemS,
    I64RemU,
    I64And,
    I64Or,
    I64Xor,
    I64Shl,
    I64ShrS,
    I64ShrU,
    I64Rotl,
    I64Rotr,
    F32Abs,
    F32Neg,
    F32Ceil,
    F32Floor,
    F32Trunc,
    F32Nearest,
    F32Sqrt,
    F32Add,
    F32Sub,
    F32Mul,
    F32Div,
    F32Min,
    F32Max,
    F32Copysign,
    F64Abs,
    F64Neg,
    F64Ceil,
    F64Floor,
    F64Trunc,
    F64Nearest,
    F64Sqrt,
    F64Add,
    F64Sub,
    F64Mul,
    F64Div,
    F64Min,
    F64Max,
    F64Copysign,
    I32WrapI64,
    I32TruncF32S,
    I32TruncF32U,
    I32TruncF64S,
    I32TruncF64U,
    I64ExtendI32S,
    I64ExtendI32U,
    I64TruncF32S,
    I64TruncF32U,
    I64TruncF64S,
    I64TruncF64U,
    F32ConvertI32S,
    F32ConvertI32U,
    F32ConvertI64S,
    F32ConvertI64U,
    F32DemoteF64,
    F64ConvertI32S,
    F64ConvertI32U,
    F64ConvertI64S,
    F64ConvertI64U,
    F64PromoteF32,
    I32ReinterpretF32,
    I64ReinterpretF64,
    F32ReinterpretI32,
    F64ReinterpretI64,
    I32Extend8S,
    I32Extend16S,
    I64Extend8S,
    I64Extend16S,
    I64Extend32S,
    I32TruncSatF32S,
    I32TruncSatF32U,
    I32TruncSatF64S,
    I32TruncSatF64U,
    I64TruncSatF32S,
    I64TruncSatF32U,
    I64TruncSatF64S,
    I64TruncSatF64U,
    TypedSelect(ValType),
    RefNull(ValType),
    RefIsNull,
    RefFunc(u32),
    TableInit { segment: u32, table: u32 },
    ElemDrop { segment: u32 },
    TableFill { table: u32 },
    TableSet { table: u32 },
    TableGet { table: u32 },
    TableGrow { table: u32 },
    TableSize { table: u32 },
    TableCopy { src: u32, dst: u32 },
}

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

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

impl<C> ConfiguredModule<C>
where
    C: Config,
{
    fn build(&mut self, u: &mut Unstructured, allow_invalid: bool) -> Result<()> {
        self.config = C::arbitrary(u)?;
        self.valtypes.push(ValType::I32);
        self.valtypes.push(ValType::I64);
        self.valtypes.push(ValType::F32);
        self.valtypes.push(ValType::F64);
        if self.config.reference_types_enabled() {
            self.valtypes.push(ValType::ExternRef);
            self.valtypes.push(ValType::FuncRef);
        }
        self.arbitrary_initial_sections(u)?;
        self.arbitrary_funcs(u)?;
        self.arbitrary_tables(u)?;
        self.arbitrary_memories(u)?;
        self.arbitrary_globals(u)?;
        self.arbitrary_exports(u)?;
        self.arbitrary_start(u)?;
        self.arbitrary_elems(u)?;
        self.arbitrary_data(u)?;
        self.arbitrary_code(u, allow_invalid)?;
        Ok(())
    }

    fn arbitrary_initial_sections(&mut self, u: &mut Unstructured) -> Result<()> {
        let mut aliases = AvailableAliases::default();
        let mut instantiations = AvailableInstantiations::default();
        if !self.config.module_linking_enabled() {
            self.arbitrary_types(self.config.min_types(), u)?;
            self.arbitrary_imports(self.config.min_imports(), u)?;
            return Ok(());
        }

        let mut choices: Vec<
            fn(
                &mut Unstructured,
                &mut ConfiguredModule<C>,
                &mut AvailableAliases,
                &mut AvailableInstantiations,
            ) -> Result<()>,
        > = Vec::new();
        loop {
            choices.clear();
            if self.types.len() < self.config.max_types() {
                choices.push(|u, m, _, _| m.arbitrary_types(0, u));
            }
            if self.num_imports < self.config.max_imports() {
                choices.push(|u, m, _, _| m.arbitrary_imports(0, u));
            }
            if self.modules.len() < self.config.max_modules()
                && self.outers.len() < self.config.max_nesting_depth()
            {
                choices.push(|u, m, _, _| m.arbitrary_modules(u));
            }
            aliases.update(self);
            if self.num_aliases < self.config.max_aliases() && aliases.aliases.len() > 0 {
                choices.push(|u, m, a, _| m.arbitrary_aliases(a, u));
            }
            instantiations.update(self);
            if self.instances.len() < self.config.max_instances() {
                choices.push(|u, m, _, i| m.arbitrary_instances(i, u));
            }
            if choices.is_empty() || !u.arbitrary()? {
                break;
            }
            u.choose(&choices)?(u, self, &mut aliases, &mut instantiations)?;
        }

        // If after generating a list of sections we haven't met our
        // minimum quotas then meet them now.
        if self.types.len() < self.config.min_types() {
            self.arbitrary_types(self.config.min_types() - self.types.len(), u)?;
        }
        if self.num_imports < self.config.min_imports() {
            self.arbitrary_imports(self.config.min_imports() - self.num_imports, u)?;
        }
        Ok(())
    }

    fn arbitrary_types(&mut self, min: usize, u: &mut Unstructured) -> Result<()> {
        // Note that we push to `self.initializers` immediately because types
        // can mention any previous types, so we need to ensure that after each
        // type is generated it's listed in the module's types so indexing will
        // succeed.
        let section_idx = self.initial_sections.len();
        self.initial_sections.push(InitialSection::Type(Vec::new()));
        arbitrary_loop(u, min, self.config.max_types() - self.types.len(), |u| {
            let ty = self.arbitrary_type(u)?;
            self.record_type(&ty);
            let types = match self.initial_sections.last_mut().unwrap() {
                InitialSection::Type(list) => list,
                _ => unreachable!(),
            };
            self.types.push(LocalType::Defined {
                section: section_idx,
                nth: types.len(),
            });
            types.push(ty);
            Ok(true)
        })?;
        let types = match self.initial_sections.last_mut().unwrap() {
            InitialSection::Type(list) => list,
            _ => unreachable!(),
        };
        if types.is_empty() && !u.arbitrary()? {
            self.initial_sections.pop();
        }
        Ok(())
    }

    fn record_type(&mut self, ty: &Type) {
        let list = match &ty {
            Type::Func(_) => &mut self.func_types,
            Type::Module(_) => &mut self.module_types,
            Type::Instance(_) => &mut self.instance_types,
        };
        list.push(self.types.len() as u32);
    }

    fn arbitrary_type(&mut self, u: &mut Unstructured) -> Result<Type> {
        if !self.config.module_linking_enabled() {
            return Ok(Type::Func(self.arbitrary_func_type(u)?));
        }
        Ok(match u.int_in_range(0..=2)? {
            0 => Type::Func(self.arbitrary_func_type(u)?),
            1 => Type::Module(self.arbitrary_module_type(u, &mut Entities::default())?),
            _ => Type::Instance(self.arbitrary_instance_type(u, &mut Entities::default())?),
        })
    }

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

    fn arbitrary_module_type(
        &mut self,
        u: &mut Unstructured,
        entities: &mut Entities,
    ) -> Result<Rc<ModuleType>> {
        let exports = self.arbitrary_instance_type(u, entities)?;
        let mut imports = Vec::new();
        let mut import_types = indexmap::IndexMap::new();
        let mut names = HashMap::new();
        let mut type_size = exports.type_size;
        if !entities.max_reached(&self.config) {
            arbitrary_loop(u, 0, self.config.max_imports(), |u| {
                let (module, name) = unique_import_strings(1_000, &mut names, true, u)?;
                let ty = self.arbitrary_entity_type(u, entities)?;
                match type_size.checked_add(ty.size() + 1) {
                    Some(s) if s < self.config.max_type_size() => type_size = s,
                    _ => return Ok(false),
                }
                if let Some(name) = &name {
                    let ity = import_types.entry(module.clone()).or_insert_with(|| {
                        EntityType::Instance(u32::max_value(), Default::default())
                    });
                    let ity = match ity {
                        EntityType::Instance(_, ty) => Rc::get_mut(ty).unwrap(),
                        _ => unreachable!(),
                    };
                    ity.exports.insert(name.clone(), ty.clone());
                } else {
                    import_types.insert(module.clone(), ty.clone());
                }
                imports.push((module, name, ty));
                Ok(!entities.max_reached(&self.config))
            })?;
        }
        Ok(Rc::new(ModuleType {
            type_size,
            imports,
            import_types,
            exports,
        }))
    }

    fn arbitrary_instance_type(
        &mut self,
        u: &mut Unstructured,
        entities: &mut Entities,
    ) -> Result<Rc<InstanceType>> {
        let mut export_names = HashSet::new();
        let mut exports = indexmap::IndexMap::new();
        let mut type_size = 0u32;
        if !entities.max_reached(&self.config) {
            arbitrary_loop(u, 0, self.config.max_exports(), |u| {
                let name = unique_string(1_000, &mut export_names, u)?;
                let ty = self.arbitrary_entity_type(u, entities)?;
                match type_size.checked_add(ty.size() + 1) {
                    Some(s) if s < self.config.max_type_size() => type_size = s,
                    _ => return Ok(false),
                }
                exports.insert(name, ty);
                Ok(!entities.max_reached(&self.config))
            })?;
        }
        Ok(Rc::new(InstanceType { type_size, exports }))
    }

    fn arbitrary_entity_type(
        &mut self,
        u: &mut Unstructured,
        entities: &mut Entities,
    ) -> Result<EntityType> {
        let mut choices: Vec<
            fn(&mut Unstructured, &mut ConfiguredModule<C>, &mut Entities) -> Result<EntityType>,
        > = Vec::with_capacity(6);

        if entities.globals < self.config.max_globals() {
            choices.push(|u, m, e| {
                e.globals += 1;
                Ok(EntityType::Global(m.arbitrary_global_type(u)?))
            });
        }
        if entities.memories < self.config.max_memories() {
            choices.push(|u, m, e| {
                e.memories += 1;
                Ok(EntityType::Memory(m.arbitrary_memtype(u)?))
            });
        }
        if entities.tables < self.config.max_tables() {
            choices.push(|u, m, e| {
                e.tables += 1;
                Ok(EntityType::Table(m.arbitrary_table_type(u)?))
            });
        }
        if entities.funcs < self.config.max_funcs() && self.func_types.len() > 0 {
            choices.push(|u, m, e| {
                e.funcs += 1;
                let idx = *u.choose(&m.func_types)?;
                let ty = m.func_type(idx);
                Ok(EntityType::Func(idx, ty.clone()))
            });
        }
        if entities.instances < self.config.max_instances() && self.instance_types.len() > 0 {
            choices.push(|u, m, e| {
                e.instances += 1;
                let idx = *u.choose(&m.instance_types)?;
                let ty = m.instance_type(idx);
                Ok(EntityType::Instance(idx, ty.clone()))
            });
        }
        if entities.modules < self.config.max_modules() && self.module_types.len() > 0 {
            choices.push(|u, m, e| {
                e.modules += 1;
                let idx = *u.choose(&m.module_types)?;
                let ty = m.module_type(idx);
                Ok(EntityType::Module(idx, ty.clone()))
            });
        }
        u.choose(&choices)?(u, self, entities)
    }

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

    fn can_add_local_or_import_instance(&self) -> bool {
        self.instance_types.len() > 0 && self.instances.len() < self.config.max_instances()
    }

    fn can_add_local_or_import_module(&self) -> bool {
        self.module_types.len() > 0 && self.modules.len() < self.config.max_modules()
    }

    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, min: usize, u: &mut Unstructured) -> Result<()> {
        if self.config.max_type_size() < self.type_size {
            return Ok(());
        }

        let mut choices: Vec<
            fn(&mut Unstructured, &mut ConfiguredModule<C>) -> Result<EntityType>,
        > = Vec::with_capacity(4);

        let mut imports = Vec::new();
        arbitrary_loop(u, min, self.config.max_imports() - self.num_imports, |u| {
            choices.clear();
            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_module() {
                choices.push(|u, m| {
                    let idx = *u.choose(&m.module_types)?;
                    let ty = m.module_type(idx).clone();
                    Ok(EntityType::Module(idx, ty.clone()))
                });
            }
            if self.can_add_local_or_import_instance() {
                choices.push(|u, m| {
                    let idx = *u.choose(&m.instance_types)?;
                    let ty = m.instance_type(idx).clone();
                    Ok(EntityType::Instance(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 = m.arbitrary_memtype(u)?;
                    Ok(EntityType::Memory(ty))
                });
            }
            if self.can_add_local_or_import_table() {
                choices.push(|u, m| {
                    let ty = m.arbitrary_table_type(u)?;
                    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 ty = f(u, self)?;
            let budget = self.config.max_type_size() - self.type_size;
            if ty.size() + 1 > budget {
                return Ok(false);
            }
            self.type_size += ty.size() + 1;

            // Generate an arbitrary module/name pair to name this import. Note
            // that if module-linking is enabled and `name` is present, then we
            // might be implicitly generating an instance. If that's the case
            // then we need to record the type of this instance.
            let module_linking = self.config.module_linking_enabled() || self.outers.len() > 0;
            let (module, name) =
                unique_import_strings(1_000, &mut self.import_names, module_linking, u)?;
            if module_linking
                && name.is_some()
                && self.import_names[&module].as_ref().unwrap().len() == 1
            {
                // This is the first time this module name is imported from, so
                // generate a new instance type.
                self.implicit_instance_types
                    .insert(module.clone(), self.instances.len());
                self.instances.push(Rc::new(InstanceType::default()));
            }

            // Once our name is determined, and if module linking is enabled
            // we've inserted the implicit instance, then we push the typed item
            // into the appropriate namespace.
            match &ty {
                EntityType::Func(idx, ty) => self.funcs.push((Some(*idx), ty.clone())),
                EntityType::Global(ty) => self.globals.push(ty.clone()),
                EntityType::Table(ty) => self.tables.push(ty.clone()),
                EntityType::Memory(ty) => self.memories.push(ty.clone()),
                EntityType::Module(_idx, ty) => self.modules.push(ty.clone()),
                EntityType::Instance(_idx, ty) => self.instances.push(ty.clone()),
            }

            if let Some(name) = &name {
                if module_linking {
                    let idx = self.implicit_instance_types[&module];
                    let instance_ty = &mut self.instances[idx];
                    Rc::get_mut(instance_ty)
                        .expect("shouldn't be aliased yet")
                        .exports
                        .insert(name.clone(), ty.clone());
                }
            }

            self.num_imports += 1;
            imports.push((module, name, ty));
            Ok(true)
        })?;
        if !imports.is_empty() || u.arbitrary()? {
            self.initial_sections.push(InitialSection::Import(imports));
        }

        // After an import section we can no longer update previously-defined
        // pseudo-instance imports, so set them all to `None` indicating that
        // the bare name is imported and finalized.
        for val in self.import_names.values_mut() {
            *val = None;
        }
        Ok(())
    }

    fn arbitrary_aliases(
        &mut self,
        available: &mut AvailableAliases,
        u: &mut Unstructured,
    ) -> Result<()> {
        assert!(available.aliases.len() > 0);

        let mut aliases = Vec::new();
        arbitrary_loop(u, 0, self.config.max_aliases() - self.num_aliases, |u| {
            let choice = u.choose(&available.aliases)?;
            aliases.push(choice.clone());
            match choice {
                Alias::InstanceExport {
                    instance,
                    kind,
                    name,
                } => {
                    let ty = &self.instances[*instance as usize];
                    match kind {
                        ItemKind::Global => {
                            let ty = match &ty.exports[name] {
                                EntityType::Global(t) => t.clone(),
                                _ => unreachable!(),
                            };
                            self.globals.push(ty);
                        }
                        ItemKind::Table => {
                            let ty = match &ty.exports[name] {
                                EntityType::Table(t) => t.clone(),
                                _ => unreachable!(),
                            };
                            self.tables.push(ty);
                        }
                        ItemKind::Memory => {
                            let ty = match &ty.exports[name] {
                                EntityType::Memory(t) => t.clone(),
                                _ => unreachable!(),
                            };
                            self.memories.push(ty);
                        }
                        ItemKind::Func => {
                            let (i, ty) = match &ty.exports[name] {
                                EntityType::Func(i, t) => (*i, t),
                                _ => unreachable!(),
                            };
                            self.funcs.push((Some(i), ty.clone()));
                        }
                        ItemKind::Module => {
                            let ty = match &ty.exports[name] {
                                EntityType::Module(_, t) => t,
                                _ => unreachable!(),
                            };
                            self.modules.push(ty.clone());
                        }
                        ItemKind::Instance => {
                            let ty = match &ty.exports[name] {
                                EntityType::Instance(_, t) => t,
                                _ => unreachable!(),
                            };
                            let ty = ty.clone();
                            self.instances.push(ty);
                        }
                    }
                }
                Alias::OuterType { depth, index } => {
                    let ty = self.outers[*depth as usize].types[*index as usize].clone();
                    self.record_type(&ty);
                    self.types.push(LocalType::Aliased(ty));
                }
                Alias::OuterModule { depth, index } => {
                    let ty = self.outers[*depth as usize].modules[*index as usize].clone();
                    self.modules.push(ty);
                }
            }
            available.update(self);
            self.num_aliases += 1;
            Ok(available.aliases.len() > 0)
        })?;
        if !aliases.is_empty() || u.arbitrary()? {
            self.initial_sections.push(InitialSection::Alias(aliases));
        }
        Ok(())
    }

    fn arbitrary_instances(
        &mut self,
        available: &mut AvailableInstantiations,
        u: &mut Unstructured,
    ) -> Result<()> {
        let mut instances = Vec::new();
        arbitrary_loop(
            u,
            0,
            self.config.max_instances() - self.instances.len(),
            |u| {
                // We can only instantiate a choice if all of its arguments
                // have at least one possibility, so filter for those candidates
                // and break out if there are 0, otherwise select one of them.
                let choices = available
                    .choices
                    .iter()
                    .filter(|i| i.args.iter().all(|i| !i.1.is_empty()))
                    .collect::<Vec<_>>();
                if choices.len() == 0 {
                    return Ok(false);
                }
                let choice = u.choose(&choices)?;
                instances.push(Instance {
                    module: choice.module,
                    args: choice
                        .args
                        .iter()
                        .map(|(name, candidates)| {
                            u.choose(candidates).map(|e| (name.clone(), e.clone()))
                        })
                        .collect::<Result<Vec<_>>>()?,
                });
                let ty = self.modules[choice.module as usize].exports.clone();
                self.instances.push(ty);
                available.update(self);
                Ok(true)
            },
        )?;
        if !instances.is_empty() || u.arbitrary()? {
            self.initial_sections
                .push(InitialSection::Instance(instances));
        }
        Ok(())
    }

    fn arbitrary_modules(&mut self, u: &mut Unstructured) -> Result<()> {
        let mut modules = Vec::new();
        arbitrary_loop(u, 0, self.config.max_modules(), |u| {
            let mut module = ConfiguredModule::<C>::default();
            module.outers = self.outers.clone();
            let parent = Outer {
                types: (0..self.types.len())
                    .map(|i| self.ty(i as u32).clone())
                    .collect(),
                modules: self.modules.clone(),
            };
            module.outers.insert(0, parent);
            module.config = self.config.clone();
            module.build(u, false)?;

            // After we've generated the `module`, we create `ty` which is its
            // own type signature of itself.
            let mut imports = Vec::with_capacity(module.num_imports);
            let mut import_types = indexmap::IndexMap::with_capacity(module.num_imports);
            for (name, field, ty) in module
                .initial_sections
                .iter()
                .filter_map(|section| match section {
                    InitialSection::Import(list) => Some(list),
                    _ => None,
                })
                .flat_map(|a| a)
            {
                if field.is_none() {
                    // If the field is none then `ty` matches the import type
                    // exactly.
                    import_types.insert(name.clone(), ty.clone());
                } else if import_types.get(name).is_none() {
                    // Otherwise if we haven't already recorded the implicit
                    // type of `name` then we do so here.
                    let ty = module.instances[module.implicit_instance_types[name]].clone();
                    import_types.insert(name.clone(), EntityType::Instance(u32::max_value(), ty));
                }
                imports.push((name.clone(), field.clone(), ty.clone()));
            }
            let mut exports = indexmap::IndexMap::with_capacity(module.exports.len());
            for (name, export) in module.exports.iter() {
                let ty = module.type_of(export);
                exports.insert(name.clone(), ty);
            }
            let ty = Rc::new(ModuleType {
                type_size: module.type_size,
                imports,
                import_types,
                exports: Rc::new(InstanceType {
                    // This type size isn't quite right since it takes into
                    // account imports, but that's ok for now since it's just a
                    // predictor about how big things should get.
                    type_size: module.type_size,
                    exports,
                }),
            });

            // And then given the type of the module we copy it over to
            // ourselves and get a type index. This index goes into the module
            // section and we also record the type of this module in our
            // `modules` array.
            modules.push(module);
            self.modules.push(ty.clone());
            Ok(true)
        })?;
        if !modules.is_empty() || u.arbitrary()? {
            self.initial_sections.push(InitialSection::Module(modules));
        }
        Ok(())
    }

    fn type_of(&self, item: &Export) -> EntityType {
        match *item {
            Export::Global(idx) => EntityType::Global(self.globals[idx as usize].clone()),
            Export::Memory(idx) => EntityType::Memory(self.memories[idx as usize].clone()),
            Export::Table(idx) => EntityType::Table(self.tables[idx as usize].clone()),
            Export::Func(idx) => {
                let (_idx, ty) = &self.funcs[idx as usize];
                EntityType::Func(u32::max_value(), ty.clone())
            }
            Export::Module(idx) => {
                EntityType::Module(u32::max_value(), self.modules[idx as usize].clone())
            }
            Export::Instance(idx) => {
                EntityType::Instance(u32::max_value(), self.instances[idx as usize].clone())
            }
        }
    }

    fn ty(&self, idx: u32) -> &Type {
        match &self.types[idx as usize] {
            LocalType::Defined { section, nth } => {
                if let InitialSection::Type(list) = &self.initial_sections[*section] {
                    return &list[*nth];
                }
                panic!("looked up a type with the wrong index")
            }
            LocalType::Aliased(ty) => ty,
        }
    }

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

    fn func_type(&self, idx: u32) -> &Rc<FuncType> {
        if let Type::Func(f) = self.ty(idx) {
            return f;
        }
        panic!("looked up a function type with the wrong index")
    }

    fn instance_type(&self, idx: u32) -> &Rc<InstanceType> {
        if let Type::Instance(f) = self.ty(idx) {
            return f;
        }
        panic!("looked up an instance type with the wrong index")
    }

    fn module_type(&self, idx: u32) -> &Rc<ModuleType> {
        if let Type::Module(f) = self.ty(idx) {
            return f;
        }
        panic!("looked up an instance type with the wrong index")
    }

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

    fn arbitrary_valtype(&self, u: &mut Unstructured) -> Result<ValType> {
        Ok(*u.choose(&self.valtypes)?)
    }

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

    fn arbitrary_table_type(&self, u: &mut Unstructured) -> Result<TableType> {
        Ok(TableType {
            elem_ty: if self.config.reference_types_enabled() {
                *u.choose(&[ValType::FuncRef, ValType::ExternRef])?
            } else {
                ValType::FuncRef
            },
            limits: Limits::limited(u, 1_000_000, false)?,
        })
    }

    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((Some(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);
                }
                self.num_defined_tables += 1;
                let ty = self.arbitrary_table_type(u)?;
                self.tables.push(ty);
                Ok(true)
            },
        )
    }

    fn arbitrary_memtype(&self, u: &mut Unstructured) -> Result<MemoryType> {
        let limits = Limits::limited(
            u,
            self.config.max_memory_pages(),
            self.config.memory_max_size_required(),
        )?;
        Ok(MemoryType { limits })
    }

    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(self.arbitrary_memtype(u)?);
                Ok(true)
            },
        )
    }

    fn arbitrary_globals(&mut self, u: &mut Unstructured) -> Result<()> {
        let mut choices: Vec<Box<dyn Fn(&mut Unstructured, ValType) -> Result<Instruction>>> =
            vec![];

        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)?;

                choices.clear();
                let num_funcs = self.funcs.len() as u32;
                choices.push(Box::new(move |u, ty| {
                    Ok(match ty {
                        ValType::I32 => Instruction::I32Const(u.arbitrary()?),
                        ValType::I64 => Instruction::I64Const(u.arbitrary()?),
                        ValType::F32 => Instruction::F32Const(u.arbitrary()?),
                        ValType::F64 => Instruction::F64Const(u.arbitrary()?),
                        ValType::ExternRef => Instruction::RefNull(ValType::ExternRef),
                        ValType::FuncRef => {
                            if num_funcs > 0 && u.arbitrary()? {
                                let func = u.int_in_range(0..=num_funcs - 1)?;
                                Instruction::RefFunc(func)
                            } else {
                                Instruction::RefNull(ValType::FuncRef)
                            }
                        }
                    })
                }));

                for (i, g) in self.globals.iter().enumerate() {
                    if !g.mutable && g.val_type == ty.val_type {
                        choices.push(Box::new(move |_, _| Ok(Instruction::GlobalGet(i as u32))));
                    }
                }

                let f = u.choose(&choices)?;
                let expr = f(u, ty.val_type)?;
                let global_idx = self.globals.len() as u32;
                self.globals.push(ty);
                self.defined_globals.push((global_idx, expr));
                Ok(true)
            },
        )
    }

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

        // Build up a list of candidates for each class of import
        let mut choices: Vec<Vec<Export>> = Vec::with_capacity(6);
        choices.push(
            (0..self.funcs.len())
                .map(|i| Export::Func(i as u32))
                .collect(),
        );
        choices.push(
            (0..self.tables.len())
                .map(|i| Export::Table(i as u32))
                .collect(),
        );
        choices.push(
            (0..self.memories.len())
                .map(|i| Export::Memory(i as u32))
                .collect(),
        );
        choices.push(
            (0..self.globals.len())
                .map(|i| Export::Global(i as u32))
                .collect(),
        );
        choices.push(
            (0..self.instances.len())
                .map(|i| Export::Instance(i as u32))
                .collect(),
        );
        choices.push(
            (0..self.modules.len())
                .map(|i| Export::Module(i as u32))
                .collect(),
        );

        let mut export_names = HashSet::new();
        arbitrary_loop(
            u,
            self.config.min_exports(),
            self.config.max_exports(),
            |u| {
                // Remove all candidates for export whose type size exceeds our
                // remaining budget for type size. Then also remove any classes
                // of exports which no longer have any candidates.
                //
                // If there's nothing remaining after this, then we're done.
                let max_size = self.config.max_type_size() - self.type_size;
                for list in choices.iter_mut() {
                    list.retain(|c| self.type_of(c).size() + 1 < max_size);
                }
                choices.retain(|list| list.len() > 0);
                if choices.len() == 0 {
                    return Ok(false);
                }

                // Pick a name, then pick the export, and then we can record
                // information about the chosen export.
                let name = unique_string(1_000, &mut export_names, u)?;
                let list = u.choose(&choices)?;
                let export = u.choose(list)?;
                let ty = self.type_of(export);
                self.type_size += 1 + ty.size();
                self.exports.push((name, *export));
                Ok(true)
            },
        )
    }

    fn arbitrary_start(&mut self, u: &mut Unstructured) -> Result<()> {
        if !self.config.allow_start_export() {
            return Ok(());
        }

        let mut choices = Vec::with_capacity(self.funcs.len() as usize);

        for (func_idx, ty) in self.funcs() {
            if ty.params.is_empty() && ty.results.is_empty() {
                choices.push(func_idx);
            }
        }

        if !choices.is_empty() && u.arbitrary().unwrap_or(false) {
            let f = *u.choose(&choices)?;
            self.start = Some(f);
        }

        Ok(())
    }

    fn arbitrary_elems(&mut self, u: &mut Unstructured) -> Result<()> {
        let func_max = self.funcs.len() as u32;
        let table_tys = self.tables.iter().map(|t| t.elem_ty).collect::<Vec<_>>();

        // Create a helper closure to choose an arbitrary offset.
        let mut offset_global_choices = vec![];
        for (i, g) in self.globals.iter().enumerate() {
            if !g.mutable && g.val_type == ValType::I32 {
                offset_global_choices.push(i as u32);
            }
        }
        let arbitrary_offset = |u: &mut Unstructured| {
            Ok(if !offset_global_choices.is_empty() && u.arbitrary()? {
                let g = u.choose(&offset_global_choices)?;
                Instruction::GlobalGet(*g)
            } else {
                Instruction::I32Const(u.arbitrary()?)
            })
        };

        let mut choices: Vec<Box<dyn Fn(&mut Unstructured) -> Result<(ElementKind, ValType)>>> =
            Vec::new();

        if table_tys.len() > 0 {
            // If we have at least one table, then the MVP encoding is always
            // available so long as it's a funcref table.
            if table_tys[0] == ValType::FuncRef {
                choices.push(Box::new(|u| {
                    Ok((
                        ElementKind::Active {
                            table: None,
                            offset: arbitrary_offset(u)?,
                        },
                        table_tys[0],
                    ))
                }));
            }

            // If we have reference types enabled, then we can initialize any
            // table, and we can also use the alternate encoding to initialize
            // the 0th table.
            if self.config.reference_types_enabled() {
                choices.push(Box::new(|u| {
                    let i = u.int_in_range(0..=table_tys.len() - 1)? as u32;
                    Ok((
                        ElementKind::Active {
                            table: Some(i),
                            offset: arbitrary_offset(u)?,
                        },
                        table_tys[i as usize],
                    ))
                }));
            }
        }

        // Reference types allows us to create passive and declared element
        // segments.
        if self.config.reference_types_enabled() {
            choices.push(Box::new(|_| Ok((ElementKind::Passive, ValType::FuncRef))));
            choices.push(Box::new(|_| Ok((ElementKind::Passive, ValType::ExternRef))));
            choices.push(Box::new(|_| Ok((ElementKind::Declared, ValType::FuncRef))));
            choices.push(Box::new(|_| {
                Ok((ElementKind::Declared, ValType::ExternRef))
            }));
        }

        if choices.is_empty() {
            return Ok(());
        }

        arbitrary_loop(
            u,
            self.config.min_element_segments(),
            self.config.max_element_segments(),
            |u| {
                // Choose whether to generate a segment whose elements are initialized via
                // expressions, or one whose elements are initialized via function indices.
                let (kind, ty) = u.choose(&choices)?(u)?;
                let items = if ty == ValType::ExternRef
                    || (self.config.reference_types_enabled() && u.arbitrary()?)
                {
                    let mut init = vec![];
                    arbitrary_loop(
                        u,
                        self.config.min_elements(),
                        self.config.max_elements(),
                        |u| {
                            init.push(
                                if ty == ValType::ExternRef || func_max == 0 || u.arbitrary()? {
                                    None
                                } else {
                                    Some(u.int_in_range(0..=func_max - 1)?)
                                },
                            );
                            Ok(true)
                        },
                    )?;
                    Elements::Expressions(init)
                } else {
                    let mut init = vec![];
                    if func_max > 0 {
                        arbitrary_loop(
                            u,
                            self.config.min_elements(),
                            self.config.max_elements(),
                            |u| {
                                let func_idx = u.int_in_range(0..=func_max - 1)?;
                                init.push(func_idx);
                                Ok(true)
                            },
                        )?;
                    }
                    Elements::Functions(init)
                };

                self.elems.push(ElementSegment { kind, ty, items });
                Ok(true)
            },
        )
    }

    fn arbitrary_code(&mut self, u: &mut Unstructured, allow_invalid: bool) -> Result<()> {
        self.code.reserve(self.num_defined_funcs);
        let mut allocs = CodeBuilderAllocations::new(self);
        for (_, ty) in self.funcs[self.funcs.len() - self.num_defined_funcs..].iter() {
            let body = self.arbitrary_func_body(u, ty, &mut allocs, allow_invalid)?;
            self.code.push(body);
        }
        Ok(())
    }

    fn arbitrary_func_body(
        &self,
        u: &mut Unstructured,
        ty: &FuncType,
        allocs: &mut CodeBuilderAllocations<C>,
        allow_invalid: bool,
    ) -> Result<Code> {
        let locals = self.arbitrary_locals(u)?;
        let builder = allocs.builder(ty, &locals);
        let instructions = if allow_invalid && u.arbitrary().unwrap_or(false) {
            Instructions::Arbitrary(arbitrary_vec_u8(u)?)
        } else {
            Instructions::Generated(builder.arbitrary(u, self)?)
        };

        Ok(Code {
            locals,
            instructions,
        })
    }

    fn arbitrary_locals(&self, u: &mut Unstructured) -> Result<Vec<ValType>> {
        let mut ret = Vec::new();
        arbitrary_loop(u, 0, 100, |u| {
            ret.push(self.arbitrary_valtype(u)?);
            Ok(true)
        })?;
        Ok(ret)
    }

    fn arbitrary_data(&mut self, u: &mut Unstructured) -> Result<()> {
        // With bulk-memory we can generate passive data, otherwise if there are
        // no memories we can't generate any data.
        let memories = self.memories.len() as u32;
        if memories == 0 && !self.config.bulk_memory_enabled() {
            return Ok(());
        }

        let mut choices: Vec<Box<dyn Fn(&mut Unstructured) -> Result<Instruction>>> = vec![];

        arbitrary_loop(
            u,
            self.config.min_data_segments(),
            self.config.max_data_segments(),
            |u| {
                if choices.is_empty() {
                    choices.push(Box::new(|u| Ok(Instruction::I32Const(u.arbitrary()?))));

                    for (i, g) in self.globals[..self.globals.len() - self.defined_globals.len()]
                        .iter()
                        .enumerate()
                    {
                        if !g.mutable && g.val_type == ValType::I32 {
                            choices.push(Box::new(move |_| Ok(Instruction::GlobalGet(i as u32))));
                        }
                    }
                }

                // Passive data can only be generated if bulk memory is enabled.
                // Otherwise if there are no memories we *only* generate passive
                // data. Finally if all conditions are met we use an input byte to
                // determine if it should be passive or active.
                let kind =
                    if self.config.bulk_memory_enabled() && (memories == 0 || u.arbitrary()?) {
                        DataSegmentKind::Passive
                    } else {
                        let f = u.choose(&choices)?;
                        let offset = f(u)?;
                        let memory_index = u.int_in_range(0..=memories - 1)?;
                        DataSegmentKind::Active {
                            offset,
                            memory_index,
                        }
                    };
                let init = u.arbitrary()?;
                self.data.push(DataSegment { kind, init });
                Ok(true)
            },
        )
    }

    /// Returns a candidate list of `Export` entities which are items in this
    /// module which match the type of `expected`.
    ///
    /// This function is used to build candidates for instantiation of a module.
    /// The module's imported type is provided with `expected` and this function
    /// will walk over all up-to-this-point defined items in the module and
    /// return if any are candidates for supplying to that requested import.
    fn subtypes(&self, skip: &Entities, expected: &EntityType) -> Vec<Export> {
        let mut ret = Vec::new();
        match expected {
            EntityType::Global(expected) => {
                for (i, actual) in self.globals.iter().enumerate().skip(skip.globals) {
                    if self.is_subtype_global(actual, expected) {
                        ret.push(Export::Global(i as u32));
                    }
                }
            }
            EntityType::Memory(expected) => {
                for (i, actual) in self.memories.iter().enumerate().skip(skip.memories) {
                    if self.is_subtype_memory(actual, expected) {
                        ret.push(Export::Memory(i as u32));
                    }
                }
            }
            EntityType::Table(expected) => {
                for (i, actual) in self.tables.iter().enumerate().skip(skip.tables) {
                    if self.is_subtype_table(actual, expected) {
                        ret.push(Export::Table(i as u32));
                    }
                }
            }
            EntityType::Func(_, expected) => {
                for (i, (_, actual)) in self.funcs.iter().enumerate().skip(skip.funcs) {
                    if self.is_subtype_func(actual, expected) {
                        ret.push(Export::Func(i as u32));
                    }
                }
            }
            EntityType::Instance(_, expected) => {
                for (i, actual) in self.instances.iter().enumerate().skip(skip.instances) {
                    if self.is_subtype_instance(actual, expected) {
                        ret.push(Export::Instance(i as u32));
                    }
                }
            }
            EntityType::Module(_, expected) => {
                for (i, actual) in self.modules.iter().enumerate().skip(skip.modules) {
                    if self.is_subtype_module(actual, expected) {
                        ret.push(Export::Module(i as u32));
                    }
                }
            }
        }
        ret
    }

    // Returns whether `a` is a subtype of `b`.
    fn is_subtype(&self, a: &EntityType, b: &EntityType) -> bool {
        match a {
            EntityType::Global(a) => match b {
                EntityType::Global(b) => self.is_subtype_global(a, b),
                _ => false,
            },
            EntityType::Memory(a) => match b {
                EntityType::Memory(b) => self.is_subtype_memory(a, b),
                _ => false,
            },
            EntityType::Table(a) => match b {
                EntityType::Table(b) => self.is_subtype_table(a, b),
                _ => false,
            },
            EntityType::Func(_, a) => match b {
                EntityType::Func(_, b) => self.is_subtype_func(a, b),
                _ => false,
            },
            EntityType::Instance(_, a) => match b {
                EntityType::Instance(_, b) => self.is_subtype_instance(a, b),
                _ => false,
            },
            EntityType::Module(_, a) => match b {
                EntityType::Module(_, b) => self.is_subtype_module(a, b),
                _ => false,
            },
        }
    }

    // https://webassembly.github.io/spec/core/exec/modules.html#globals
    fn is_subtype_global(&self, a: &GlobalType, b: &GlobalType) -> bool {
        a == b
    }

    // https://webassembly.github.io/spec/core/exec/modules.html#memories
    fn is_subtype_memory(&self, a: &MemoryType, b: &MemoryType) -> bool {
        self.is_subtype_limits(&a.limits, &b.limits)
    }

    // https://webassembly.github.io/spec/core/exec/modules.html#tables
    fn is_subtype_table(&self, a: &TableType, b: &TableType) -> bool {
        a.elem_ty == b.elem_ty && self.is_subtype_limits(&a.limits, &b.limits)
    }

    // https://webassembly.github.io/spec/core/exec/modules.html#limits
    fn is_subtype_limits(&self, a: &Limits, b: &Limits) -> bool {
        a.min >= b.min
            && match b.max {
                Some(b_max) => match a.max {
                    Some(a_max) => a_max <= b_max,
                    None => false,
                },
                None => true,
            }
    }

    // https://webassembly.github.io/spec/core/exec/modules.html#functions
    fn is_subtype_func(&self, a: &FuncType, b: &FuncType) -> bool {
        a == b
    }

    // https://github.com/WebAssembly/module-linking/blob/master/proposals/module-linking/Subtyping.md
    fn is_subtype_instance(&self, a: &InstanceType, b: &InstanceType) -> bool {
        self.is_set_subtypes(&a.exports, &b.exports)
    }

    // https://github.com/WebAssembly/module-linking/blob/master/proposals/module-linking/Subtyping.md
    fn is_subtype_module(&self, a: &ModuleType, b: &ModuleType) -> bool {
        self.is_set_subtypes(&a.exports.exports, &b.exports.exports)
            && self.is_set_subtypes(&b.import_types, &a.import_types)
    }

    // https://github.com/WebAssembly/module-linking/blob/master/proposals/module-linking/Subtyping.md
    fn is_set_subtypes(
        &self,
        a: &indexmap::IndexMap<String, EntityType>,
        b: &indexmap::IndexMap<String, EntityType>,
    ) -> bool {
        b.iter().all(|(b_name, b_ty)| match a.get(b_name) {
            Some(a_ty) => self.is_subtype(a_ty, b_ty),
            None => false,
        })
    }
}

pub(crate) fn arbitrary_loop(
    u: &mut Unstructured,
    min: usize,
    max: usize,
    mut f: impl FnMut(&mut Unstructured) -> Result<bool>,
) -> Result<()> {
    assert!(max >= min);
    for _ in 0..min {
        if !f(u)? {
            break;
        }
    }
    for _ in 0..(max - min) {
        let keep_going = u.arbitrary().unwrap_or(false);
        if !keep_going {
            break;
        }

        if !f(u)? {
            break;
        }
    }

    Ok(())
}

// Mirror what happens in `Arbitrary for String`, but do so with a clamped size.
fn limited_string(max_size: usize, u: &mut Unstructured) -> Result<String> {
    let size = u.arbitrary_len::<u8>()?;
    let size = std::cmp::min(size, max_size);
    match str::from_utf8(&u.peek_bytes(size).unwrap()) {
        Ok(s) => {
            u.bytes(size).unwrap();
            Ok(s.into())
        }
        Err(e) => {
            let i = e.valid_up_to();
            let valid = u.bytes(i).unwrap();
            let s = unsafe {
                debug_assert!(str::from_utf8(valid).is_ok());
                str::from_utf8_unchecked(valid)
            };
            Ok(s.into())
        }
    }
}

fn unique_string(
    max_size: usize,
    names: &mut HashSet<String>,
    u: &mut Unstructured,
) -> Result<String> {
    let mut name = limited_string(max_size, u)?;
    while names.contains(&name) {
        name.push_str(&format!("{}", names.len()));
    }
    names.insert(name.clone());
    Ok(name)
}

fn unique_import_strings(
    max_size: usize,
    import_names: &mut HashMap<String, Option<HashSet<String>>>,
    module_linking_enabled: bool,
    u: &mut Unstructured,
) -> Result<(String, Option<String>)> {
    let mut module = limited_string(max_size, u)?;
    if !module_linking_enabled {
        let field = limited_string(max_size, u)?;
        return Ok((module, Some(field)));
    }
    loop {
        match import_names.get_mut(&module) {
            // This import was previously a bare imported item, so we can't
            // import from the same name. Generate a new name and try again.
            Some(None) => {
                module.push_str(&format!("{}", import_names.len()));
            }

            // This import matches a module previously imported through a
            // two-level syntax, so assume that we'll also be a two-level
            // import and generate a unique name.
            Some(Some(set)) => {
                let field = unique_string(max_size, set, u)?;
                return Ok((module, Some(field)));
            }

            // This is a unique import, we'll insert it in the map below.
            None => break,
        }
    }
    let field = if u.arbitrary()? {
        None
    } else {
        Some(limited_string(1_000, u)?)
    };
    let set = field.as_ref().map(|name| {
        let mut set = HashSet::new();
        set.insert(name.clone());
        set
    });
    assert!(import_names.insert(module.clone(), set).is_none());
    Ok((module, field))
}

fn arbitrary_vec_u8(u: &mut Unstructured) -> Result<Vec<u8>> {
    let size = u.arbitrary_len::<u8>()?;
    Ok(u.bytes(size)?.to_vec())
}

impl EntityType {
    fn size(&self) -> u32 {
        match self {
            EntityType::Global(_) | EntityType::Table(_) | EntityType::Memory(_) => 1,
            EntityType::Func(_, ty) => 1 + (ty.params.len() + ty.results.len()) as u32,
            EntityType::Instance(_, ty) => ty.type_size,
            EntityType::Module(_, ty) => ty.type_size,
        }
    }
}

/// This is a helper structure used during the `arbitrary_initial_sections`
/// phase of generating a module to generate the alias section.
///
/// This structure is dynamically updated with new instances that are available,
/// keeping track of all posssible `Alias` directives we could add to a module.
/// Whenever an instance is defined all of its exports are then candidates for
/// aliasing.
///
/// This then also takes care of filtering where once we reach the maximal size
/// for an entity type all those alias candidates are removed from the pool of
/// choices.
#[derive(Default)]
struct AvailableAliases {
    aliases: Vec<Alias>,
    instances_added: usize,
    outers_processed: bool,
}

impl AvailableAliases {
    fn update(&mut self, module: &ConfiguredModule<impl Config>) {
        // First add in any instances that were created since last time...
        for (instance, ty) in module
            .instances
            .iter()
            .enumerate()
            .skip(self.instances_added)
        {
            self.instances_added += 1;
            let instance = instance as u32;
            for (name, ty) in ty.exports.iter() {
                match ty {
                    EntityType::Global(_) => {
                        self.aliases.push(Alias::InstanceExport {
                            instance,
                            kind: ItemKind::Global,
                            name: name.clone(),
                        });
                    }
                    EntityType::Memory(_) => {
                        self.aliases.push(Alias::InstanceExport {
                            instance,
                            kind: ItemKind::Memory,
                            name: name.clone(),
                        });
                    }
                    EntityType::Func(_, _) => {
                        self.aliases.push(Alias::InstanceExport {
                            instance,
                            kind: ItemKind::Func,
                            name: name.clone(),
                        });
                    }
                    EntityType::Table(_) => {
                        self.aliases.push(Alias::InstanceExport {
                            instance,
                            kind: ItemKind::Table,
                            name: name.clone(),
                        });
                    }
                    EntityType::Instance(_, _) => {
                        self.aliases.push(Alias::InstanceExport {
                            instance,
                            kind: ItemKind::Instance,
                            name: name.clone(),
                        });
                    }
                    EntityType::Module(_, _) => {
                        self.aliases.push(Alias::InstanceExport {
                            instance,
                            kind: ItemKind::Module,
                            name: name.clone(),
                        });
                    }
                }
            }
        }

        // Then add in our all parent's alias candidates, if there are any
        // outers.
        if !self.outers_processed {
            for (i, parent) in module.outers.iter().enumerate() {
                for j in 0..parent.types.len() {
                    self.aliases.push(Alias::OuterType {
                        depth: i as u32,
                        index: j as u32,
                    });
                }
                for j in 0..parent.modules.len() {
                    self.aliases.push(Alias::OuterModule {
                        depth: i as u32,
                        index: j as u32,
                    });
                }
            }
            self.outers_processed = true;
        }

        // And afterwards we need to discard alias candidates that create items
        // which, if created, would exceed our maximum limits.
        self.aliases.retain(|alias| match alias {
            Alias::InstanceExport {
                kind: ItemKind::Global,
                ..
            } => module.globals.len() < module.config.max_globals(),
            Alias::InstanceExport {
                kind: ItemKind::Table,
                ..
            } => module.tables.len() < module.config.max_tables(),
            Alias::InstanceExport {
                kind: ItemKind::Func,
                ..
            } => module.funcs.len() < module.config.max_funcs(),
            Alias::InstanceExport {
                kind: ItemKind::Memory,
                ..
            } => module.memories.len() < module.config.max_memories(),
            Alias::InstanceExport {
                kind: ItemKind::Instance,
                ..
            } => module.instances.len() < module.config.max_instances(),
            Alias::InstanceExport {
                kind: ItemKind::Module,
                ..
            } => module.modules.len() < module.config.max_modules(),
            Alias::OuterType { .. } => module.types.len() < module.config.max_types(),
            Alias::OuterModule { .. } => module.modules.len() < module.config.max_modules(),
        });
    }
}

/// A helper structure to keep track of possible instantiations a module can do
/// at any one point in time.
///
/// This structure is similar to `AvailableAliases` where it is used as part of
/// the `arbitrary_instances` method to generate the module linking instance
/// section. Candidates for instantiation are stored in `choices`, and if that
/// array is empty then there are not possible candidates for instantiation at
/// this time.
///
/// This will be dynamically updated over time with new choices as they become
/// available (e.g. as imports are defined, aliases are defined, etc).
#[derive(Default)]
struct AvailableInstantiations {
    choices: Vec<Instantiation>,
    // Entities that we've visited so far when generating `choices` and
    // populated the uninstantiable list.
    entities: Entities,
}

struct Instantiation {
    /// The module index which can be instantiated.
    module: u32,

    /// Data used to construct the arguments to the `module` above on
    /// instantiation.
    ///
    /// Each sub-vector `args[i]` contains all the valid options for the named
    /// instantiation argument of the `module`.
    ///
    /// In this example, both `$g1` and `$g2` are possible arguments
    /// for `$nested.imported-global`, so the associated `args[i]` would be
    /// `[$g1, $g2]`:
    ///
    /// ```wasm
    /// (module
    ///   (module $nested
    ///     (import $imported-global "g" (mut i32))
    ///   )
    ///   (global $g1 (mut i32) (i32.const 0))
    ///   (global $g2 (mut i32) (i32.const 42))
    /// )
    /// ```
    args: Vec<(String, Vec<Export>)>,
}

impl AvailableInstantiations {
    fn update(&mut self, module: &ConfiguredModule<impl Config>) {
        let cur_entities = Entities {
            globals: module.globals.len(),
            memories: module.memories.len(),
            tables: module.tables.len(),
            funcs: module.funcs.len(),
            modules: module.modules.len(),
            instances: module.instances.len(),
        };

        // If nothing was added since we last checked, there's nothing to check
        if cur_entities == self.entities {
            return;
        }

        // First up we need to update the list of candidates for all our
        // previously possible instantiations. For this we only need to consider
        // items after `self.entities` since the choices already take into
        // account everything prior to that.
        for choice in self.choices.iter_mut() {
            let ty = &module.modules[choice.module as usize];
            for ((_, candidates), ty) in choice.args.iter_mut().zip(ty.import_types.values()) {
                candidates.extend(module.subtypes(&self.entities, ty));
            }
        }

        // Afterwards we need to consider instantiating any new modules added to
        // the module. For this, however, we need to consider all entities in
        // the module since we haven't checked anything prior.
        let empty = Entities::default();
        for i in self.entities.modules..module.modules.len() {
            let ty = &module.modules[i];
            let mut args = Vec::with_capacity(ty.import_types.len());
            for (name, import) in ty.import_types.iter() {
                let candidates = module.subtypes(&empty, import);
                args.push((name.clone(), candidates));
            }

            self.choices.push(Instantiation {
                module: i as u32,
                args,
            });
        }

        // Update the count of all entities we've considered when generating the
        // choices array.
        self.entities = cur_entities;
    }
}

// A helper structure used when generating module/instance types to limit the
// amount of each kind of import created.
#[derive(Default, Clone, Copy, PartialEq)]
struct Entities {
    globals: usize,
    memories: usize,
    tables: usize,
    funcs: usize,
    modules: usize,
    instances: usize,
}

impl Entities {
    fn max_reached(&self, config: &impl Config) -> bool {
        self.globals >= config.max_globals()
            || self.memories >= config.max_memories()
            || self.tables >= config.max_tables()
            || self.funcs >= config.max_funcs()
            || self.modules >= config.max_modules()
            || self.instances >= config.max_instances()
    }
}

#[derive(Clone, Debug)]
enum LocalType {
    /// A type that's locally defined in a module via a type section.
    Defined {
        /// The section (index within `ConfiguredModule::initializers` that this
        /// type is defined.
        section: usize,
        /// Which element within the section definition this type corresponds
        /// to.
        nth: usize,
    },

    /// A type that's aliased from another outer module to be defined in a
    /// module. The type's definition is copied inline here.
    Aliased(Type),
}

#[derive(Debug, Clone)]
struct Outer {
    types: Vec<Type>,
    modules: Vec<Rc<ModuleType>>,
}