#![deny(missing_docs, missing_debug_implementations)]
#![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};
#[derive(Debug, Default, Arbitrary)]
pub struct Module {
inner: ConfiguredModule<DefaultConfig>,
}
#[derive(Debug, Default)]
pub struct ConfiguredModule<C>
where
C: Config,
{
config: C,
valtypes: Vec<ValType>,
initial_sections: Vec<InitialSection>,
types: Vec<(usize, usize)>,
func_types: Vec<u32>,
func_map: HashMap<Rc<FuncType>, Vec<u32>>,
module_types: Vec<u32>,
instance_types: Vec<u32>,
num_imports: usize,
num_aliases: usize,
num_defined_funcs: usize,
num_defined_tables: usize,
num_defined_memories: usize,
defined_globals: Vec<(u32, Instruction)>,
funcs: Vec<(Option<u32>, Rc<FuncType>)>,
tables: Vec<TableType>,
globals: Vec<GlobalType>,
memories: Vec<MemoryType>,
instances: Vec<Rc<InstanceType>>,
modules: Vec<Rc<ModuleType>>,
defined_modules: Vec<ConfiguredModule<C>>,
exports: Vec<(String, Export)>,
start: Option<u32>,
elems: Vec<ElementSegment>,
code: Vec<Code>,
data: Vec<DataSegment>,
}
impl<C: Config> ConfiguredModule<C> {
pub fn config(&self) -> &C {
&self.config
}
}
impl<C: Config> Arbitrary for ConfiguredModule<C> {
fn arbitrary(u: &mut Unstructured) -> Result<Self> {
let mut module = ConfiguredModule::<C>::default();
module.build(u, false)?;
Ok(module)
}
}
#[derive(Debug, Default)]
pub struct MaybeInvalidModule {
module: Module,
}
impl MaybeInvalidModule {
pub fn to_bytes(&self) -> Vec<u8> {
self.module.to_bytes()
}
}
impl Arbitrary for MaybeInvalidModule {
fn arbitrary(u: &mut Unstructured) -> Result<Self> {
let mut module = Module::default();
module.inner.build(u, true)?;
Ok(MaybeInvalidModule { module })
}
}
#[derive(Clone, Debug)]
enum InitialSection {
Type(Vec<Type>),
Import(Vec<(String, Option<String>, EntityType)>),
Alias(Vec<Alias>),
Instance(Vec<Instance>),
Module(Vec<u32>),
}
#[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)]
struct InstanceType {
exports: Vec<(String, EntityType)>,
}
#[derive(Clone, Debug)]
struct ModuleType {
imports: Vec<(String, Option<String>, EntityType)>,
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,
export: Export,
},
#[allow(dead_code)]
ParentType(u32),
#[allow(dead_code)]
ParentModule(u32),
}
#[derive(Clone, Debug)]
struct Instance {
module: u32,
args: Vec<Export>,
}
#[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>,
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 {
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 },
Drop,
Select,
LocalGet(u32),
LocalSet(u32),
LocalTee(u32),
GlobalGet(u32),
GlobalSet(u32),
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),
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();
while u.arbitrary()? {
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() {
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()
&& instantiations.choices.len() > 0
{
choices.push(|u, m, _, i| m.arbitrary_instances(i, u));
}
u.choose(&choices)?(u, self, &mut aliases, &mut instantiations)?;
}
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<()> {
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)?;
let list = match &ty {
Type::Func(f) => {
self.func_map
.entry(f.clone())
.or_insert(Vec::new())
.push(self.types.len() as u32);
&mut self.func_types
}
Type::Module(_) => &mut self.module_types,
Type::Instance(_) => &mut self.instance_types,
};
list.push(self.types.len() as u32);
let types = match self.initial_sections.last_mut().unwrap() {
InitialSection::Type(list) => list,
_ => unreachable!(),
};
self.types.push((section_idx, 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 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)?),
_ => Type::Instance(self.arbitrary_instance_type(u)?),
})
}
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) -> Result<Rc<ModuleType>> {
let exports = self.arbitrary_instance_type(u)?;
let mut imports = Vec::new();
arbitrary_loop(u, 0, self.config.max_imports(), |u| {
let module = limited_string(1_000, u)?;
let name = if self.config.module_linking_enabled() && u.arbitrary()? {
None
} else {
Some(limited_string(1_000, u)?)
};
let ty = self.arbitrary_entity_type(u)?;
imports.push((module, name, ty));
Ok(true)
})?;
Ok(Rc::new(ModuleType { imports, exports }))
}
fn arbitrary_instance_type(&mut self, u: &mut Unstructured) -> Result<Rc<InstanceType>> {
let mut export_names = HashSet::new();
let mut exports = Vec::new();
arbitrary_loop(u, 0, self.config.max_exports(), |u| {
let mut name = limited_string(1_000, u)?;
while export_names.contains(&name) {
name.push_str(&format!("{}", export_names.len()));
}
export_names.insert(name.clone());
let ty = self.arbitrary_entity_type(u)?;
exports.push((name, ty));
Ok(true)
})?;
Ok(Rc::new(InstanceType { exports }))
}
fn arbitrary_entity_type(&mut self, u: &mut Unstructured) -> Result<EntityType> {
let mut choices: Vec<
fn(&mut Unstructured, &mut ConfiguredModule<C>) -> Result<EntityType>,
> = Vec::with_capacity(6);
choices.push(|u, m| Ok(EntityType::Global(m.arbitrary_global_type(u)?)));
choices.push(|u, m| Ok(EntityType::Memory(m.arbitrary_memtype(u)?)));
choices.push(|u, m| Ok(EntityType::Table(m.arbitrary_table_type(u)?)));
if self.func_types.len() > 0 {
choices.push(|u, m| {
let idx = *u.choose(&m.func_types)?;
let ty = m.func_type(idx);
Ok(EntityType::Func(idx, ty.clone()))
});
}
if self.instance_types.len() > 0 {
choices.push(|u, m| {
let idx = *u.choose(&m.instance_types)?;
let ty = m.instance_type(idx);
Ok(EntityType::Instance(idx, ty.clone()))
});
}
if self.module_types.len() > 0 {
choices.push(|u, m| {
let idx = *u.choose(&m.module_types)?;
let ty = m.module_type(idx);
Ok(EntityType::Module(idx, ty.clone()))
});
}
u.choose(&choices)?(u, self)
}
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<()> {
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();
m.funcs.push((Some(idx), ty.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();
m.modules.push(ty.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();
m.instances.push(ty.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)?;
m.globals.push(ty.clone());
Ok(EntityType::Global(ty))
});
}
if self.can_add_local_or_import_memory() {
choices.push(|u, m| {
let ty = m.arbitrary_memtype(u)?;
m.memories.push(ty.clone());
Ok(EntityType::Memory(ty))
});
}
if self.can_add_local_or_import_table() {
choices.push(|u, m| {
let ty = m.arbitrary_table_type(u)?;
m.tables.push(ty.clone());
Ok(EntityType::Table(ty))
});
}
if choices.is_empty() {
return Ok(false);
}
let module = limited_string(1_000, u)?;
let name = if self.config.module_linking_enabled() && u.arbitrary()? {
None
} else {
Some(limited_string(1_000, u)?)
};
let f = u.choose(&choices)?;
let ty = f(u, self)?;
self.num_imports += 1;
imports.push((module, name, ty));
Ok(true)
})?;
if !imports.is_empty() || u.arbitrary()? {
self.initial_sections.push(InitialSection::Import(imports));
}
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, export } => {
let ty = &self.instances[*instance as usize];
match export {
Export::Global(i) => {
let ty = match &ty.exports[*i as usize].1 {
EntityType::Global(t) => t.clone(),
_ => unreachable!(),
};
self.globals.push(ty);
}
Export::Table(i) => {
let ty = match &ty.exports[*i as usize].1 {
EntityType::Table(t) => t.clone(),
_ => unreachable!(),
};
self.tables.push(ty);
}
Export::Memory(i) => {
let ty = match &ty.exports[*i as usize].1 {
EntityType::Memory(t) => t.clone(),
_ => unreachable!(),
};
self.memories.push(ty);
}
Export::Func(i) => {
let (i, ty) = match &ty.exports[*i as usize].1 {
EntityType::Func(i, t) => (*i, t),
_ => unreachable!(),
};
self.funcs.push((Some(i), ty.clone()));
}
Export::Module(i) => {
let ty = match &ty.exports[*i as usize].1 {
EntityType::Module(_, t) => t,
_ => unreachable!(),
};
self.modules.push(ty.clone());
}
Export::Instance(i) => {
let ty = match &ty.exports[*i as usize].1 {
EntityType::Instance(_, t) => t,
_ => unreachable!(),
};
let ty = ty.clone();
self.instances.push(ty);
}
}
}
Alias::ParentType(_) => unimplemented!(),
Alias::ParentModule(_) => unimplemented!(),
}
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<()> {
assert!(available.choices.len() > 0);
let mut instances = Vec::new();
arbitrary_loop(
u,
0,
self.config.max_instances() - self.instances.len(),
|u| {
let choice = u.choose(&available.choices)?;
instances.push(Instance {
module: choice.module,
args: choice
.args
.iter()
.map(|candidates| u.choose(candidates).map(|i| *i))
.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 module = u.arbitrary::<ConfiguredModule<C>>()?;
let mut imports = Vec::with_capacity(module.num_imports);
for (module, name, ty) in module
.initial_sections
.iter()
.filter_map(|section| match section {
InitialSection::Import(list) => Some(list),
_ => None,
})
.flat_map(|a| a)
{
imports.push((module.clone(), name.clone(), ty.clone()));
}
let mut exports = Vec::with_capacity(module.exports.len());
for (name, item) in module.exports.iter() {
let ty = module.type_of(item);
exports.push((name.clone(), ty));
}
let ty = Rc::new(ModuleType {
imports,
exports: Rc::new(InstanceType { exports }),
});
let ty_idx = self.get_module_type_idx(&ty);
modules.push(ty_idx);
self.modules.push(self.module_type(ty_idx).clone());
self.defined_modules.push(module);
Ok(true)
})?;
if !modules.is_empty() || u.arbitrary()? {
self.initial_sections.push(InitialSection::Module(modules));
}
Ok(())
}
fn copy_type_to_self(&mut self, ty: &EntityType) -> EntityType {
match ty {
EntityType::Global(t) => EntityType::Global(t.clone()),
EntityType::Table(t) => EntityType::Table(t.clone()),
EntityType::Memory(t) => EntityType::Memory(t.clone()),
EntityType::Func(_other_idx, sig) => {
EntityType::Func(self.get_func_type_idx(sig), sig.clone())
}
EntityType::Instance(_other_idx, sig) => {
EntityType::Instance(self.get_instance_type_idx(sig), sig.clone())
}
EntityType::Module(_other_idx, sig) => {
EntityType::Module(self.get_module_type_idx(sig), sig.clone())
}
}
}
fn get_func_type_idx(&mut self, sig: &Rc<FuncType>) -> u32 {
if let Some(list) = self.func_map.get(sig) {
return list[0];
}
let type_idx = self.types.len() as u32;
self.func_types.push(type_idx);
self.func_map
.entry(sig.clone())
.or_insert(Vec::new())
.push(type_idx);
self.push_type(Type::Func(sig.clone()));
type_idx
}
fn get_instance_type_idx(&mut self, sig: &Rc<InstanceType>) -> u32 {
let sig = Rc::new(InstanceType {
exports: sig
.exports
.iter()
.map(|(name, ty)| (name.clone(), self.copy_type_to_self(ty)))
.collect(),
});
let type_idx = self.types.len() as u32;
self.instance_types.push(type_idx);
self.push_type(Type::Instance(sig));
type_idx
}
fn get_module_type_idx(&mut self, sig: &Rc<ModuleType>) -> u32 {
let exports_idx = self.get_instance_type_idx(&sig.exports);
let exports = self.instance_type(exports_idx).clone();
let sig = Rc::new(ModuleType {
imports: sig
.imports
.iter()
.map(|(m, n, ty)| (m.clone(), n.clone(), self.copy_type_to_self(ty)))
.collect(),
exports,
});
let type_idx = self.types.len() as u32;
self.module_types.push(type_idx);
self.push_type(Type::Module(sig));
type_idx
}
fn push_type(&mut self, ty: Type) {
let mut i = self.initial_sections.len();
let j = match self.initial_sections.last_mut() {
Some(InitialSection::Type(types)) => {
i -= 1;
types.push(ty);
types.len() - 1
}
_ => {
self.initial_sections.push(InitialSection::Type(vec![ty]));
0
}
};
self.types.push((i, j));
}
fn type_of(&self, item: &Export) -> EntityType {
match *item {
Export::Global(i) => EntityType::Global(self.globals[i as usize].clone()),
Export::Memory(i) => EntityType::Memory(self.memories[i as usize].clone()),
Export::Table(i) => EntityType::Table(self.tables[i as usize].clone()),
Export::Func(i) => {
let (_idx, ty) = &self.funcs[i as usize];
EntityType::Func(u32::max_value(), ty.clone())
}
Export::Module(i) => {
EntityType::Module(u32::max_value(), self.modules[i as usize].clone())
}
Export::Instance(i) => {
EntityType::Instance(u32::max_value(), self.instances[i as usize].clone())
}
}
}
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> {
let (i, j) = self.types[idx as usize];
if let InitialSection::Type(list) = &self.initial_sections[i] {
if let Type::Func(f) = &list[j] {
return f;
}
}
panic!("looked up a function type with the wrong index")
}
fn instance_type(&self, idx: u32) -> &Rc<InstanceType> {
let (i, j) = self.types[idx as usize];
if let InitialSection::Type(list) = &self.initial_sections[i] {
if let Type::Instance(f) = &list[j] {
return f;
}
}
panic!("looked up an instance type with the wrong index")
}
fn module_type(&self, idx: u32) -> &Rc<ModuleType> {
let (i, j) = self.types[idx as usize];
if let InitialSection::Type(list) = &self.initial_sections[i] {
if let Type::Module(f) = &list[j] {
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<()> {
let mut choices: Vec<fn(&mut Unstructured, &mut ConfiguredModule<C>) -> Result<Export>> =
Vec::with_capacity(4);
if self.funcs.len() > 0 {
choices.push(|u, m| {
let idx = u.int_in_range(0..=m.funcs.len() - 1)?;
Ok(Export::Func(idx as u32))
});
}
if self.tables.len() > 0 {
choices.push(|u, m| {
let idx = u.int_in_range(0..=m.tables.len() - 1)?;
Ok(Export::Table(idx as u32))
});
}
if self.memories.len() > 0 {
choices.push(|u, m| {
let idx = u.int_in_range(0..=m.memories.len() - 1)?;
Ok(Export::Memory(idx as u32))
});
}
if self.globals.len() > 0 {
choices.push(|u, m| {
let idx = u.int_in_range(0..=m.globals.len() - 1)?;
Ok(Export::Global(idx as u32))
});
}
if choices.is_empty() {
return Ok(());
}
let mut export_names = HashSet::new();
arbitrary_loop(
u,
self.config.min_exports(),
self.config.max_exports(),
|u| {
let mut name = limited_string(1_000, u)?;
while export_names.contains(&name) {
name.push_str(&format!("{}", export_names.len()));
}
export_names.insert(name.clone());
let f = u.choose(&choices)?;
let export = f(u, self)?;
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<_>>();
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 table_tys[0] == ValType::FuncRef {
choices.push(Box::new(|u| {
Ok((
ElementKind::Active {
table: None,
offset: arbitrary_offset(u)?,
},
table_tys[0],
))
}));
}
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],
))
}));
}
}
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| {
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<()> {
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))));
}
}
}
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)
},
)
}
fn subtypes(&self, expected: &EntityType) -> Vec<Export> {
let mut ret = Vec::new();
match expected {
EntityType::Global(expected) => {
for (i, actual) in self.globals.iter().enumerate() {
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() {
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() {
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() {
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() {
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() {
if self.is_subtype_module(actual, expected) {
ret.push(Export::Module(i as u32));
}
}
}
}
ret
}
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,
},
}
}
fn is_subtype_global(&self, a: &GlobalType, b: &GlobalType) -> bool {
a == b
}
fn is_subtype_memory(&self, a: &MemoryType, b: &MemoryType) -> bool {
self.is_subtype_limits(&a.limits, &b.limits)
}
fn is_subtype_table(&self, a: &TableType, b: &TableType) -> bool {
a.elem_ty == b.elem_ty && self.is_subtype_limits(&a.limits, &b.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,
}
}
fn is_subtype_func(&self, a: &FuncType, b: &FuncType) -> bool {
a == b
}
fn is_subtype_instance(&self, a: &InstanceType, b: &InstanceType) -> bool {
b.exports.iter().all(|(b_name, b_ty)| {
a.exports
.iter()
.any(|(a_name, a_ty)| a_name == b_name && self.is_subtype(a_ty, b_ty))
})
}
fn is_subtype_module(&self, a: &ModuleType, b: &ModuleType) -> bool {
self.is_subtype_instance(&a.exports, &b.exports)
&& a.imports.len() == 0
&& b.imports.len() == 0
}
}
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(())
}
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.get_bytes(size).unwrap();
Ok(s.into())
}
Err(e) => {
let i = e.valid_up_to();
let valid = u.get_bytes(i).unwrap();
let s = unsafe {
debug_assert!(str::from_utf8(valid).is_ok());
str::from_utf8_unchecked(valid)
};
Ok(s.into())
}
}
}
fn arbitrary_vec_u8(u: &mut Unstructured) -> Result<Vec<u8>> {
let size = u.arbitrary_len::<u8>()?;
Ok(u.get_bytes(size)?.to_vec())
}
#[derive(Default)]
struct AvailableAliases {
aliases: Vec<Alias>,
instances_added: usize,
}
impl AvailableAliases {
fn update(&mut self, module: &ConfiguredModule<impl Config>) {
for (instance, ty) in module
.instances
.iter()
.enumerate()
.skip(self.instances_added)
{
self.instances_added += 1;
let instance = instance as u32;
for (i, (_, ty)) in ty.exports.iter().enumerate() {
match ty {
EntityType::Global(_) => {
self.aliases.push(Alias::InstanceExport {
instance,
export: Export::Global(i as u32),
});
}
EntityType::Memory(_) => {
self.aliases.push(Alias::InstanceExport {
instance,
export: Export::Memory(i as u32),
});
}
EntityType::Func(_, _) => {
self.aliases.push(Alias::InstanceExport {
instance,
export: Export::Func(i as u32),
});
}
EntityType::Table(_) => {
self.aliases.push(Alias::InstanceExport {
instance,
export: Export::Table(i as u32),
});
}
EntityType::Instance(_, _) => {
self.aliases.push(Alias::InstanceExport {
instance,
export: Export::Instance(i as u32),
});
}
EntityType::Module(_, _) => {
self.aliases.push(Alias::InstanceExport {
instance,
export: Export::Module(i as u32),
});
}
}
}
}
self.aliases.retain(|alias| match alias {
Alias::InstanceExport {
export: Export::Global(_),
..
} => module.globals.len() < module.config.max_globals(),
Alias::InstanceExport {
export: Export::Table(_),
..
} => module.tables.len() < module.config.max_tables(),
Alias::InstanceExport {
export: Export::Func(_),
..
} => module.funcs.len() < module.config.max_funcs(),
Alias::InstanceExport {
export: Export::Memory(_),
..
} => module.memories.len() < module.config.max_memories(),
Alias::InstanceExport {
export: Export::Instance(_),
..
} => module.instances.len() < module.config.max_instances(),
Alias::InstanceExport {
export: Export::Module(_),
..
} => module.modules.len() < module.config.max_modules(),
Alias::ParentType(_) => module.types.len() < module.config.max_types(),
Alias::ParentModule(_) => module.modules.len() < module.config.max_modules(),
});
}
}
#[derive(Default)]
struct AvailableInstantiations {
choices: Vec<Instantiation>,
}
struct Instantiation {
module: u32,
args: Vec<Vec<Export>>,
}
impl AvailableInstantiations {
fn update(&mut self, module: &ConfiguredModule<impl Config>) {
self.choices.clear();
'outer: for (i, ty) in module.modules.iter().enumerate() {
let mut args = Vec::new();
for (_, _, import) in ty.imports.iter() {
let candidates = module.subtypes(import);
if candidates.is_empty() {
continue 'outer;
}
args.push(candidates);
}
self.choices.push(Instantiation {
module: i as u32,
args,
});
}
}
}