diff options
Diffstat (limited to 'src/runtime.rs')
-rw-r--r-- | src/runtime.rs | 327 |
1 files changed, 208 insertions, 119 deletions
diff --git a/src/runtime.rs b/src/runtime.rs index 3954a80..b041561 100644 --- a/src/runtime.rs +++ b/src/runtime.rs @@ -1,5 +1,6 @@ -use std::{collections::LinkedList, cmp::Ordering, sync::Arc}; +use std::{collections::{LinkedList, BTreeMap}, cmp::Ordering, sync::Arc, iter::{Copied, Rev}}; +use boa_interner::Sym; use ion_rs::SymbolTable; use crate::ion::{IonReader, IonValue}; @@ -12,7 +13,14 @@ pub enum OpCode { Jump = 0x01, + Dup = 0x02, Dup2 = 0x03, + SwapPop = 0x04, + + Invoke = 0x05, + Yield = 0x06, + Return = 0x07, + /// Push a typed Ion value onto the stack. /// operands: T and L @@ -221,6 +229,10 @@ pub enum OpCode { /// stack: [{value1}, {value2}] -> [] IfLt2 = 0x3b, + + NewList = 0xB1, + NewStruct = 0xD1, + } impl OpCode { @@ -229,10 +241,17 @@ impl OpCode { } } +impl From<OpCode> for u8 { + fn from(value: OpCode) -> Self { + value.as_u8() + } +} + pub struct Runtime { symbols: SymbolTable, + bytecode: Arc<ByteCode>, + functions: BTreeMap<usize, Function>, stacks: LinkedList<StackFrame>, - functions: Vec<Arc<Function>>, } pub enum ExecutionState { @@ -240,11 +259,13 @@ pub enum ExecutionState { Halt, } +#[derive(Copy, Clone)] pub struct Function { - bytecode: ByteCode, - arguments: u16, - variables: u16, - expected_stack_depth: usize, + pub(crate) name_symbol: usize, + pub(crate) arguments: u16, + pub(crate) variables: u16, + pub(crate) pc: usize, + pub(crate) expected_stack_depth: usize, } pub type FnRef = usize; @@ -253,42 +274,30 @@ pub type ByteCode = Vec<u8>; struct Stack(Vec<u8>); pub struct StackFrame { - func: Arc<Function>, + bytecode: Arc<ByteCode>, pc: usize, variables: Vec<IonValue>, stack: Stack, } -impl Runtime { - pub fn new() -> Runtime { +impl Runtime { + pub fn new(symbols: SymbolTable, bytecode: ByteCode, functions: Vec<Function>) -> Runtime { Runtime { - symbols: SymbolTable::new(), + symbols, + functions: functions.into_iter().map(|f| (f.name_symbol, f)).collect(), + bytecode: bytecode.into(), stacks: LinkedList::new(), - functions: Vec::new(), } } - pub fn load_bytecode(&mut self, data: Vec<u8>) -> FnRef { - let arguments = (data[0] as u16) << 8 | (data[1] as u16); - let variables = (data[2] as u16) << 8 | (data[3] as u16); - let func = Function { - bytecode: data.into_iter().skip(4).collect(), - arguments, - variables, - expected_stack_depth: 32, - }; - self.functions.push(func.into()); - self.functions.len() - 1 - } - pub fn invoke(&mut self, fnref: FnRef, arguments: Vec<IonValue>) -> Vec<IonValue> { - let func = self.functions.get(fnref).expect("Undefined function").clone(); - let mut frame = StackFrame::new(func.clone(), arguments); + let func = *self.functions.get(&fnref).expect("Undefined function"); + let mut frame = StackFrame::new(self.bytecode.clone(), &func, arguments); loop { match self.execute(&mut frame) { ExecutionState::Continue => (), ExecutionState::Halt => { - frame.variables.truncate(func.arguments.into()); + //frame.variables.truncate(func.arguments.into()); return frame.variables; }, } @@ -301,17 +310,22 @@ impl Runtime { } let op = frame.next_byte(); - println!("PC: {:02X}, OP: {:02X}, Stack: {:02X}", frame.pc, op, frame.stack.0.len()); for x in &frame.stack.0 { print!(" {x:02X}"); } println!(); + println!("PC: {:02X}, OP: {:02X}", frame.pc - 1, op); match op { 0x01 => { // OpType::Jump - let pc = frame.next_varuint(); + let pc = frame.next_u32().try_into().unwrap(); frame.jump(pc); }, + 0x02 => { // OpType::Dup + let value1 = frame.stack.pop_value(); + frame.stack.push_value(&value1); + frame.stack.push_value(&value1); + }, 0x03 => { // OpType::Dup2 let value1 = frame.stack.pop_value(); let value2 = frame.stack.pop_value(); @@ -320,8 +334,13 @@ impl Runtime { frame.stack.push_value(&value2); frame.stack.push_value(&value1); }, + 0x04 => { // OpType::SwapPop + let value1 = frame.stack.pop_value(); + frame.stack.drop_value(); + frame.stack.push_value(&value1); + }, 0x10 => { // OpType::Push - let buf = &frame.func.bytecode[frame.pc..]; + let buf = &self.bytecode[frame.pc..]; let mut reader = IonReader::new(buf.iter().copied(), 0); let value = reader.next_value(); frame.pc += reader.offset(); @@ -349,14 +368,12 @@ impl Runtime { 0x17 => todo!(), // OpCode::ListLoad 0x18 => todo!(), // OpCode::FieldAppend 0x19 => { // OpCode::Iterate - let varid = frame.next_varuint(); - let value = frame.variables - .get(varid) - .expect("Undefined variable"); - - let mut reader = value.reader(); - let (ion_type, end) = reader.step_in(); - let pos = reader.offset(); + let (ion_type, end, pos) = { + let mut reader = frame.stack.peek_reader(); + let (ion_type, end) = reader.step_in(); + let pos = reader.offset(); + (ion_type, end, pos) + }; frame.stack.push_usize(ion_type as usize); frame.stack.push_usize(end); @@ -368,20 +385,16 @@ impl Runtime { let len = frame.stack.pop_value().to_usize(); let ion_type = frame.stack.pop_value().to_usize(); - let varid = frame.next_varuint(); - let mut value = if ion_type == 0x0D { - frame.variables - .get(varid) - .expect("Undefined variable") - .struct_reader_at(pos) - } else { - frame.variables - .get(varid) - .expect("Undefined variable") - .reader_at(pos) + let next = { + let mut reader = if ion_type == 0x0D { + frame.stack.peek_struct_reader_at(pos) + } else { + frame.stack.peek_reader_at(pos) + }; + reader.skip_value(); + reader.offset() }; - value.skip_value(); - let next = value.offset(); + frame.stack.push_usize(ion_type); // TODO peek frame.stack.push_usize(len); // TODO peek frame.stack.push_usize(next); @@ -391,26 +404,21 @@ impl Runtime { let len = frame.stack.pop_value().to_usize(); let ion_type = frame.stack.pop_value().to_usize(); + let (next_type, next_end, next_pos) = { + let mut reader = if ion_type == 0x0D { + frame.stack.peek_struct_reader_at(pos) + } else { + frame.stack.peek_reader_at(pos) + }; + let (next_type, next_end) = reader.step_in(); + let next_pos = reader.offset(); + (next_type, next_end, next_pos) + }; + frame.stack.push_usize(ion_type); // TODO peek frame.stack.push_usize(len); // TODO peek frame.stack.push_usize(pos); // TODO peek - let varid = frame.next_varuint(); - let mut value = if ion_type == 0x0D { - frame.variables - .get(varid) - .expect("Undefined variable") - .struct_reader_at(pos) - } else { - frame.variables - .get(varid) - .expect("Undefined variable") - .reader_at(pos) - }; - - let (next_type, next_end) = value.step_in(); - let next_pos = value.offset(); - frame.stack.push_usize(next_type as usize); frame.stack.push_usize(next_end); frame.stack.push_usize(next_pos); @@ -425,24 +433,19 @@ impl Runtime { let len = frame.stack.pop_value().to_usize(); let ion_type = frame.stack.pop_value().to_usize(); + let next_value = { + let mut reader = if ion_type == 0x0D { + frame.stack.peek_struct_reader_at(pos) + } else { + frame.stack.peek_reader_at(pos) + }; + reader.next_value() + }; + frame.stack.push_usize(ion_type); // TODO peek frame.stack.push_usize(len); // TODO peek frame.stack.push_usize(pos); // TODO peek - let varid = frame.next_varuint(); - let mut value = if ion_type == 0x0D { - frame.variables - .get(varid) - .expect("Undefined variable") - .struct_reader_at(pos) - } else { - frame.variables - .get(varid) - .expect("Undefined variable") - .reader_at(pos) - }; - - let next_value = value.next_value(); frame.stack.push_value(&next_value); }, 0x1E => { // OpCode::StructField @@ -450,25 +453,21 @@ impl Runtime { let len = frame.stack.pop_value().to_usize(); let ion_type = frame.stack.pop_value().to_usize(); + let field_id = { + let mut reader = if ion_type == 0x0D { + frame.stack.peek_struct_reader_at(pos) + } else { + frame.stack.peek_reader_at(pos) + }; + reader.skip_value(); + reader.field_id() + }; + frame.stack.push_usize(ion_type); // TODO peek frame.stack.push_usize(len); // TODO peek frame.stack.push_usize(pos); // TODO peek - let varid = frame.next_varuint(); - let mut value = if ion_type == 0x0D { - frame.variables - .get(varid) - .expect("Undefined variable") - .struct_reader_at(pos) - } else { - frame.variables - .get(varid) - .expect("Undefined variable") - .reader_at(pos) - }; - - value.skip_value(); - if let Some(field_id) = value.field_id() { + if let Some(field_id) = field_id { frame.stack.push_symbol(field_id); } else { panic!("Not a struct"); @@ -493,7 +492,7 @@ impl Runtime { 0x34 => todo!(), // OpCode::IfLe 0x35 => todo!(), // OpCode::IfLt 0x36 => { // OpCode::IfEq2 - let next_pc = frame.next_varuint(); + let next_pc = frame.next_u32().try_into().unwrap(); let value1 = frame.stack.pop_value(); let value2 = frame.stack.pop_value(); if value1 == value2 { @@ -501,7 +500,7 @@ impl Runtime { } }, 0x37 => { // OpCode::IfNe2 - let next_pc = frame.next_varuint(); + let next_pc = frame.next_u32().try_into().unwrap(); let value1 = frame.stack.pop_value(); let value2 = frame.stack.pop_value(); if value1 != value2 { @@ -509,7 +508,7 @@ impl Runtime { } }, 0x38 => { // OpCode::IfGe2 - let next_pc = frame.next_varuint(); + let next_pc = frame.next_u32().try_into().unwrap(); let value1 = frame.stack.pop_value(); let value2 = frame.stack.pop_value(); if value1 >= value2 { @@ -517,7 +516,7 @@ impl Runtime { } }, 0x39 => { // OpCode::IfGt2 - let next_pc = frame.next_varuint(); + let next_pc = frame.next_u32().try_into().unwrap(); let value1 = frame.stack.pop_value(); let value2 = frame.stack.pop_value(); if value1 > value2 { @@ -525,7 +524,7 @@ impl Runtime { } }, 0x3A => { // OpCode::IfLe2 - let next_pc = frame.next_varuint(); + let next_pc = frame.next_u32().try_into().unwrap(); let value1 = frame.stack.pop_value(); let value2 = frame.stack.pop_value(); if value1 <= value2 { @@ -533,14 +532,59 @@ impl Runtime { } }, 0x3B => { // OpCode::IfLt2 - let next_pc = frame.next_varuint(); + let next_pc = frame.next_u32().try_into().unwrap(); let value1 = frame.stack.pop_value(); let value2 = frame.stack.pop_value(); if value1 < value2 { frame.pc = next_pc; } }, - _ => panic!("Invalid opcode {:02x} at {}", op, frame.pc), + + 0xB1 => { // OpCode::NewList + // TODO: Yuck + let len = frame.stack.pop_usize(); + let mut list = Vec::new(); + let mut sz = 0; + for _ in 0..len { + let value = frame.stack.pop_value(); + sz += value.len(); + list.push(value); + } + for v in list { + frame.stack.push_value(&v); + } + if sz >= 14 { + frame.stack.push_varuint(sz); + frame.stack.push_byte(0xBE); + } else { + frame.stack.push_byte(0xB0 | (sz as u8)); + } + }, + + 0xD1 => { // OpCode::NewStruct + // TODO: Yuck + let len = frame.stack.pop_usize(); + let mut pairs = Vec::new(); + for _ in 0..len { + let sym = frame.stack.pop_value(); + let value = frame.stack.pop_value(); + pairs.push((sym, value)); + } + let mark = frame.stack.len(); + for (sym, v) in pairs { + frame.stack.push_value(&v); + frame.stack.push_varuint(sym.reader().next_symbol_id()); + } + let sz = frame.stack.len() - mark; + if sz >= 14 { + frame.stack.push_varuint(sz); + frame.stack.push_byte(0xDE); + } else { + frame.stack.push_byte(0xD0 | (sz as u8)); + } + }, + + _ => panic!("Invalid opcode {:02x} at {:02x}", op, frame.pc - 1), } ExecutionState::Continue @@ -551,17 +595,17 @@ impl Runtime { } } -impl StackFrame { - pub fn new(func: Arc<Function>, arguments: Vec<IonValue>) -> StackFrame { +impl StackFrame { + pub fn new(bytecode: Arc<ByteCode>, func: &Function, arguments: Vec<IonValue>) -> StackFrame { let stack = Stack::new(func.expected_stack_depth); let mut frame = StackFrame { - func, - pc: 0, + bytecode, + pc: func.pc, variables: arguments, stack, }; - for _ in frame.func.arguments..frame.func.variables { + for _ in func.arguments..func.variables { frame.variables.push(IonValue::new_null()); } @@ -573,22 +617,31 @@ impl StackFrame { } fn eof(&self) -> bool { - self.pc >= self.func.bytecode.len() + self.pc >= self.bytecode.len() } fn next_byte(&mut self) -> u8 { - let b = self.func.bytecode[self.pc]; + let b = self.bytecode[self.pc]; self.pc += 1; b } fn next_bytes(&mut self, len: usize) -> &[u8] { let end = self.pc + len; - let bytes = &self.func.bytecode[self.pc..end]; + let bytes = &self.bytecode[self.pc..end]; self.pc = end; bytes } + fn next_u32(&mut self) -> u32 { + let mut v: u32 = 0; + for _ in 0..4 { + v <<= 8; + v |= self.next_byte() as u32; + } + v + } + fn next_varuint(&mut self) -> usize { let mut b: usize = self.next_byte().into(); let mut v = b & 0x7f; @@ -606,10 +659,24 @@ impl Stack { Stack(Vec::with_capacity(expected_depth)) } - pub fn peak_reader(&self) -> IonReader<impl DoubleEndedIterator<Item = u8> + '_> { + pub fn len(&self) -> usize { + self.0.len() + } + + pub fn peek_reader(&self) -> IonReader<impl DoubleEndedIterator<Item = u8> + '_> { IonReader::new(self.0.iter().copied().rev(), 0) } + pub fn peek_reader_at(&self, offset: usize) -> IonReader<Rev<Copied<std::slice::Iter<'_, u8>>>> { + let end = self.0.len() - offset; + IonReader::new(self.0[..end].iter().copied().rev(), offset) + } + + pub fn peek_struct_reader_at(&self, offset: usize) -> IonReader<Rev<Copied<std::slice::Iter<'_, u8>>>> { + let end = self.0.len() - offset; + IonReader::new_struct(self.0[..end].iter().copied().rev(), offset) + } + pub fn drop_value(&mut self) { let mut it = IonReader::new(self.0.iter().copied().rev(), 0); it.skip_value(); @@ -625,25 +692,47 @@ impl Stack { value } + pub fn pop_usize(&mut self) -> usize { + let mut it = IonReader::new(self.0.iter().copied().rev(), 0); + let value = it.next_usize(); + let offset = it.offset(); + self.0.truncate(self.0.len() - offset); + value + } + + #[inline] + pub fn push_byte(&mut self, value: u8) { + self.0.push(value); + } + + pub fn push_varuint(&mut self, mut value: usize) { + self.push_byte((value & 0x7F | 0x80) as u8); + value >>= 7; + while value != 0 { + self.push_byte((value & 0x7F) as u8); + value >>= 7; + } + } + pub fn push_value(&mut self, value: &IonValue) { for byte in value.bytes().rev() { - self.0.push(byte); + self.push_byte(byte); } } pub fn push_symbol(&mut self, value: usize) { match value.cmp(&0) { - Ordering::Equal => self.0.push(0x70), + Ordering::Equal => self.push_byte(0x70), Ordering::Greater => { let mut v = value; let mut octets = 0; while v != 0 { - self.0.push((v & 0xFF) as u8); + self.push_byte((v & 0xFF) as u8); octets += 1; v >>= 8; } let tl = 0x70 | octets; - self.0.push(tl); + self.push_byte(tl); }, Ordering::Less => (), } @@ -651,17 +740,17 @@ impl Stack { pub fn push_usize(&mut self, value: usize) { match value.cmp(&0) { - Ordering::Equal => self.0.push(0x20), + Ordering::Equal => self.push_byte(0x20), Ordering::Greater => { let mut v = value; let mut octets = 0; while v != 0 { - self.0.push((v & 0xFF) as u8); + self.push_byte((v & 0xFF) as u8); octets += 1; v >>= 8; } let tl = 0x20 | octets; - self.0.push(tl); + self.push_byte(tl); }, Ordering::Less => (), } |