feat: start work on 'real' interpreter

Signed-off-by: Henry Gressmann <mail@henrygressmann.de>

11 files changed, 269 insertions, 129 deletions

diff --git a/crates/cli/bin.rs b/crates/cli/bin.rs
index 38e30da..6875eac 100644
--- a/crates/cli/bin.rs
+++ b/crates/cli/bin.rs
@@ -1,6 +1,6 @@
 use argh::FromArgs;
 use color_eyre::eyre::Result;
-use tinywasm::{self, module::WasmValue, Module};
+use tinywasm::{self, Module, WasmValue};
 use util::install_tracing;
 
 mod util;
@@ -45,11 +45,11 @@ fn main() -> Result<()> {
 fn run(wasm: &[u8]) -> Result<()> {
     let mut module = Module::new(wasm)?;
     let args = [WasmValue::I32(1), WasmValue::I32(2)];
-    let res = module.run("add", &args)?;
+    let res = tinywasm::naive_runtime::run(&mut module, "add", &args)?;
     println!("res: {:?}", res);
 
     let args = [WasmValue::I64(1), WasmValue::I64(2)];
-    let res = module.run("add_64", &args)?;
+    let res = tinywasm::naive_runtime::run(&mut module, "add_64", &args)?;
     println!("res: {:?}", res);
 
     Ok(())
diff --git a/crates/tinywasm/src/lib.rs b/crates/tinywasm/src/lib.rs
index 0f97863..6b2cd3f 100644
--- a/crates/tinywasm/src/lib.rs
+++ b/crates/tinywasm/src/lib.rs
@@ -10,6 +10,11 @@ pub mod instructions;
 pub mod module;
 pub use error::*;
 pub use module::Module;
+pub mod types;
+pub use types::*;
+pub mod runtime;
+
+pub mod naive_runtime;
 
 pub struct Store {}
 
@@ -17,7 +22,6 @@ pub struct Instance {}
 
 #[cfg(test)]
 mod tests {
-    use super::*;
     use crate::{error::Result, Module};
 
     #[test]
diff --git a/crates/tinywasm/src/module/mod.rs b/crates/tinywasm/src/module/mod.rs
index 4684254..23c2a93 100644
--- a/crates/tinywasm/src/module/mod.rs
+++ b/crates/tinywasm/src/module/mod.rs
@@ -1,8 +1,7 @@
 use core::fmt::Debug;
 
 use crate::error::{Error, Result};
-use alloc::{format, string::ToString, vec, vec::Vec};
-use tracing::info;
+use alloc::vec::Vec;
 use wasmparser::*;
 
 mod reader;
@@ -36,28 +35,6 @@ impl Debug for Module<'_> {
     }
 }
 
-#[derive(Debug, Clone, PartialEq, Eq)]
-#[non_exhaustive]
-pub enum WasmValue {
-    I32(i32),
-    I64(i64),
-}
-
-impl Into<ValType> for &WasmValue {
-    fn into(self) -> ValType {
-        match self {
-            WasmValue::I32(_) => ValType::I32,
-            WasmValue::I64(_) => ValType::I64,
-        }
-    }
-}
-
-impl WasmValue {
-    pub fn to_type(&self) -> ValType {
-        self.into()
-    }
-}
-
 impl<'data> Module<'data> {
     pub fn new(wasm: &'data [u8]) -> Result<Self> {
         let mut validator = Validator::new();
@@ -74,106 +51,6 @@ impl<'data> Module<'data> {
         Self::from_reader(reader)
     }
 
-    pub fn run(&mut self, func_name: &str, args: &[WasmValue]) -> Result<Vec<WasmValue>> {
-        let func = self
-            .exports
-            .iter()
-            .find(|e| e.name == func_name)
-            .ok_or_else(|| Error::Other(format!("Function {} not found", func_name)))?;
-
-        let func_type_index = self.functions[func.index as usize];
-        let func_type = &self.types[func_type_index as usize];
-
-        info!("func_type: {:#?}", func_type);
-        let code = &mut self.code[func.index as usize];
-        code.allow_memarg64(false);
-
-        let mut locals = vec![];
-        for ty in func_type.params() {
-            locals.push(ty.clone());
-        }
-
-        let mut returns = vec![];
-        for ty in func_type.results() {
-            returns.push(ty.clone());
-        }
-
-        let locals_reader = code.get_locals_reader().unwrap();
-        for local in locals_reader.into_iter() {
-            let local = local.unwrap();
-            if locals.len() != local.0 as usize {
-                panic!("Invalid local index");
-            }
-            locals.push(local.1);
-        }
-
-        let mut body = code.get_operators_reader().unwrap().into_iter();
-
-        let mut local_values = vec![];
-        for (i, arg) in args.iter().enumerate() {
-            if locals[i] != arg.into() {
-                return Error::other(&format!(
-                    "Invalid argument type for {}, index {}: expected {:?}, got {:?}",
-                    func_name,
-                    i,
-                    locals[i],
-                    arg.to_type()
-                ));
-            }
-
-            local_values.push(arg);
-        }
-
-        let mut stack: Vec<WasmValue> = vec![];
-        while let Some(op) = body.next() {
-            let op = op.unwrap();
-            info!("op: {:#?}", op);
-
-            match op {
-                Operator::LocalGet { local_index } => {
-                    let local = locals.get(local_index as usize).unwrap();
-                    let val = local_values[local_index as usize];
-                    info!("local: {:#?}", local);
-                    stack.push(val.clone());
-                }
-                Operator::I64Add => {
-                    let a = stack.pop().unwrap();
-                    let b = stack.pop().unwrap();
-                    let (WasmValue::I64(a), WasmValue::I64(b)) = (a, b) else {
-                        panic!("Invalid type");
-                    };
-                    let c = WasmValue::I64(a + b);
-                    stack.push(c);
-                }
-                Operator::I32Add => {
-                    let a = stack.pop().unwrap();
-                    let b = stack.pop().unwrap();
-                    let (WasmValue::I32(a), WasmValue::I32(b)) = (a, b) else {
-                        panic!("Invalid type");
-                    };
-                    let c = WasmValue::I32(a + b);
-                    stack.push(c);
-                }
-                Operator::End => {
-                    info!("stack: {:#?}", stack);
-                    let res = returns
-                        .iter()
-                        .map(|ty| {
-                            let val = stack.pop()?;
-                            (ty == &val.to_type()).then(|| val)
-                        })
-                        .collect::<Option<Vec<_>>>()
-                        .ok_or_else(|| Error::Other("Invalid return type".to_string()))?;
-
-                    return Ok(res);
-                }
-                _ => {}
-            }
-        }
-
-        return Error::other("End not reached");
-    }
-
     fn from_reader(reader: ModuleReader<'data>) -> Result<Self> {
         let types = reader
             .type_section
diff --git a/crates/tinywasm/src/module/reader.rs b/crates/tinywasm/src/module/reader.rs
index 7ecfddf..5ccadea 100644
--- a/crates/tinywasm/src/module/reader.rs
+++ b/crates/tinywasm/src/module/reader.rs
@@ -149,7 +149,7 @@ impl<'a> ModuleReader<'a> {
             x => Error::other(&format!("Unknown payload: {:?}", x))?,
         };
 
-        return Ok(());
+        Ok(())
     }
 
     // fn exports(&mut self) -> Result<Vec<Export>> {
diff --git a/crates/tinywasm/src/naive_runtime.rs b/crates/tinywasm/src/naive_runtime.rs
new file mode 100644
index 0000000..6e6c709
--- /dev/null
+++ b/crates/tinywasm/src/naive_runtime.rs
@@ -0,0 +1,104 @@
+use alloc::{format, string::ToString, vec, vec::Vec};
+use tracing::info;
+use wasmparser::Operator;
+
+use crate::{Error, Module, Result, WasmValue};
+
+pub fn run(module: &mut Module, func_name: &str, args: &[WasmValue]) -> Result<Vec<WasmValue>> {
+    let func = module
+        .exports
+        .iter()
+        .find(|e| e.name == func_name)
+        .ok_or_else(|| Error::Other(format!("Function {} not found", func_name)))?;
+
+    let func_type_index = module.functions[func.index as usize];
+    let func_type = &module.types[func_type_index as usize];
+
+    info!("func_type: {:#?}", func_type);
+    let code = &mut module.code[func.index as usize];
+    code.allow_memarg64(false);
+
+    let mut locals = vec![];
+    for ty in func_type.params() {
+        locals.push(*ty);
+    }
+
+    let mut returns = vec![];
+    for ty in func_type.results() {
+        returns.push(*ty);
+    }
+
+    let locals_reader = code.get_locals_reader().unwrap();
+    for local in locals_reader.into_iter() {
+        let local = local.unwrap();
+        if locals.len() != local.0 as usize {
+            panic!("Invalid local index");
+        }
+        locals.push(local.1);
+    }
+
+    let mut local_values = vec![];
+    let body = code.get_operators_reader().unwrap().into_iter();
+    for (i, arg) in args.iter().enumerate() {
+        if !arg.is(locals[i]) {
+            return Error::other(&format!(
+                "Invalid argument type for {}, index {}: expected {:?}, got {:?}",
+                func_name,
+                i,
+                locals[i],
+                arg.type_of()
+            ));
+        }
+
+        local_values.push(arg);
+    }
+
+    let mut stack: Vec<WasmValue> = vec![];
+    for op in body {
+        let op = op.unwrap();
+        info!("op: {:#?}", op);
+
+        match op {
+            Operator::LocalGet { local_index } => {
+                let local = locals.get(local_index as usize).unwrap();
+                let val = local_values[local_index as usize];
+                info!("local: {:#?}", local);
+                stack.push(val.clone());
+            }
+            Operator::I64Add => {
+                let a = stack.pop().unwrap();
+                let b = stack.pop().unwrap();
+                let (WasmValue::I64(a), WasmValue::I64(b)) = (a, b) else {
+                    panic!("Invalid type");
+                };
+                let c = WasmValue::I64(a + b);
+                stack.push(c);
+            }
+            Operator::I32Add => {
+                let a = stack.pop().unwrap();
+                let b = stack.pop().unwrap();
+                let (WasmValue::I32(a), WasmValue::I32(b)) = (a, b) else {
+                    panic!("Invalid type");
+                };
+                let c = WasmValue::I32(a + b);
+                stack.push(c);
+            }
+            Operator::End => {
+                info!("stack: {:#?}", stack);
+                let res = returns
+                    .iter()
+                    .map(|ty| {
+                        let val = stack.pop()?;
+                        (val.is(*ty)).then_some(val)
+                    })
+                    .collect::<Option<Vec<_>>>()
+                    .ok_or_else(|| Error::Other("Invalid return type".to_string()))?;
+
+                return Ok(res);
+            }
+            _ => {}
+        }
+    }
+
+    Error::other("End not reached")
+}
diff --git a/crates/tinywasm/src/runtime/mod.rs b/crates/tinywasm/src/runtime/mod.rs
new file mode 100644
index 0000000..0504365
--- /dev/null
+++ b/crates/tinywasm/src/runtime/mod.rs
@@ -0,0 +1,6 @@
+mod stack;
+mod store;
+mod types;
+pub use stack::*;
+pub use store::*;
+pub use types::*;
diff --git a/crates/tinywasm/src/runtime/stack/call.rs b/crates/tinywasm/src/runtime/stack/call.rs
new file mode 100644
index 0000000..a58e2ef
--- /dev/null
+++ b/crates/tinywasm/src/runtime/stack/call.rs
@@ -0,0 +1,8 @@
+use alloc::vec::Vec;
+
+pub struct CallFrame {
+    pub instr_ptr: usize,
+    pub func_ptr: usize,
+
+    pub local_addrs: Vec<usize>,
+}
diff --git a/crates/tinywasm/src/runtime/stack/mod.rs b/crates/tinywasm/src/runtime/stack/mod.rs
new file mode 100644
index 0000000..68f02ff
--- /dev/null
+++ b/crates/tinywasm/src/runtime/stack/mod.rs
@@ -0,0 +1,23 @@
+use crate::WasmValue;
+use alloc::vec::Vec;
+
+mod call;
+pub use call::CallFrame;
+
+pub const STACK_SIZE: usize = 1024;
+
+/// A WebAssembly Stack
+pub struct Stack {
+    /// Locals
+    // TODO: maybe store the locals on the stack instead?
+    pub locals: Vec<WasmValue>,
+
+    /// The value stack
+    // TODO: Split into Vec<u8> and Vec<ValType> for better memory usage?
+    pub value_stack: Vec<WasmValue>, // keeping this typed for now to make it easier to debug
+    pub value_stack_top: usize,
+
+    /// The call stack
+    pub call_stack: Vec<CallFrame>,
+    pub call_stack_top: usize,
+}
diff --git a/crates/tinywasm/src/runtime/store.rs b/crates/tinywasm/src/runtime/store.rs
new file mode 100644
index 0000000..cf0163b
--- /dev/null
+++ b/crates/tinywasm/src/runtime/store.rs
@@ -0,0 +1,14 @@
+use alloc::vec::Vec;
+
+use super::FuncInst;
+
+/// global state that can be manipulated by WebAssembly programs
+/// https://webassembly.github.io/spec/core/exec/runtime.html#store
+pub struct Store {
+    pub funcs: Vec<FuncInst>,
+    // tables: Vec<TableType>,
+    // mems: Vec<MemoryType>,
+    // globals: Vec<GlobalType>,
+    // elems: Vec<Element>,
+    // data: Vec<Data>,
+}
diff --git a/crates/tinywasm/src/runtime/types.rs b/crates/tinywasm/src/runtime/types.rs
new file mode 100644
index 0000000..a9be605
--- /dev/null
+++ b/crates/tinywasm/src/runtime/types.rs
@@ -0,0 +1,67 @@
+use alloc::{string::String, vec::Vec};
+use wasmparser::{FuncType, OperatorsIterator, ValType};
+
+/// A WebAssembly Label
+pub struct Label(Addr);
+
+/// A WebAssembly Address.
+/// These are indexes into the respective stores.
+/// See https://webassembly.github.io/spec/core/exec/runtime.html#addresses
+pub type Addr = u32;
+pub struct FuncAddr(pub Addr);
+pub struct TableAddr(pub Addr);
+pub struct MemAddr(pub Addr);
+pub struct GlobalAddr(pub Addr);
+pub struct ElmAddr(pub Addr);
+pub struct DataAddr(pub Addr);
+pub struct ExternAddr(pub Addr);
+
+/// A WebAssembly Module Instance.
+/// See https://webassembly.github.io/spec/core/exec/runtime.html#module-instances
+pub struct ModuleInstance {
+    pub types: Vec<FuncType>,
+    pub func_addrs: Vec<FuncAddr>,
+    pub table_addrs: Vec<TableAddr>,
+    pub mem_addrs: Vec<MemAddr>,
+    pub global_addrs: Vec<GlobalAddr>,
+    pub elem_addrs: Vec<ElmAddr>,
+    pub data_addrs: Vec<DataAddr>,
+    pub exports: Vec<ExportInst>,
+}
+
+/// A WebAssembly Function Instance.
+/// See https://webassembly.github.io/spec/core/exec/runtime.html#function-instances
+pub enum FuncInst {
+    Host(HostFunc),
+    Module(ModuleFunc),
+}
+pub struct HostFunc {
+    pub ty: FuncType,
+    pub hostcode: fn() -> (),
+}
+pub struct ModuleFunc {
+    pub ty: FuncType,
+    pub module: ModuleInstance,
+    pub code: FuncAddr,
+}
+pub struct Func<'a> {
+    pub ty: FuncType,
+    pub locals: Vec<ValType>,
+    pub body: Vec<OperatorsIterator<'a>>,
+}
+
+/// A WebAssembly Export Instance.
+/// https://webassembly.github.io/spec/core/exec/runtime.html#export-instances
+pub struct ExportInst {
+    pub name: String,
+    pub value: ExternVal,
+}
+
+/// A WebAssembly External Value.
+/// https://webassembly.github.io/spec/core/exec/runtime.html#external-values
+pub enum ExternVal {
+    Func(FuncAddr),
+    Table(TableAddr),
+    Mem(MemAddr),
+    Global(GlobalAddr),
+}
diff --git a/crates/tinywasm/src/types.rs b/crates/tinywasm/src/types.rs
new file mode 100644
index 0000000..813c6c3
--- /dev/null
+++ b/crates/tinywasm/src/types.rs
@@ -0,0 +1,37 @@
+use wasmparser::ValType;
+
+/// A WebAssembly value.
+/// See https://webassembly.github.io/spec/core/syntax/types.html#value-types
+#[derive(Debug, Clone, PartialEq)]
+pub enum WasmValue {
+    // Num types
+    I32(i32),
+    I64(i64),
+    F32(f32),
+    F64(f64),
+
+    // Vec types
+    V128(i128),
+}
+
+impl From<WasmValue> for ValType {
+    fn from(wasm_value: WasmValue) -> Self {
+        match wasm_value {
+            WasmValue::I32(_) => ValType::I32,
+            WasmValue::I64(_) => ValType::I64,
+            WasmValue::F32(_) => ValType::F32,
+            WasmValue::F64(_) => ValType::F64,
+            WasmValue::V128(_) => ValType::V128,
+        }
+    }
+}
+
+impl WasmValue {
+    pub fn type_of(&self) -> ValType {
+        self.clone().into()
+    }
+
+    pub fn is(&self, ty: ValType) -> bool {
+        self.type_of() == ty
+    }
+}