From 0efb15a9eb706896cdabb9ca5d2b0c295c2dffcf Mon Sep 17 00:00:00 2001 From: Brian Cully Date: Sun, 24 Aug 2025 14:22:48 -0400 Subject: rename parser → compiler, interp → vm MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit reflects reality better --- main.mjs | 52 ++--- src/forth/compiler.rs | 384 ++++++++++++++++++++++++++++++++++++ src/forth/interp.rs | 532 -------------------------------------------------- src/forth/mod.rs | 24 +-- src/forth/parser.rs | 384 ------------------------------------ src/forth/vm.rs | 532 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 78 ++++---- 7 files changed, 993 insertions(+), 993 deletions(-) create mode 100644 src/forth/compiler.rs delete mode 100644 src/forth/interp.rs mode change 100755 => 100644 src/forth/mod.rs delete mode 100644 src/forth/parser.rs create mode 100644 src/forth/vm.rs diff --git a/main.mjs b/main.mjs index 701659f..9e3e037 100644 --- a/main.mjs +++ b/main.mjs @@ -1,4 +1,4 @@ -import init, { make_interp } from './pkg/automathon.js'; +import init, { make_vm } from './pkg/automathon.js'; function wordlistElts(wordlist) { return wordlist.map((bc, i) => { @@ -25,12 +25,12 @@ function initWordlist() { }); } -function renderStack(interp) { +function renderStack(vm) { document.querySelectorAll('#stack').forEach(e => { while (e.lastChild) { e.removeChild(e.lastChild); } - interp.stack().reverse() + vm.stack().reverse() .forEach(datum => { const elt = document.createElement('li'); elt.textContent = datum; @@ -40,12 +40,12 @@ function renderStack(interp) { }); } -function renderCallStack(interp) { +function renderCallStack(vm) { document.querySelectorAll('#callstack').forEach(e => { while (e.lastChild) { e.removeChild(e.lastChild); } - interp.callstack().reverse() + vm.callstack().reverse() .forEach(datum => { const elt = document.createElement('li'); elt.textContent = `${datum.word}@${datum.offset}`; @@ -59,9 +59,9 @@ const highRange = new Range(); const highlight = new Highlight(highRange); CSS.highlights.set('exec', highlight); -function renderTextHighlight(interp) { - const ip = interp.ip(); - const anno = interp.annotation_at(ip) +function renderTextHighlight(vm) { + const ip = vm.ip(); + const anno = vm.annotation_at(ip) const src = document.querySelector('#src'); // this assumes the text node is the first child, maybe it isn't? @@ -69,27 +69,27 @@ function renderTextHighlight(interp) { highRange.setEnd(src.childNodes[0], anno.end); } -function tick(interp) { - if (!interp.tick()) { - interp.reset_ip(); +function tick(vm) { + if (!vm.tick()) { + vm.reset_ip(); } - const { word, offset } = interp.ip(); + const { word, offset } = vm.ip(); document.querySelectorAll('#wordlist .ip').forEach(e => e.classList.remove('ip')); const sel = selectorForIP(word, offset); document.querySelectorAll(sel).forEach(e => { e.classList.add('ip'); }); - renderStack(interp); - renderCallStack(interp); - renderTextHighlight(interp); + renderStack(vm); + renderCallStack(vm); + renderTextHighlight(vm); } async function loaded() { console.debug('running init'); const mod = await init(); console.debug('init done', mod); - const interp = make_interp(); + const vm = make_vm(); document.querySelector('#compile').onclick = e => { console.debug('compile clicked', e); @@ -104,32 +104,32 @@ async function loaded() { const text = document.querySelector('#src').textContent + '\n'; console.debug('compiling', text); const start = performance.now(); - const res = interp.compile(text); + const res = vm.compile(text); const end = performance.now(); console.info(`compile took ${end-start} ms`); if (res) { - const wordlist = wordlistElts(interp.wordlist()); + const wordlist = wordlistElts(vm.wordlist()); wordlist.forEach(elt => wordlistContainer.appendChild(elt)); initWordlist(); - renderStack(interp); - renderCallStack(interp); - renderTextHighlight(interp); + renderStack(vm); + renderCallStack(vm); + renderTextHighlight(vm); } }; document.querySelector('#tick').onclick = e => { console.debug('tick clicked', e); - tick(interp); + tick(vm); }; document.querySelector('#bench').onclick = e => { console.debug('bench clicked', e); const start = performance.now(); let tickCount = 0; for (let i = 0; i < 1_000_000; i++) { - tickCount += interp.run(); + tickCount += vm.run(); } const end = performance.now(); console.info(`run took ${end-start} ms for ${tickCount} ticks (${(end-start)/tickCount * 1_000_000} ns/tick).`); - console.info('result', interp.stack()); + console.info('result', vm.stack()); }; let blinkenRun = false; @@ -144,13 +144,13 @@ async function loaded() { const frameRate = 6; const onTimeout = _ => { if (blinkenRun) { - tick(interp); + tick(vm); setTimeout(onTimeout, 1_000 / frameRate); } } setTimeout(onTimeout); } - window.interp = interp; + window.vm = vm; } document.addEventListener('DOMContentLoaded', loaded); diff --git a/src/forth/compiler.rs b/src/forth/compiler.rs new file mode 100644 index 0000000..9120506 --- /dev/null +++ b/src/forth/compiler.rs @@ -0,0 +1,384 @@ +use super::vm::{ByteCode, OpCode, WordList}; + +use std::collections::HashMap; +use std::iter::{Enumerate, Iterator}; +use std::str::Chars; + +#[derive(Debug)] +pub enum CompileError { + EOF, + DefStackEmpty, + MissingIf, + MissingQuote, + UnknownWord(String), +} +impl std::fmt::Display for CompileError { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::EOF => write!(f, "premature end-of-file"), + Self::DefStackEmpty => write!(f, "def stack empty"), + Self::MissingIf => write!(f, "missing if"), + Self::MissingQuote => write!(f, "missing ending quote"), + Self::UnknownWord(word) => write!(f, "unknown word: {}", word), + } + } +} +impl std::error::Error for CompileError {} + +type CompileResult = Result; + +// todo: the annotations should be directly tied to the wordlist so +// they can't get out of sync. +#[derive(Debug)] +pub struct Annotation { + // (start, end) index in program text + pub loc: (usize, usize), +} + +#[derive(Debug)] +pub struct WordCatalog<'a>(pub(super) HashMap<&'a str, usize>); + +#[derive(Debug)] +pub enum IfClauses { + True(usize), + TrueFalse(usize, usize), +} + +#[derive(Debug)] +pub struct Compiler<'a> { + text: &'a str, + enumerator: Enumerate>, + // list of all word definitions, in the order defined. the main + // routine is always in the first entry. + // todo: don't be pub, have a method to extract a wordlist + pub wordlist: WordList, + pub annotations: Vec>, + // catalog of word to word index in `wordlist` + pub wordalog: WordCatalog<'a>, + // holds a stack of indices into `wordlist` that are currently + // being defined, with the top of stack being the most recent + // definition. + defstack: Vec, + // number of clauses currently being defined for a particular ‘if’ + // construct. a stack is needed in order to allow for nesting. + if_stack: Vec<(IfClauses, Annotation)>, +} + +impl<'a> Compiler<'a> { + pub fn new(text: &'a str) -> Self { + let mut wl = vec![]; + // main routine is always the first entry. + wl.push(ByteCode(vec![])); + Self { + text, + enumerator: text.chars().enumerate(), + wordlist: WordList(wl), + annotations: vec![vec![]], + wordalog: WordCatalog(HashMap::new()), + defstack: vec![], + if_stack: vec![], + } + } + + // pull the next, whitespace-delimited word off the input stream. + fn next_word(&mut self) -> Option<(&'a str, usize, usize)> { + let (start, _c) = + self.enumerator.by_ref() + .find(|(_i, c)| !c.is_whitespace())?; + let (end, _c) = + self.enumerator.by_ref() + .find(|(_i, c)| c.is_whitespace())?; + let word = &self.text[start..end]; + Some((word, start, end)) + } + + // currently ‘active’ bytecode being built. + fn bc_mut(&mut self) -> &mut ByteCode { + let word_index = self.defstack.last().unwrap_or(&0); + &mut self.wordlist.0[*word_index] + } + + fn bc(&self) -> &ByteCode { + let word_index = self.defstack.last().unwrap_or(&0); + &self.wordlist.0[*word_index] + } + + fn anno_mut(&mut self) -> &mut Vec { + let word_index = self.defstack.last().unwrap_or(&0); + &mut self.annotations[*word_index] + } + + // push `op` onto the currently building bytecode, as determined + // by the top of the `namestack`. + fn bc_push(&mut self, op: OpCode, anno: Annotation) { + self.bc_mut().0.push(op); + self.anno_mut().push(anno); + } + + pub fn compile(&mut self) -> CompileResult<()> { + while let Some((word, start, end)) = self.next_word() { + let anno = Annotation { loc: (start, end) }; + if let Ok(i) = word.parse::() { + self.bc_push(OpCode::Num(i), anno); + } else if let Some(i) = self.wordalog.0.get(word) { + self.bc_push(OpCode::Call(*i), anno); + } else { + match word { + r#"s""# => { + let (s_end, _) = + self.enumerator + .find(|(_i, c)| return *c == '"') + .ok_or(CompileError::MissingQuote)?; + self.bc_push(OpCode::Str(end+1, s_end), anno); + }, + ":" => { + let (name, _, _) = self.next_word().ok_or(CompileError::EOF)?; + self.wordalog.0.insert(name, self.wordlist.0.len()); + self.defstack.push(self.wordlist.0.len()); + self.wordlist.0.push(ByteCode(vec![])); + self.annotations.push(vec![]); + }, + ";" => { + match self.bc().0.last() { + Some(OpCode::Call(i)) => { + let k = *i; + self.bc_mut().0.pop(); + self.bc_mut().0.push(OpCode::TCall(k)); + }, + Some(OpCode::If(t, f)) => { + let t = *t; + let f = *f; + self.bc_mut().0.pop(); + self.bc_mut().0.push(OpCode::TIf(t, f)); + // technically only needed if ‘f’ is None, but whatever. + self.bc_push(OpCode::Ret, anno); + }, + _ => self.bc_push(OpCode::Ret, anno), + } + self.defstack.pop().ok_or(CompileError::DefStackEmpty)?; + }, + "if" => { + let i = self.wordlist.0.len(); + self.wordlist.0.push(ByteCode(vec![])); + self.annotations.push(vec![]); + self.defstack.push(i); + + self.if_stack.push((IfClauses::True(i), anno)); + }, + "else" => { + self.bc_push(OpCode::Ret, anno); + self.defstack.pop(); + + let i = self.wordlist.0.len(); + self.wordlist.0.push(ByteCode(vec![])); + self.annotations.push(vec![]); + self.defstack.push(i); + + let (true_clause, anno) = match self.if_stack.pop() { + None => return Err(CompileError::MissingIf), + Some((IfClauses::TrueFalse(_, _), _)) => return Err(CompileError::MissingIf), + Some((IfClauses::True(cl), anno)) => (cl, anno), + }; + self.if_stack.push((IfClauses::TrueFalse(true_clause, i), anno)); + }, + "then" => { + self.bc_push(OpCode::Ret, anno); + self.defstack.pop(); + + match self.if_stack.pop() { + None => return Err(CompileError::MissingIf), + Some((IfClauses::True(true_clause), anno)) => { + self.bc_push(OpCode::If(true_clause, None), anno); + }, + Some((IfClauses::TrueFalse(true_clause, false_clause), anno)) => { + self.bc_push(OpCode::If(true_clause, Some(false_clause)), anno); + } + } + }, + "+" => self.bc_push(OpCode::Add, anno), + "-" => self.bc_push(OpCode::Sub, anno), + "*" => self.bc_push(OpCode::Mul, anno), + "/" => self.bc_push(OpCode::Div, anno), + "dup" => self.bc_push(OpCode::Dup, anno), + "drop" => self.bc_push(OpCode::Drop, anno), + "=" => self.bc_push(OpCode::EQ, anno), + ">" => self.bc_push(OpCode::GT, anno), + ">=" => self.bc_push(OpCode::GTE, anno), + "<" => self.bc_push(OpCode::LT, anno), + "<=" => self.bc_push(OpCode::LTE, anno), + other => return Err(CompileError::UnknownWord(String::from(other))), + } + } + } + Ok(()) + } +} + +#[cfg(test)] +mod tests { + use super::*; + use super::super::vm::OpCode; + + fn compiler_for(text: &str) -> Compiler { + let mut p = Compiler::new(text); + p.compile().expect("badparse"); + p + } + + fn eprintwordlist(wordlist: &WordList) { + for i in 0..wordlist.0.len() { + eprintln!("wordlist[{}]: {:?}", i, wordlist.0[i]); + } + } + + #[test] + fn literal_num() { + let comp = compiler_for("1\n"); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::Num(1)); + } + + #[test] + fn literal_string() { + let comp = compiler_for(r#"s" hello there""#); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::Str(3, 14)); + } + + #[test] + fn add_opcode() { + let comp = compiler_for("+\n"); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::Add); + } + + #[test] + fn sub_opcode() { + let comp = compiler_for("-\n"); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::Sub); + } + + #[test] + fn def_word() { + let comp = compiler_for(": add2 2 + ; 3 add2\n"); + let main = &comp.wordlist.0[0]; + let add2_index = comp.wordalog.0.get("add2").expect("add2 has entry in wordlist"); + let add2 = &comp.wordlist.0[*add2_index]; + assert_eq!(main.len(), 2); + assert_eq!(main[0], OpCode::Num(3)); + assert_eq!(main[1], OpCode::Call(*add2_index)); + assert_eq!(add2.len(), 3); + assert_eq!(add2[0], OpCode::Num(2)); + assert_eq!(add2[1], OpCode::Add); + assert_eq!(add2[2], OpCode::Ret); + } + + #[test] + fn if_then() { + let comp = compiler_for("if 1 2 + then\n"); + eprintwordlist(&comp.wordlist); + assert_eq!(comp.wordlist.0.len(), 2); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::If(1, None)); + let tr = &comp.wordlist.0[1]; + assert_eq!(tr.len(), 4); + assert_eq!(tr[0], OpCode::Num(1)); + assert_eq!(tr[1], OpCode::Num(2)); + assert_eq!(tr[2], OpCode::Add); + assert_eq!(tr[3], OpCode::Ret); + } + + #[test] + fn if_else_then() { + let comp = compiler_for("if 1 2 + else 1 2 - then\n"); + eprintwordlist(&comp.wordlist); + assert_eq!(comp.wordlist.0.len(), 3, "wordlist length"); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::If(1, Some(2))); + let tr = &comp.wordlist.0[1]; + assert_eq!(tr.len(), 4); + assert_eq!(tr[0], OpCode::Num(1)); + assert_eq!(tr[1], OpCode::Num(2)); + assert_eq!(tr[2], OpCode::Add); + assert_eq!(tr[3], OpCode::Ret); + let fl = &comp.wordlist.0[2]; + assert_eq!(fl.len(), 4); + assert_eq!(fl[0], OpCode::Num(1)); + assert_eq!(fl[1], OpCode::Num(2)); + assert_eq!(fl[2], OpCode::Sub); + assert_eq!(fl[3], OpCode::Ret); + } + + #[test] + fn tail_call() { + let comp = compiler_for(": first + ; : second 3 first ; 1 second\n"); + assert_eq!(comp.wordlist.0.len(), 3, "wordlist length"); + eprintwordlist(&comp.wordlist); + } + + #[test] + fn tail_if() { + let comp = compiler_for(": t if 1 2 + then ; t\n"); + eprintwordlist(&comp.wordlist); + assert_eq!(comp.wordlist.0.len(), 3); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::Call(1)); + let t = &comp.wordlist.0[1]; + assert_eq!(t.len(), 2); + assert_eq!(t[0], OpCode::TIf(2, None)); + assert_eq!(t[1], OpCode::Ret); + let tr = &comp.wordlist.0[2]; + assert_eq!(tr.len(), 4); + assert_eq!(tr[0], OpCode::Num(1)); + assert_eq!(tr[1], OpCode::Num(2)); + assert_eq!(tr[2], OpCode::Add); + assert_eq!(tr[3], OpCode::Ret); + } + + #[test] + fn tail_if_else() { + let comp = compiler_for(": t if 1 2 + else 1 2 - then ; t\n"); + eprintwordlist(&comp.wordlist); + assert_eq!(comp.wordlist.0.len(), 4, "wordlist length"); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::Call(1)); + let t = &comp.wordlist.0[1]; + assert_eq!(t.len(), 2); + assert_eq!(t[0], OpCode::TIf(2, Some(3))); + assert_eq!(t[1], OpCode::Ret); + let tr = &comp.wordlist.0[2]; + assert_eq!(tr.len(), 4); + assert_eq!(tr[0], OpCode::Num(1)); + assert_eq!(tr[1], OpCode::Num(2)); + assert_eq!(tr[2], OpCode::Add); + assert_eq!(tr[3], OpCode::Ret); + let fl = &comp.wordlist.0[3]; + assert_eq!(fl.len(), 4); + assert_eq!(fl[0], OpCode::Num(1)); + assert_eq!(fl[1], OpCode::Num(2)); + assert_eq!(fl[2], OpCode::Sub); + assert_eq!(fl[3], OpCode::Ret); + } + + #[test] + fn recursion() { + let comp = compiler_for(": foo foo ; foo\n"); + eprintwordlist(&comp.wordlist); + assert_eq!(comp.wordlist.0.len(), 2); + let main = &comp.wordlist.0[0]; + assert_eq!(main.len(), 1); + assert_eq!(main[0], OpCode::Call(1)); + let foo = &comp.wordlist.0[1]; + assert_eq!(foo.len(), 1); + assert_eq!(foo[0], OpCode::TCall(1)); + } +} diff --git a/src/forth/interp.rs b/src/forth/interp.rs deleted file mode 100644 index 512c022..0000000 --- a/src/forth/interp.rs +++ /dev/null @@ -1,532 +0,0 @@ -use log::debug; - -use std::ops::Index; - -#[derive(Clone, Debug, PartialEq)] -pub enum OpCode { - Num(i32), - Str(usize, usize), - Call(usize), - TCall(usize), // tail call, really just ‘jmp’, but named to indicate desired usage. - If(usize, Option), // true word index, optional false word index. - TIf(usize, Option), // tail version - Add, - Sub, - Mul, - Div, - Dup, - Drop, - EQ, - GT, - GTE, - LT, - LTE, - // todo: maybe get rid of ret? it's only used in word definitions, - // which are bounded, so running of the end can be treated as an - // implicit ‘ret’. - Ret, -} - -#[derive(Clone, Debug)] -pub struct ByteCode(pub Vec); -impl std::ops::Deref for ByteCode { - type Target = Vec; - fn deref(&self) -> &Self::Target { - &self.0 - } -} - -impl ByteCode { - pub fn len(&self) -> usize { - self.0.len() - } -} - -impl Index for ByteCode { - type Output = OpCode; - - fn index(&self, index: usize) -> &Self::Output { - &self.0[index] - } -} - -#[derive(Debug, Copy, Clone, PartialEq)] -pub struct InstructionPointer { - pub word: usize, - pub offset: usize, -} - -impl InstructionPointer { - pub fn new() -> Self { - Self { - word: 0, - offset: 0, - } - } -} - -#[derive(Debug)] -pub struct DataStack(pub Vec); - -#[derive(Debug)] -pub struct CallStack(pub Vec); - -#[derive(Clone, Debug)] -pub struct WordList(pub Vec); -impl std::ops::Deref for WordList { - type Target = Vec; - fn deref(&self) -> &Self::Target { - &self.0 - } -} - -#[derive(Debug)] -pub struct Interp { - // todo: don't be pub, probably - pub stack: DataStack, - pub callstack: CallStack, - pub wordlist: WordList, - pub ip: InstructionPointer, -} - -#[derive(Debug)] -pub enum RuntimeError { - StackUnderflow, -} - -impl Interp { - pub fn new(wordlist: WordList) -> Self { - Self { - stack: DataStack(Vec::new()), - callstack: CallStack(Vec::new()), - ip: InstructionPointer::new(), - wordlist, - } - } - - pub fn jmp(&mut self, word: usize) { - self.ip.word = word; - self.ip.offset = 0; - } - - pub fn call(&mut self, word: usize) { - self.callstack.0.push(self.ip); - self.jmp(word); - } - - // bool is still_running - pub fn tick(&mut self) -> Result { - let bc = &self.wordlist.0[self.ip.word]; - match bc[self.ip.offset] { - OpCode::Num(n) => self.stack.0.push(n), - OpCode::Str(start, end) => debug!("got str: {} to {}", start, end), - OpCode::Add => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - self.stack.0.push(n2 + n1); - }, - OpCode::Sub => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - self.stack.0.push(n2 - n1); - }, - OpCode::Mul => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - self.stack.0.push(n2 * n1); - }, - OpCode::Div => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - self.stack.0.push(n2 / n1); - }, - OpCode::Dup => { - let n = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - self.stack.0.push(n); - self.stack.0.push(n); - }, - OpCode::Drop => { - self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - }, - OpCode::EQ => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let v = if n2 == n1 { -1 } else { 0 }; - self.stack.0.push(v); - }, - OpCode::GT => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let v = if n2 > n1 { -1 } else { 0 }; - self.stack.0.push(v); - }, - OpCode::GTE => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let v = if n2 >= n1 { -1 } else { 0 }; - self.stack.0.push(v); - }, - OpCode::LT => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let v = if n2 < n1 { -1 } else { 0 }; - self.stack.0.push(v); - }, - OpCode::LTE => { - let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - let v = if n2 <= n1 { -1 } else { 0 }; - self.stack.0.push(v); - }, - OpCode::Ret => { - self.ip = self.callstack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - }, - OpCode::Call(i) => { - self.call(i); - // skip the offset increment - return Ok(true) - }, - OpCode::TCall(i) => { - self.jmp(i); - // skip the offset increment - return Ok(true) - }, - OpCode::If(true_clause, false_clause) => { - let flag = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - if flag != 0 { - self.call(true_clause); - return Ok(true) - } else if let Some(false_clause) = false_clause { - self.call(false_clause); - return Ok(true) - } - }, - OpCode::TIf(true_clause, false_clause) => { - let flag = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; - if flag != 0 { - self.jmp(true_clause); - return Ok(true) - } else if let Some(false_clause) = false_clause { - self.jmp(false_clause); - return Ok(true) - } - }, - } - self.ip.offset += 1; - Ok(self.ip.offset < self.wordlist.0[self.ip.word].len()) - } - - pub fn run(&mut self) -> Result { - let mut count = 0; - while self.tick()? { count += 1 } - Ok(count) - } -} - -#[cfg(test)] -mod tests { - use super::*; - use super::OpCode; - - #[test] - fn simple_ticks() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Num(3), OpCode::Add])); - let mut interp = Interp::new(wordlist); - assert_eq!(interp.tick()?, true, "first arg running"); - assert_eq!(interp.ip.word, 0); - assert_eq!(interp.ip.offset, 1); - assert_eq!(interp.stack.0.len(), 1); - assert_eq!(interp.stack.0[0], 2, "first argument"); - assert_eq!(interp.tick()?, true, "second arg running"); - assert_eq!(interp.ip.word, 0); - assert_eq!(interp.ip.offset, 2); - assert_eq!(interp.stack.0.len(), 2); - assert_eq!(interp.stack.0[1], 3, "second argument"); - assert_eq!(interp.tick()?, false, "stopped after addition"); - assert_eq!(interp.ip.word, 0); - assert_eq!(interp.ip.offset, 3); - assert_eq!(interp.stack.0.len(), 1); - assert_eq!(interp.stack.0[0], 5, "result of addition"); - - Ok(()) - } - - #[test] - fn custom_word() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![ - OpCode::Num(2), OpCode::Num(3), OpCode::Call(1), OpCode::Num(-2), OpCode::Add, - OpCode::Sub, OpCode::Ret, - ])); - let mut interp = Interp::new(wordlist); - // "sub" definition - interp.wordlist.0.push(ByteCode(vec![ - OpCode::Sub, OpCode::Ret, - ])); - - interp.tick()?; - assert_eq!(interp.ip.word, 0); - assert_eq!(interp.ip.offset, 1); - assert_eq!(interp.stack.0.len(), 1); - assert_eq!(interp.stack.0[0], 2, "first argument"); - interp.tick()?; - assert_eq!(interp.ip.word, 0); - assert_eq!(interp.ip.offset, 2); - assert_eq!(interp.stack.0.len(), 2); - assert_eq!(interp.stack.0[1], 3, "second argument"); - - interp.tick()?; // call sub - assert_eq!(interp.ip.word, 1); - assert_eq!(interp.ip.offset, 0); - assert_eq!(interp.stack.0.len(), 2); - - interp.tick()?; // - - assert_eq!(interp.ip.word, 1); - assert_eq!(interp.ip.offset, 1); - assert_eq!(interp.stack.0.len(), 1); - - interp.tick()?; // ret - assert_eq!(interp.ip.word, 0); - assert_eq!(interp.ip.offset, 3); - assert_eq!(interp.stack.0.len(), 1); - assert_eq!(interp.stack.0[0], -1, "result of sub word"); - - interp.tick()?; // 2 - assert_eq!(interp.ip.word, 0); - assert_eq!(interp.ip.offset, 4); - assert_eq!(interp.stack.0.len(), 2); - assert_eq!(interp.stack.0[1], -2, "post sub arg"); - - interp.tick()?; // - - assert_eq!(interp.ip.word, 0); - assert_eq!(interp.ip.offset, 5); - assert_eq!(interp.stack.0.len(), 1); - assert_eq!(interp.stack.0[0], -3, "add opcode result"); - - Ok(()) - } - - #[test] - fn tail_call() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Call(1)])); - wordlist.0.push(ByteCode(vec![OpCode::TCall(2), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; // call - assert_eq!(interp.callstack.0.len(), 1, "callstack after call"); - interp.tick()?; // tcall - assert_eq!(interp.callstack.0.len(), 1, "callstack after tcall"); - interp.tick()?; // ret - assert_eq!(interp.callstack.0.len(), 0, "callstack after ret"); - Ok(()) - } - - #[test] - fn if_then_true() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::If(1, None), OpCode::Num(0)])); - wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push -1 stack len"); - assert_eq!(interp.stack.0[0], -1, "push -1 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "if stack "); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 1 stack len"); - assert_eq!(interp.stack.0[0], 1, "push 1 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "ret stack len"); - assert_eq!(interp.stack.0[0], 1, "ret stack val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 2, "push 0 stack len"); - assert_eq!(interp.stack.0[1], 0, "push 0 stack val"); - - Ok(()) - } - - #[test] - fn if_then_false() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::If(1, None), OpCode::Num(-1)])); - wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 0 stack len"); - assert_eq!(interp.stack.0[0], 0, "push 0 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "if stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push -1 stack len"); - assert_eq!(interp.stack.0[0], -1, "push -1 val"); - - Ok(()) - } - - #[test] - fn if_else_then_true() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::If(1, Some(2)), OpCode::Num(-2)])); - wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push -1 stack len"); - assert_eq!(interp.stack.0[0], -1, "push -1 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "if stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 1 stack len"); - assert_eq!(interp.stack.0[0], 1, "push 1 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "ret stack len"); - assert_eq!(interp.stack.0[0], 1, "ret val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 2, "push -2 stack len"); - assert_eq!(interp.stack.0[1], -2, "push -2 val"); - - Ok(()) - } - - #[test] - fn if_else_then_false() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::If(1, Some(2)), OpCode::Num(-2)])); - wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 0 stack len"); - assert_eq!(interp.stack.0[0], 0, "push 0 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "if"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 2 stack len"); - assert_eq!(interp.stack.0[0], 2, "push 2 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "ret"); - assert_eq!(interp.stack.0[0], 2, "ret"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 2, "push -2 stack len"); - assert_eq!(interp.stack.0[1], -2, "push -2 val"); - - Ok(()) - } - - #[test] - fn tail_if_then_true() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(0)])); - wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::TIf(2, None), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "call(1) stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push -1 stack len"); - assert_eq!(interp.stack.0[0], -1, "push -1 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "tif stack "); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 1 stack len"); - assert_eq!(interp.stack.0[0], 1, "push 1 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "ret stack len"); - assert_eq!(interp.stack.0[0], 1, "ret stack val"); - interp.tick()?; // no ret on wordlist[1] since it's ‘tif’ - assert_eq!(interp.stack.0.len(), 2, "push 0 stack len"); - assert_eq!(interp.stack.0[1], 0, "push 0 stack val"); - - Ok(()) - } - - #[test] - fn tail_if_then_false() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(0)])); - wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::TIf(2, None), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "call(1) stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 0 stack len"); - assert_eq!(interp.stack.0[0], 0, "push 0 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "tif stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "ret stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 0 stack len"); - assert_eq!(interp.stack.0[0], 0, "push 0 val"); - - Ok(()) - } - - #[test] - fn tail_if_else_then_true() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(-2)])); - wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::TIf(2, Some(3)), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "call(1) stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push -1 stack len"); - assert_eq!(interp.stack.0[0], -1, "push -1 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "tif stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 1 stack len"); - assert_eq!(interp.stack.0[0], 1, "push 1 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "ret stack len"); - assert_eq!(interp.stack.0[0], 1, "ret val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 2, "push -2 stack len"); - assert_eq!(interp.stack.0[1], -2, "push -2 val"); - - Ok(()) - } - - #[test] - fn tail_if_else_then_false() -> Result<(), RuntimeError> { - let mut wordlist = WordList(vec![]); - wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(-2)])); - wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::TIf(2, Some(3)), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); - let mut interp = Interp::new(wordlist); - - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "call(1) stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 0 stack len"); - assert_eq!(interp.stack.0[0], 0, "push 0 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 0, "tif stack len"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "push 2 stack len"); - assert_eq!(interp.stack.0[0], 2, "push 2 val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 1, "ret stack len"); - assert_eq!(interp.stack.0[0], 2, "ret val"); - interp.tick()?; - assert_eq!(interp.stack.0.len(), 2, "push -2 stack len"); - assert_eq!(interp.stack.0[1], -2, "push -2 val"); - - Ok(()) - } -} diff --git a/src/forth/mod.rs b/src/forth/mod.rs old mode 100755 new mode 100644 index 063b40e..f244ef4 --- a/src/forth/mod.rs +++ b/src/forth/mod.rs @@ -1,16 +1,16 @@ -pub mod interp; -pub mod parser; +pub mod compiler; +pub mod vm; #[cfg(test)] mod tests { use super::{ - interp::{Interp, WordList}, - parser::Parser + vm::{VM, WordList}, + compiler::Compiler, }; - fn parser_for(text: &str) -> Parser { - let mut p = Parser::new(text); - p.parse().expect("badparse"); + fn parser_for(text: &str) -> Compiler { + let mut p = Compiler::new(text); + p.compile().expect("badparse"); p } @@ -26,10 +26,10 @@ mod tests { let prog = ": fac dup 1 > if dup 1 - fac * then ; 5 fac\n"; let p = parser_for(prog); eprintwordlist(&p.wordlist); - let mut interp = Interp::new(p.wordlist); - interp.run().expect("should run to completion"); - eprintln!("stack: {:?}", interp.stack); - assert_eq!(interp.stack.0.len(), 1, "factorial result stack len"); - assert_eq!(interp.stack.0[0], 120, "factorial result value"); + let mut vm = VM::new(p.wordlist); + vm.run().expect("should run to completion"); + eprintln!("stack: {:?}", vm.stack); + assert_eq!(vm.stack.0.len(), 1, "factorial result stack len"); + assert_eq!(vm.stack.0[0], 120, "factorial result value"); } } diff --git a/src/forth/parser.rs b/src/forth/parser.rs deleted file mode 100644 index c934c4a..0000000 --- a/src/forth/parser.rs +++ /dev/null @@ -1,384 +0,0 @@ -use super::interp::{ByteCode, OpCode, WordList}; - -use std::collections::HashMap; -use std::iter::{Enumerate, Iterator}; -use std::str::Chars; - -#[derive(Debug)] -pub enum ParseError { - EOF, - DefStackEmpty, - MissingIf, - MissingQuote, - UnknownWord(String), -} -impl std::fmt::Display for ParseError { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - match self { - Self::EOF => write!(f, "premature end-of-file"), - Self::DefStackEmpty => write!(f, "def stack empty"), - Self::MissingIf => write!(f, "missing if"), - Self::MissingQuote => write!(f, "missing ending quote"), - Self::UnknownWord(word) => write!(f, "unknown word: {}", word), - } - } -} -impl std::error::Error for ParseError {} - -type ParseResult = Result; - -// todo: the annotations should be directly tied to the wordlist so -// they can't get out of sync. -#[derive(Debug)] -pub struct Annotation { - // (start, end) index in program text - pub loc: (usize, usize), -} - -#[derive(Debug)] -pub struct WordCatalog<'a>(pub(super) HashMap<&'a str, usize>); - -#[derive(Debug)] -pub enum IfClauses { - True(usize), - TrueFalse(usize, usize), -} - -#[derive(Debug)] -pub struct Parser<'a> { - text: &'a str, - enumerator: Enumerate>, - // list of all word definitions, in the order defined. the main - // routine is always in the first entry. - // todo: don't be pub, have a method to extract a wordlist - pub wordlist: WordList, - pub annotations: Vec>, - // catalog of word to word index in `wordlist` - pub wordalog: WordCatalog<'a>, - // holds a stack of indices into `wordlist` that are currently - // being defined, with the top of stack being the most recent - // definition. - defstack: Vec, - // number of clauses currently being defined for a particular ‘if’ - // construct. a stack is needed in order to allow for nesting. - if_stack: Vec<(IfClauses, Annotation)>, -} - -impl<'a> Parser<'a> { - pub fn new(text: &'a str) -> Self { - let mut wl = vec![]; - // main routine is always the first entry. - wl.push(ByteCode(vec![])); - Self { - text, - enumerator: text.chars().enumerate(), - wordlist: WordList(wl), - annotations: vec![vec![]], - wordalog: WordCatalog(HashMap::new()), - defstack: vec![], - if_stack: vec![], - } - } - - // pull the next, whitespace-delimited word off the input stream. - fn next_word(&mut self) -> Option<(&'a str, usize, usize)> { - let (start, _c) = - self.enumerator.by_ref() - .find(|(_i, c)| !c.is_whitespace())?; - let (end, _c) = - self.enumerator.by_ref() - .find(|(_i, c)| c.is_whitespace())?; - let word = &self.text[start..end]; - Some((word, start, end)) - } - - // currently ‘active’ bytecode being built. - fn bc_mut(&mut self) -> &mut ByteCode { - let word_index = self.defstack.last().unwrap_or(&0); - &mut self.wordlist.0[*word_index] - } - - fn bc(&self) -> &ByteCode { - let word_index = self.defstack.last().unwrap_or(&0); - &self.wordlist.0[*word_index] - } - - fn anno_mut(&mut self) -> &mut Vec { - let word_index = self.defstack.last().unwrap_or(&0); - &mut self.annotations[*word_index] - } - - // push `op` onto the currently building bytecode, as determined - // by the top of the `namestack`. - fn bc_push(&mut self, op: OpCode, anno: Annotation) { - self.bc_mut().0.push(op); - self.anno_mut().push(anno); - } - - pub fn parse(&mut self) -> ParseResult<()> { - while let Some((word, start, end)) = self.next_word() { - let anno = Annotation { loc: (start, end) }; - if let Ok(i) = word.parse::() { - self.bc_push(OpCode::Num(i), anno); - } else if let Some(i) = self.wordalog.0.get(word) { - self.bc_push(OpCode::Call(*i), anno); - } else { - match word { - r#"s""# => { - let (s_end, _) = - self.enumerator - .find(|(_i, c)| return *c == '"') - .ok_or(ParseError::MissingQuote)?; - self.bc_push(OpCode::Str(end+1, s_end), anno); - }, - ":" => { - let (name, _, _) = self.next_word().ok_or(ParseError::EOF)?; - self.wordalog.0.insert(name, self.wordlist.0.len()); - self.defstack.push(self.wordlist.0.len()); - self.wordlist.0.push(ByteCode(vec![])); - self.annotations.push(vec![]); - }, - ";" => { - match self.bc().0.last() { - Some(OpCode::Call(i)) => { - let k = *i; - self.bc_mut().0.pop(); - self.bc_mut().0.push(OpCode::TCall(k)); - }, - Some(OpCode::If(t, f)) => { - let t = *t; - let f = *f; - self.bc_mut().0.pop(); - self.bc_mut().0.push(OpCode::TIf(t, f)); - // technically only needed if ‘f’ is None, but whatever. - self.bc_push(OpCode::Ret, anno); - }, - _ => self.bc_push(OpCode::Ret, anno), - } - self.defstack.pop().ok_or(ParseError::DefStackEmpty)?; - }, - "if" => { - let i = self.wordlist.0.len(); - self.wordlist.0.push(ByteCode(vec![])); - self.annotations.push(vec![]); - self.defstack.push(i); - - self.if_stack.push((IfClauses::True(i), anno)); - }, - "else" => { - self.bc_push(OpCode::Ret, anno); - self.defstack.pop(); - - let i = self.wordlist.0.len(); - self.wordlist.0.push(ByteCode(vec![])); - self.annotations.push(vec![]); - self.defstack.push(i); - - let (true_clause, anno) = match self.if_stack.pop() { - None => return Err(ParseError::MissingIf), - Some((IfClauses::TrueFalse(_, _), _)) => return Err(ParseError::MissingIf), - Some((IfClauses::True(cl), anno)) => (cl, anno), - }; - self.if_stack.push((IfClauses::TrueFalse(true_clause, i), anno)); - }, - "then" => { - self.bc_push(OpCode::Ret, anno); - self.defstack.pop(); - - match self.if_stack.pop() { - None => return Err(ParseError::MissingIf), - Some((IfClauses::True(true_clause), anno)) => { - self.bc_push(OpCode::If(true_clause, None), anno); - }, - Some((IfClauses::TrueFalse(true_clause, false_clause), anno)) => { - self.bc_push(OpCode::If(true_clause, Some(false_clause)), anno); - } - } - }, - "+" => self.bc_push(OpCode::Add, anno), - "-" => self.bc_push(OpCode::Sub, anno), - "*" => self.bc_push(OpCode::Mul, anno), - "/" => self.bc_push(OpCode::Div, anno), - "dup" => self.bc_push(OpCode::Dup, anno), - "drop" => self.bc_push(OpCode::Drop, anno), - "=" => self.bc_push(OpCode::EQ, anno), - ">" => self.bc_push(OpCode::GT, anno), - ">=" => self.bc_push(OpCode::GTE, anno), - "<" => self.bc_push(OpCode::LT, anno), - "<=" => self.bc_push(OpCode::LTE, anno), - other => return Err(ParseError::UnknownWord(String::from(other))), - } - } - } - Ok(()) - } -} - -#[cfg(test)] -mod tests { - use super::*; - use super::super::interp::OpCode; - - fn parser_for(text: &str) -> Parser { - let mut p = Parser::new(text); - p.parse().expect("badparse"); - p - } - - fn eprintwordlist(wordlist: &WordList) { - for i in 0..wordlist.0.len() { - eprintln!("wordlist[{}]: {:?}", i, wordlist.0[i]); - } - } - - #[test] - fn literal_num() { - let p = parser_for("1\n"); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::Num(1)); - } - - #[test] - fn literal_string() { - let p = parser_for(r#"s" hello there""#); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::Str(3, 14)); - } - - #[test] - fn add_opcode() { - let p = parser_for("+\n"); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::Add); - } - - #[test] - fn sub_opcode() { - let p = parser_for("-\n"); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::Sub); - } - - #[test] - fn def_word() { - let p = parser_for(": add2 2 + ; 3 add2\n"); - let main = &p.wordlist.0[0]; - let add2_index = p.wordalog.0.get("add2").expect("add2 has entry in wordlist"); - let add2 = &p.wordlist.0[*add2_index]; - assert_eq!(main.len(), 2); - assert_eq!(main[0], OpCode::Num(3)); - assert_eq!(main[1], OpCode::Call(*add2_index)); - assert_eq!(add2.len(), 3); - assert_eq!(add2[0], OpCode::Num(2)); - assert_eq!(add2[1], OpCode::Add); - assert_eq!(add2[2], OpCode::Ret); - } - - #[test] - fn if_then() { - let p = parser_for("if 1 2 + then\n"); - eprintwordlist(&p.wordlist); - assert_eq!(p.wordlist.0.len(), 2); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::If(1, None)); - let tr = &p.wordlist.0[1]; - assert_eq!(tr.len(), 4); - assert_eq!(tr[0], OpCode::Num(1)); - assert_eq!(tr[1], OpCode::Num(2)); - assert_eq!(tr[2], OpCode::Add); - assert_eq!(tr[3], OpCode::Ret); - } - - #[test] - fn if_else_then() { - let p = parser_for("if 1 2 + else 1 2 - then\n"); - eprintwordlist(&p.wordlist); - assert_eq!(p.wordlist.0.len(), 3, "wordlist length"); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::If(1, Some(2))); - let tr = &p.wordlist.0[1]; - assert_eq!(tr.len(), 4); - assert_eq!(tr[0], OpCode::Num(1)); - assert_eq!(tr[1], OpCode::Num(2)); - assert_eq!(tr[2], OpCode::Add); - assert_eq!(tr[3], OpCode::Ret); - let fl = &p.wordlist.0[2]; - assert_eq!(fl.len(), 4); - assert_eq!(fl[0], OpCode::Num(1)); - assert_eq!(fl[1], OpCode::Num(2)); - assert_eq!(fl[2], OpCode::Sub); - assert_eq!(fl[3], OpCode::Ret); - } - - #[test] - fn tail_call() { - let p = parser_for(": first + ; : second 3 first ; 1 second\n"); - assert_eq!(p.wordlist.0.len(), 3, "wordlist length"); - eprintwordlist(&p.wordlist); - } - - #[test] - fn tail_if() { - let p = parser_for(": t if 1 2 + then ; t\n"); - eprintwordlist(&p.wordlist); - assert_eq!(p.wordlist.0.len(), 3); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::Call(1)); - let t = &p.wordlist.0[1]; - assert_eq!(t.len(), 2); - assert_eq!(t[0], OpCode::TIf(2, None)); - assert_eq!(t[1], OpCode::Ret); - let tr = &p.wordlist.0[2]; - assert_eq!(tr.len(), 4); - assert_eq!(tr[0], OpCode::Num(1)); - assert_eq!(tr[1], OpCode::Num(2)); - assert_eq!(tr[2], OpCode::Add); - assert_eq!(tr[3], OpCode::Ret); - } - - #[test] - fn tail_if_else() { - let p = parser_for(": t if 1 2 + else 1 2 - then ; t\n"); - eprintwordlist(&p.wordlist); - assert_eq!(p.wordlist.0.len(), 4, "wordlist length"); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::Call(1)); - let t = &p.wordlist.0[1]; - assert_eq!(t.len(), 2); - assert_eq!(t[0], OpCode::TIf(2, Some(3))); - assert_eq!(t[1], OpCode::Ret); - let tr = &p.wordlist.0[2]; - assert_eq!(tr.len(), 4); - assert_eq!(tr[0], OpCode::Num(1)); - assert_eq!(tr[1], OpCode::Num(2)); - assert_eq!(tr[2], OpCode::Add); - assert_eq!(tr[3], OpCode::Ret); - let fl = &p.wordlist.0[3]; - assert_eq!(fl.len(), 4); - assert_eq!(fl[0], OpCode::Num(1)); - assert_eq!(fl[1], OpCode::Num(2)); - assert_eq!(fl[2], OpCode::Sub); - assert_eq!(fl[3], OpCode::Ret); - } - - #[test] - fn recursion() { - let p = parser_for(": foo foo ; foo\n"); - eprintwordlist(&p.wordlist); - assert_eq!(p.wordlist.0.len(), 2); - let main = &p.wordlist.0[0]; - assert_eq!(main.len(), 1); - assert_eq!(main[0], OpCode::Call(1)); - let foo = &p.wordlist.0[1]; - assert_eq!(foo.len(), 1); - assert_eq!(foo[0], OpCode::TCall(1)); - } -} diff --git a/src/forth/vm.rs b/src/forth/vm.rs new file mode 100644 index 0000000..b4ce674 --- /dev/null +++ b/src/forth/vm.rs @@ -0,0 +1,532 @@ +use log::debug; + +use std::ops::Index; + +#[derive(Clone, Debug, PartialEq)] +pub enum OpCode { + Num(i32), + Str(usize, usize), + Call(usize), + TCall(usize), // tail call, really just ‘jmp’, but named to indicate desired usage. + If(usize, Option), // true word index, optional false word index. + TIf(usize, Option), // tail version + Add, + Sub, + Mul, + Div, + Dup, + Drop, + EQ, + GT, + GTE, + LT, + LTE, + // todo: maybe get rid of ret? it's only used in word definitions, + // which are bounded, so running of the end can be treated as an + // implicit ‘ret’. + Ret, +} + +#[derive(Clone, Debug)] +pub struct ByteCode(pub Vec); +impl std::ops::Deref for ByteCode { + type Target = Vec; + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl ByteCode { + pub fn len(&self) -> usize { + self.0.len() + } +} + +impl Index for ByteCode { + type Output = OpCode; + + fn index(&self, index: usize) -> &Self::Output { + &self.0[index] + } +} + +#[derive(Debug, Copy, Clone, PartialEq)] +pub struct InstructionPointer { + pub word: usize, + pub offset: usize, +} + +impl InstructionPointer { + pub fn new() -> Self { + Self { + word: 0, + offset: 0, + } + } +} + +#[derive(Debug)] +pub struct DataStack(pub Vec); + +#[derive(Debug)] +pub struct CallStack(pub Vec); + +#[derive(Clone, Debug)] +pub struct WordList(pub Vec); +impl std::ops::Deref for WordList { + type Target = Vec; + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +#[derive(Debug)] +pub struct VM { + // todo: don't be pub, probably + pub stack: DataStack, + pub callstack: CallStack, + pub wordlist: WordList, + pub ip: InstructionPointer, +} + +#[derive(Debug)] +pub enum RuntimeError { + StackUnderflow, +} + +impl VM { + pub fn new(wordlist: WordList) -> Self { + Self { + stack: DataStack(Vec::new()), + callstack: CallStack(Vec::new()), + ip: InstructionPointer::new(), + wordlist, + } + } + + pub fn jmp(&mut self, word: usize) { + self.ip.word = word; + self.ip.offset = 0; + } + + pub fn call(&mut self, word: usize) { + self.callstack.0.push(self.ip); + self.jmp(word); + } + + // bool is still_running + pub fn tick(&mut self) -> Result { + let bc = &self.wordlist.0[self.ip.word]; + match bc[self.ip.offset] { + OpCode::Num(n) => self.stack.0.push(n), + OpCode::Str(start, end) => debug!("got str: {} to {}", start, end), + OpCode::Add => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + self.stack.0.push(n2 + n1); + }, + OpCode::Sub => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + self.stack.0.push(n2 - n1); + }, + OpCode::Mul => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + self.stack.0.push(n2 * n1); + }, + OpCode::Div => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + self.stack.0.push(n2 / n1); + }, + OpCode::Dup => { + let n = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + self.stack.0.push(n); + self.stack.0.push(n); + }, + OpCode::Drop => { + self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + }, + OpCode::EQ => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 == n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::GT => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 > n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::GTE => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 >= n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::LT => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 < n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::LTE => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 <= n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::Ret => { + self.ip = self.callstack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + }, + OpCode::Call(i) => { + self.call(i); + // skip the offset increment + return Ok(true) + }, + OpCode::TCall(i) => { + self.jmp(i); + // skip the offset increment + return Ok(true) + }, + OpCode::If(true_clause, false_clause) => { + let flag = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + if flag != 0 { + self.call(true_clause); + return Ok(true) + } else if let Some(false_clause) = false_clause { + self.call(false_clause); + return Ok(true) + } + }, + OpCode::TIf(true_clause, false_clause) => { + let flag = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + if flag != 0 { + self.jmp(true_clause); + return Ok(true) + } else if let Some(false_clause) = false_clause { + self.jmp(false_clause); + return Ok(true) + } + }, + } + self.ip.offset += 1; + Ok(self.ip.offset < self.wordlist.0[self.ip.word].len()) + } + + pub fn run(&mut self) -> Result { + let mut count = 0; + while self.tick()? { count += 1 } + Ok(count) + } +} + +#[cfg(test)] +mod tests { + use super::*; + use super::OpCode; + + #[test] + fn simple_ticks() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Num(3), OpCode::Add])); + let mut vm = VM::new(wordlist); + assert_eq!(vm.tick()?, true, "first arg running"); + assert_eq!(vm.ip.word, 0); + assert_eq!(vm.ip.offset, 1); + assert_eq!(vm.stack.0.len(), 1); + assert_eq!(vm.stack.0[0], 2, "first argument"); + assert_eq!(vm.tick()?, true, "second arg running"); + assert_eq!(vm.ip.word, 0); + assert_eq!(vm.ip.offset, 2); + assert_eq!(vm.stack.0.len(), 2); + assert_eq!(vm.stack.0[1], 3, "second argument"); + assert_eq!(vm.tick()?, false, "stopped after addition"); + assert_eq!(vm.ip.word, 0); + assert_eq!(vm.ip.offset, 3); + assert_eq!(vm.stack.0.len(), 1); + assert_eq!(vm.stack.0[0], 5, "result of addition"); + + Ok(()) + } + + #[test] + fn custom_word() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![ + OpCode::Num(2), OpCode::Num(3), OpCode::Call(1), OpCode::Num(-2), OpCode::Add, + OpCode::Sub, OpCode::Ret, + ])); + let mut vm = VM::new(wordlist); + // "sub" definition + vm.wordlist.0.push(ByteCode(vec![ + OpCode::Sub, OpCode::Ret, + ])); + + vm.tick()?; + assert_eq!(vm.ip.word, 0); + assert_eq!(vm.ip.offset, 1); + assert_eq!(vm.stack.0.len(), 1); + assert_eq!(vm.stack.0[0], 2, "first argument"); + vm.tick()?; + assert_eq!(vm.ip.word, 0); + assert_eq!(vm.ip.offset, 2); + assert_eq!(vm.stack.0.len(), 2); + assert_eq!(vm.stack.0[1], 3, "second argument"); + + vm.tick()?; // call sub + assert_eq!(vm.ip.word, 1); + assert_eq!(vm.ip.offset, 0); + assert_eq!(vm.stack.0.len(), 2); + + vm.tick()?; // - + assert_eq!(vm.ip.word, 1); + assert_eq!(vm.ip.offset, 1); + assert_eq!(vm.stack.0.len(), 1); + + vm.tick()?; // ret + assert_eq!(vm.ip.word, 0); + assert_eq!(vm.ip.offset, 3); + assert_eq!(vm.stack.0.len(), 1); + assert_eq!(vm.stack.0[0], -1, "result of sub word"); + + vm.tick()?; // 2 + assert_eq!(vm.ip.word, 0); + assert_eq!(vm.ip.offset, 4); + assert_eq!(vm.stack.0.len(), 2); + assert_eq!(vm.stack.0[1], -2, "post sub arg"); + + vm.tick()?; // - + assert_eq!(vm.ip.word, 0); + assert_eq!(vm.ip.offset, 5); + assert_eq!(vm.stack.0.len(), 1); + assert_eq!(vm.stack.0[0], -3, "add opcode result"); + + Ok(()) + } + + #[test] + fn tail_call() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1)])); + wordlist.0.push(ByteCode(vec![OpCode::TCall(2), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; // call + assert_eq!(vm.callstack.0.len(), 1, "callstack after call"); + vm.tick()?; // tcall + assert_eq!(vm.callstack.0.len(), 1, "callstack after tcall"); + vm.tick()?; // ret + assert_eq!(vm.callstack.0.len(), 0, "callstack after ret"); + Ok(()) + } + + #[test] + fn if_then_true() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::If(1, None), OpCode::Num(0)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push -1 stack len"); + assert_eq!(vm.stack.0[0], -1, "push -1 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "if stack "); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 1 stack len"); + assert_eq!(vm.stack.0[0], 1, "push 1 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "ret stack len"); + assert_eq!(vm.stack.0[0], 1, "ret stack val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 2, "push 0 stack len"); + assert_eq!(vm.stack.0[1], 0, "push 0 stack val"); + + Ok(()) + } + + #[test] + fn if_then_false() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::If(1, None), OpCode::Num(-1)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 0 stack len"); + assert_eq!(vm.stack.0[0], 0, "push 0 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "if stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push -1 stack len"); + assert_eq!(vm.stack.0[0], -1, "push -1 val"); + + Ok(()) + } + + #[test] + fn if_else_then_true() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::If(1, Some(2)), OpCode::Num(-2)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push -1 stack len"); + assert_eq!(vm.stack.0[0], -1, "push -1 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "if stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 1 stack len"); + assert_eq!(vm.stack.0[0], 1, "push 1 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "ret stack len"); + assert_eq!(vm.stack.0[0], 1, "ret val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 2, "push -2 stack len"); + assert_eq!(vm.stack.0[1], -2, "push -2 val"); + + Ok(()) + } + + #[test] + fn if_else_then_false() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::If(1, Some(2)), OpCode::Num(-2)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 0 stack len"); + assert_eq!(vm.stack.0[0], 0, "push 0 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "if"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 2 stack len"); + assert_eq!(vm.stack.0[0], 2, "push 2 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "ret"); + assert_eq!(vm.stack.0[0], 2, "ret"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 2, "push -2 stack len"); + assert_eq!(vm.stack.0[1], -2, "push -2 val"); + + Ok(()) + } + + #[test] + fn tail_if_then_true() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(0)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::TIf(2, None), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "call(1) stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push -1 stack len"); + assert_eq!(vm.stack.0[0], -1, "push -1 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "tif stack "); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 1 stack len"); + assert_eq!(vm.stack.0[0], 1, "push 1 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "ret stack len"); + assert_eq!(vm.stack.0[0], 1, "ret stack val"); + vm.tick()?; // no ret on wordlist[1] since it's ‘tif’ + assert_eq!(vm.stack.0.len(), 2, "push 0 stack len"); + assert_eq!(vm.stack.0[1], 0, "push 0 stack val"); + + Ok(()) + } + + #[test] + fn tail_if_then_false() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(0)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::TIf(2, None), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "call(1) stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 0 stack len"); + assert_eq!(vm.stack.0[0], 0, "push 0 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "tif stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "ret stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 0 stack len"); + assert_eq!(vm.stack.0[0], 0, "push 0 val"); + + Ok(()) + } + + #[test] + fn tail_if_else_then_true() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(-2)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::TIf(2, Some(3)), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "call(1) stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push -1 stack len"); + assert_eq!(vm.stack.0[0], -1, "push -1 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "tif stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 1 stack len"); + assert_eq!(vm.stack.0[0], 1, "push 1 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "ret stack len"); + assert_eq!(vm.stack.0[0], 1, "ret val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 2, "push -2 stack len"); + assert_eq!(vm.stack.0[1], -2, "push -2 val"); + + Ok(()) + } + + #[test] + fn tail_if_else_then_false() -> Result<(), RuntimeError> { + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(-2)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::TIf(2, Some(3)), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut vm = VM::new(wordlist); + + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "call(1) stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 0 stack len"); + assert_eq!(vm.stack.0[0], 0, "push 0 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 0, "tif stack len"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "push 2 stack len"); + assert_eq!(vm.stack.0[0], 2, "push 2 val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 1, "ret stack len"); + assert_eq!(vm.stack.0[0], 2, "ret val"); + vm.tick()?; + assert_eq!(vm.stack.0.len(), 2, "push -2 stack len"); + assert_eq!(vm.stack.0[1], -2, "push -2 val"); + + Ok(()) + } +} diff --git a/src/lib.rs b/src/lib.rs index bb8e638..60a406f 100755 --- a/src/lib.rs +++ b/src/lib.rs @@ -10,8 +10,8 @@ pub struct ExportedInstructionPointer { pub offset: usize, } -impl From<&forth::interp::InstructionPointer> for ExportedInstructionPointer { - fn from(ip: &forth::interp::InstructionPointer) -> Self { +impl From<&forth::vm::InstructionPointer> for ExportedInstructionPointer { + fn from(ip: &forth::vm::InstructionPointer) -> Self { Self { word: ip.word, offset: ip.offset } } } @@ -22,8 +22,8 @@ impl From<&forth::interp::InstructionPointer> for ExportedInstructionPointer { pub struct ExportedByteCode(Vec); impl ExportedByteCode { - fn tr_op(op: &forth::interp::OpCode) -> String { - use forth::interp::OpCode::*; + fn tr_op(op: &forth::vm::OpCode) -> String { + use forth::vm::OpCode::*; let s = match op { If(t, None) => format!("If({}, none)", t), If(t, Some(f)) => format!("If({}, {})", t, f), @@ -35,8 +35,8 @@ impl ExportedByteCode { } } -impl From<&forth::interp::ByteCode> for ExportedByteCode { - fn from(v: &forth::interp::ByteCode) -> Self { +impl From<&forth::vm::ByteCode> for ExportedByteCode { + fn from(v: &forth::vm::ByteCode) -> Self { Self(v.iter().map(Self::tr_op).collect()) } } @@ -60,8 +60,8 @@ pub struct ExportedAnnotation { pub end: usize, } -impl From<&forth::parser::Annotation> for ExportedAnnotation { - fn from(v: &forth::parser::Annotation) -> Self { +impl From<&forth::compiler::Annotation> for ExportedAnnotation { + fn from(v: &forth::compiler::Annotation) -> Self { Self { start: v.loc.0, end: v.loc.1, @@ -92,65 +92,65 @@ impl ExportedWordAnnotations { } #[wasm_bindgen] -pub struct ExportedInterp { +pub struct ExportedVM { annos: Vec, - i: Option, + vm: Option, } #[wasm_bindgen] -impl ExportedInterp { +impl ExportedVM { fn new() -> Self { - Self { annos: vec![], i: None } + Self { annos: vec![], vm: None } } pub fn compile(&mut self, text: &str) -> bool { - let mut p = forth::parser::Parser::new(&text); - if let Err(e) = p.parse() { - error!("couldn't parse program text: {:?}", e); + let mut comp = forth::compiler::Compiler::new(&text); + if let Err(e) = comp.compile() { + error!("couldn't compile program text: {:?}", e); return false } self.annos = - p.annotations.iter() + comp.annotations.iter() .map(|word_anno| -> ExportedWordAnnotations { word_anno.into_iter().map(|a| a.into()).collect() }) .collect(); - let interp = forth::interp::Interp::new(p.wordlist); - let _ = self.i.insert(interp); + let vm = forth::vm::VM::new(comp.wordlist); + let _ = self.vm.insert(vm); true } pub fn tick(&mut self) -> Result { - let Some(interp) = &mut self.i else { - return Err("no interpreter".to_string()) + let Some(vm) = &mut self.vm else { + return Err("no vm".to_string()) }; - interp.tick().or_else(|err| Err(format!("runtime error: {:?}", err))) + vm.tick().or_else(|err| Err(format!("runtime error: {:?}", err))) } pub fn run(&mut self) -> Result { - let Some(interp) = &mut self.i else { - return Err("no interpreter".to_string()) + let Some(vm) = &mut self.vm else { + return Err("no vm".to_string()) }; - interp.ip.word = 0; - interp.ip.offset = 0; - interp.run().or_else(|err| Err(format!("runtime error: {:?}", err))) + vm.ip.word = 0; + vm.ip.offset = 0; + vm.run().or_else(|err| Err(format!("runtime error: {:?}", err))) } pub fn stack(&self) -> Vec { - let Some(interp) = &self.i else { + let Some(vm) = &self.vm else { return vec![] }; - return interp.stack.0.clone() + return vm.stack.0.clone() } pub fn wordlist(&self) -> Vec { - let Some(interp) = &self.i else { + let Some(vm) = &self.vm else { return vec![] }; - interp.wordlist.iter().map(|bc| bc.into()).collect() + vm.wordlist.iter().map(|bc| bc.into()).collect() } pub fn annotations(&self) -> Vec { @@ -162,33 +162,33 @@ impl ExportedInterp { } pub fn callstack(&self) -> Vec { - let Some(interp) = &self.i else { + let Some(vm) = &self.vm else { return vec![] }; - interp.callstack.0.iter() + vm.callstack.0.iter() .map(|ip| ip.into()) .collect() } pub fn ip(&self) -> ExportedInstructionPointer { - let Some(interp) = &self.i else { + let Some(vm) = &self.vm else { return ExportedInstructionPointer { word: 0, offset: 0 } }; - (&interp.ip).into() + (&vm.ip).into() } pub fn reset_ip(&mut self) { - let Some(interp) = &mut self.i else { + let Some(vm) = &mut self.vm else { return; }; - interp.ip.word = 0; - interp.ip.offset = 0; + vm.ip.word = 0; + vm.ip.offset = 0; } } #[wasm_bindgen] -pub fn make_interp() -> ExportedInterp { - ExportedInterp::new() +pub fn make_vm() -> ExportedVM { + ExportedVM::new() } #[wasm_bindgen(start)] -- cgit v1.3