Something went wrong. Try again.
Reggie, the experimental Gleam -> WASM compiler (mirror) reggie.desertthunder.dev
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604//! Validation for the compiler-owned WebAssembly model.//!//! The validator checks module references and instruction semantics before//! binary emission: stack effects, branch labels/results, locals, function and//! call signatures, memories, tables, exports, imports, and data offsets.
use super::builder::*;
#[derive(Debug, Clone)]struct LabelType { branch_results: Vec<ValueType>,}
#[derive(Debug, Clone, PartialEq, Eq)]pub struct ValidationError { pub message: String,}
impl ValidationError { fn new(message: impl Into<String>) -> Self { Self { message: message.into() } }}
pub type ValidationResult<T> = Result<T, Vec<ValidationError>>;
pub struct Validator<'a> { module: &'a Module, errors: Vec<ValidationError>,}
impl<'a> Validator<'a> { pub fn new(module: &'a Module) -> Self { Self { module, errors: Vec::new() } }
pub fn validate(mut self) -> ValidationResult<()> { self.validate_module(); if self.errors.is_empty() { Ok(()) } else { Err(self.errors) } }
fn validate_module(&mut self) { for (id, import) in self.module.imports.iter().enumerate() { self.validate_import(id, import); } for export in &self.module.exports { self.validate_export(export); } for global in &self.module.globals { let mut context = FunctionContext::constant_expression(); if self.validate_sequence(&global.init, &mut context, vec![global.type_]) != Some(vec![global.type_]) { self.error("global initializer must leave its global type on the stack"); } } for segment in &self.module.data_segments { if self.memory_type(segment.memory).is_none() { self.error(format!("unknown memory index {} in data segment", segment.memory.0)); } let mut context = FunctionContext::constant_expression(); if self.validate_sequence(&segment.offset, &mut context, vec![ValueType::I32]) != Some(vec![ValueType::I32]) { self.error("data segment offset must leave one i32 on the stack"); } } for (idx, segment) in self.module.element_segments.iter().enumerate() { if self.table_type(segment.table).is_none() { self.error(format!( "element segment {idx} references unknown table index {}", segment.table.0 )); } for func_id in &segment.functions { if self.function_type(*func_id).is_none() { self.error(format!( "element segment {idx} references unknown function index {}", func_id.0 )); } } } for (defined_index, function) in self.module.functions.iter().enumerate() { self.validate_function(defined_index, function); } }
fn validate_import(&mut self, id: usize, import: &Import) { match &import.desc { ImportDesc::Function(type_id) => { if self.type_(type_id).is_none() { self.error(format!("import {id} references unknown function type {}", type_id.0)); } } ImportDesc::Memory(memory) => self.validate_limits( memory.minimum_pages, memory.maximum_pages, format!("imported memory {id}"), ), ImportDesc::Table(table) => { self.validate_limits(table.minimum, table.maximum, format!("imported table {id}")) } } }
fn validate_export(&mut self, export: &Export) { match export.desc { ExportDesc::Function(id) => { if self.function_type(id).is_none() { self.error(format!( "export `{}` references unknown function index {}", export.name, id.0 )); } } ExportDesc::Memory(id) => { if self.memory_type(id).is_none() { self.error(format!( "export `{}` references unknown memory index {}", export.name, id.0 )); } } ExportDesc::Table(id) => { if self.table_type(id).is_none() { self.error(format!( "export `{}` references unknown table index {}", export.name, id.0 )); } } } }
fn validate_function(&mut self, defined_index: usize, function: &Function) { let Some(type_) = self.type_(&function.type_id).cloned() else { self.error(format!( "function {defined_index} references unknown type {}", function.type_id.0 )); return; };
let params = function.params.iter().map(|local| local.type_).collect::<Vec<_>>(); if params != type_.params { self.error(format!( "function {defined_index} params {:?} do not match signature {:?}", params, type_.params )); }
let mut context = FunctionContext::new( function .params .iter() .chain(&function.locals) .map(|local| local.type_) .collect(), type_.results.clone(), ); let actual = self.validate_sequence(&function.body, &mut context, type_.results.clone()); if let Some(actual) = actual && actual != type_.results { self.error(format!( "function {defined_index} leaves stack {:?}, expected {:?}", actual, type_.results )); } }
fn validate_sequence( &mut self, instructions: &[Instruction], context: &mut FunctionContext, expected: Vec<ValueType>, ) -> Option<Vec<ValueType>> { self.validate_sequence_from(instructions, context, Vec::new(), expected) }
fn validate_sequence_from( &mut self, instructions: &[Instruction], context: &mut FunctionContext, mut stack: Vec<ValueType>, expected: Vec<ValueType>, ) -> Option<Vec<ValueType>> { let mut unreachable = false; for instruction in instructions { if unreachable { stack.clear(); } if !self.validate_instruction(instruction, context, &mut stack, unreachable) { unreachable = true; } }
if unreachable { Some(expected) } else { Some(stack) } }
fn validate_instruction( &mut self, instruction: &Instruction, context: &mut FunctionContext, stack: &mut Vec<ValueType>, unreachable: bool, ) -> bool { if !self.validate_instruction_references(instruction, context) { return true; }
match instruction { Instruction::Block { type_, body } => { self.validate_block_type(type_); if !self.pop_types(stack, &type_.params, instruction, unreachable) { return true; } context.labels.push(LabelType { branch_results: type_.results.clone() }); let actual = self.validate_sequence_from(body, context, type_.params.clone(), type_.results.clone()); context.labels.pop(); if let Some(actual) = actual && actual != type_.results { self.error(format!("block leaves stack {actual:?}, expected {:?}", type_.results)); } stack.extend(type_.results.clone()); true } Instruction::Loop { type_, body } => { self.validate_block_type(type_); if !self.pop_types(stack, &type_.params, instruction, unreachable) { return true; } context.labels.push(LabelType { branch_results: type_.params.clone() }); let actual = self.validate_sequence_from(body, context, type_.params.clone(), type_.results.clone()); context.labels.pop(); if let Some(actual) = actual && actual != type_.results { self.error(format!("loop leaves stack {actual:?}, expected {:?}", type_.results)); } stack.extend(type_.results.clone()); true } Instruction::If { type_, then_body, else_body } => { self.validate_block_type(type_); let mut consumes = type_.params.clone(); consumes.push(ValueType::I32); if !self.pop_types(stack, &consumes, instruction, unreachable) { return true; }
context.labels.push(LabelType { branch_results: type_.results.clone() }); let then_actual = self.validate_sequence_from(then_body, context, type_.params.clone(), type_.results.clone()); let else_actual = self.validate_sequence_from(else_body, context, type_.params.clone(), type_.results.clone()); context.labels.pop();
if let Some(actual) = then_actual && actual != type_.results { self.error(format!( "if then branch leaves stack {actual:?}, expected {:?}", type_.results )); } if let Some(actual) = else_actual && actual != type_.results { self.error(format!( "if else branch leaves stack {actual:?}, expected {:?}", type_.results )); } stack.extend(type_.results.clone()); true } Instruction::Br { depth, results } => { self.validate_branch(*depth, results, context); self.pop_types(stack, results, instruction, unreachable); false } Instruction::BrIf { depth, results } => { self.validate_branch(*depth, results, context); self.apply_stack_effect(stack, instruction, unreachable); true } Instruction::Return { results } => { if results != &context.return_types { self.error(format!( "return has results {results:?}, expected {:?}", context.return_types )); } self.pop_types(stack, results, instruction, unreachable); false } Instruction::Unreachable => false, _ => { self.apply_stack_effect(stack, instruction, unreachable); true } } }
fn validate_instruction_references(&mut self, instruction: &Instruction, context: &FunctionContext) -> bool { let mut valid = true; match instruction { Instruction::Call { function, type_ } => match self.function_type(*function) { Some(actual) if actual == type_ => {} Some(actual) => { self.error(format!( "call to function {} has signature {type_:?}, expected {actual:?}", function.0 )); valid = false; } None => { self.error(format!("call references unknown function index {}", function.0)); valid = false; } }, Instruction::CallName { .. } => {} Instruction::CallIndirect { table, type_id, type_ } => { if self.table_type(*table).is_none() { self.error(format!("call_indirect references unknown table index {}", table.0)); valid = false; } match self.type_(type_id) { Some(actual) if actual == type_ => {} Some(actual) => { self.error(format!( "call_indirect type {type_id:?} is {actual:?}, instruction uses {type_:?}" )); valid = false; } None => { self.error(format!("call_indirect references unknown type index {}", type_id.0)); valid = false; } } } Instruction::LocalGet { local, type_ } | Instruction::LocalSet { local, type_ } | Instruction::LocalTee { local, type_ } => match context.locals.get(local.0 as usize) { Some(actual) if actual == type_ => {} Some(actual) => { self.error(format!( "local {} has type {actual:?}, instruction uses {type_:?}", local.0 )); valid = false; } None => { self.error(format!("instruction references unknown local index {}", local.0)); valid = false; } }, Instruction::GlobalGet { global, type_ } | Instruction::GlobalSet { global, type_ } => { match self.module.globals.get(global.0 as usize) { Some(actual) if actual.type_ == *type_ => {} Some(actual) => { self.error(format!( "global {} has type {:?}, instruction uses {type_:?}", global.0, actual.type_ )); valid = false; } None => { self.error(format!("instruction references unknown global index {}", global.0)); valid = false; } } } Instruction::I32Load(arg) | Instruction::I32Load8U(arg) | Instruction::I32Store(arg) | Instruction::I32Store8(arg) | Instruction::I64Load(arg) | Instruction::I64Store(arg) | Instruction::F64Load(arg) | Instruction::F64Store(arg) if self.memory_type(arg.memory).is_none() => { self.error(format!( "memory instruction references unknown memory index {}", arg.memory.0 )); valid = false; } Instruction::MemorySize(memory) | Instruction::MemoryGrow(memory) if self.memory_type(*memory).is_none() => { self.error(format!( "memory instruction references unknown memory index {}", memory.0 )); valid = false; } _ => {} } valid }
fn apply_stack_effect(&mut self, stack: &mut Vec<ValueType>, instruction: &Instruction, unreachable: bool) { let effect = instruction.stack_effect(); if self.pop_types(stack, &effect.consumes, instruction, unreachable) { stack.extend(effect.produces); } }
fn pop_types( &mut self, stack: &mut Vec<ValueType>, expected: &[ValueType], instruction: &Instruction, unreachable: bool, ) -> bool { if unreachable { return true; } if stack.len() < expected.len() { self.error(format!( "stack underflow for {instruction:?}: expected {expected:?}, stack was {stack:?}" )); return false; } let start = stack.len() - expected.len(); if stack[start..] != *expected { self.error(format!( "stack mismatch for {instruction:?}: expected top {expected:?}, stack was {stack:?}" )); return false; } stack.truncate(start); true }
fn validate_block_type(&mut self, type_: &BlockType) { if (type_.params.len() > 0 || type_.results.len() > 1) && self.block_type_id(type_).is_none() { self.error(format!( "block type params {:?} results {:?} must be present in the module type section", type_.params, type_.results )); } }
fn block_type_id(&self, type_: &BlockType) -> Option<TypeId> { let function_type = FunctionType::new(type_.params.clone(), type_.results.clone()); self.module .types .iter() .position(|candidate| candidate == &function_type) .map(|index| TypeId(index as u32)) }
fn validate_branch(&mut self, depth: u32, results: &[ValueType], context: &FunctionContext) { match context.labels.iter().rev().nth(depth as usize) { Some(label) if label.branch_results == results => {} Some(label) => self.error(format!( "branch depth {depth} has results {results:?}, expected {:?}", label.branch_results )), None => self.error(format!("branch references unknown label depth {depth}")), } }
fn type_(&self, id: &TypeId) -> Option<&FunctionType> { self.module.types.get(id.0 as usize) }
fn function_type(&self, id: FunctionId) -> Option<&FunctionType> { let imported_count = self.module.imported_function_count(); let index = id.0 as usize; if index < imported_count { self.module .imports .iter() .filter_map(|import| match import.desc { ImportDesc::Function(type_id) => self.type_(&type_id), ImportDesc::Memory(_) | ImportDesc::Table(_) => None, }) .nth(index) } else { let function = self.module.functions.get(index - imported_count)?; self.type_(&function.type_id) } }
fn memory_type(&self, id: MemoryId) -> Option<&Memory> { let imported_count = self.module.imported_memory_count(); let index = id.0 as usize; if index < imported_count { self.module .imports .iter() .filter_map(|import| match &import.desc { ImportDesc::Memory(memory) => Some(memory), ImportDesc::Function(_) | ImportDesc::Table(_) => None, }) .nth(index) } else { self.module.memories.get(index - imported_count) } }
fn table_type(&self, id: TableId) -> Option<&Table> { let imported_count = self.module.imported_table_count(); let index = id.0 as usize; if index < imported_count { self.module .imports .iter() .filter_map(|import| match &import.desc { ImportDesc::Table(table) => Some(table), ImportDesc::Function(_) | ImportDesc::Memory(_) => None, }) .nth(index) } else { self.module.tables.get(index - imported_count) } }
fn validate_limits(&mut self, minimum: u32, maximum: Option<u32>, item: impl std::fmt::Display) { if let Some(maximum) = maximum && maximum < minimum { self.error(format!("{item} maximum {maximum} is below minimum {minimum}")); } }
fn error(&mut self, message: impl Into<String>) { self.errors.push(ValidationError::new(message)); }}
#[derive(Debug, Clone)]struct FunctionContext { locals: Vec<ValueType>, return_types: Vec<ValueType>, labels: Vec<LabelType>,}
impl FunctionContext { fn new(locals: Vec<ValueType>, return_types: Vec<ValueType>) -> Self { Self { locals, return_types: return_types.clone(), labels: vec![LabelType { branch_results: return_types }] } }
fn constant_expression() -> Self { Self { locals: Vec::new(), return_types: Vec::new(), labels: Vec::new() } }}
#[cfg(test)]mod tests { use crate::source::{SourceFileId, Span}; use crate::wasm::builder;
fn invalid_structured_module(span: Span, body: Vec<builder::Instruction>) -> builder::Module { let mut module = builder::Module::new(); module.source_span = Some(span);
let type_id = module.push_type(builder::FunctionType::new([], [builder::ValueType::I64])); let mut function = builder::Function::new(type_id); function.body = body; module.push_function(function); module }
fn assert_source_spanned_wasm_error(module: &builder::Module, expected: &str, span: Span) { let errors = module .structured_wat() .expect_err("invalid module should fail before byte emission"); assert!( errors.iter().any(|diagnostic| diagnostic.message.contains(expected)), "{errors:?}" ); assert!( errors .iter() .any(|diagnostic| diagnostic.labels.iter().any(|label| label.span == span)), "{errors:?}" ); }
#[test] fn backend_validation_reports_source_spanned_stack_diagnostics() { let span = Span::new(SourceFileId(0), 5, 9); let module = invalid_structured_module(span, vec![builder::Instruction::I32Const(1)]); assert_source_spanned_wasm_error(&module, "leaves stack", span); }
#[test] fn backend_validation_reports_source_spanned_signature_diagnostics() { let span = Span::new(SourceFileId(0), 10, 14); let mut module = invalid_structured_module( span, vec![builder::Instruction::Call { function: builder::FunctionId(0), type_: builder::FunctionType::new([], [builder::ValueType::I32]), }], );
module.functions[0].body.push(builder::Instruction::I64Const(0)); assert_source_spanned_wasm_error(&module, "call to function 0 has signature", span); }
#[test] fn backend_validation_reports_source_spanned_local_diagnostics() { let span = Span::new(SourceFileId(0), 15, 20); let module = invalid_structured_module( span, vec![builder::Instruction::LocalGet { local: builder::LocalId(9), type_: builder::ValueType::I64 }], ); assert_source_spanned_wasm_error(&module, "unknown local index", span); }}