diff options
| -rw-r--r-- | src/compiler.rs | 159 | ||||
| -rw-r--r-- | src/vm.rs | 145 | ||||
| -rw-r--r-- | tests/simple.tdy | 22 |
3 files changed, 274 insertions, 52 deletions
diff --git a/src/compiler.rs b/src/compiler.rs index 1a6cfc6..ad97783 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -79,7 +79,7 @@ impl From<&Value> for Type { Value::Float(_) => Type::Float, Value::Bool(_) => Type::Bool, Value::String(_) => Type::String, - Value::Function(block) => block.ty.clone(), + Value::Function(_, block) => block.ty.clone(), _ => Type::Void, } } @@ -94,24 +94,69 @@ impl Type { Type::Float => Value::Float(1.0), Type::Bool => Value::Bool(true), Type::String => Value::String(Rc::new("".to_string())), - Type::Function(_, _) => Value::Function(Rc::new(Block::from_type(self))), + Type::Function(_, _) => Value::Function( + Vec::new(), + Rc::new(Block::from_type(self))), } } } +#[derive(Clone)] struct Variable { name: String, typ: Type, scope: usize, + slot: usize, + + outer_slot: usize, + outer_upvalue: bool, + active: bool, + upvalue: bool, + captured: bool, } struct Frame { stack: Vec<Variable>, + upvalues: Vec<Variable>, scope: usize, variables_below: usize, } +impl Frame { + fn find_local(&self, name: &str) -> Option<Variable> { + for var in self.stack.iter().rev() { + if var.name == name && var.active { + return Some(var.clone()); + } + } + None + } + + fn find_upvalue(&self, name: &str) -> Option<Variable> { + for var in self.upvalues.iter().rev() { + if var.name == name && var.active { + return Some(var.clone()); + } + } + None + } + + fn add_upvalue(&mut self, variable: Variable) -> Variable { + println!("{} - UPDOG", variable.name); + let new_variable = Variable { + outer_upvalue: variable.upvalue, + outer_slot: variable.slot, + slot: self.upvalues.len(), + active: true, + upvalue: true, + ..variable + }; + self.upvalues.push(new_variable.clone()); + new_variable + } +} + struct Compiler { curr: usize, tokens: TokenStream, @@ -130,6 +175,7 @@ macro_rules! push_frame { { $compiler.frames.push(Frame { stack: Vec::new(), + upvalues: Vec::new(), scope: 0, variables_below: $compiler.frame().variables_below + $compiler.stack().len(), }); @@ -154,8 +200,13 @@ macro_rules! push_scope { $code; $compiler.frame_mut().scope -= 1; - for _ in ss..$compiler.stack().len() { - $block.add(Op::Pop, $compiler.line()); + + for var in $compiler.frame().stack[ss..$compiler.stack().len()].iter().rev() { + if var.captured { + $block.add(Op::PopUpvalue, $compiler.line()); + } else { + $block.add(Op::Pop, $compiler.line()); + } } $compiler.stack_mut().truncate(ss); }; @@ -170,6 +221,7 @@ impl Compiler { frames: vec![Frame { stack: Vec::new(), + upvalues: Vec::new(), scope: 0, variables_below: 0, }], @@ -388,16 +440,36 @@ impl Compiler { } } - fn find_local(&self, name: &str, _block: &Block) -> Option<(usize, Type, usize)> { - let frame = self.frame(); - for (slot, var) in frame.stack.iter().enumerate().rev() { - if var.name == name && var.active { - return Some((slot, var.typ.clone(), var.scope)); + fn find_and_capture_variable<'a, I>(name: &str, mut iterator: I) -> Option<Variable> + where I: Iterator<Item = &'a mut Frame> { + if let Some(frame) = iterator.next() { + if let Some(res) = frame.find_local(name) { + frame.stack[res.slot].captured = true; + return Some(res); + } + if let Some(res) = frame.find_upvalue(name) { + return Some(res); + } + + if let Some(res) = Self::find_and_capture_variable(name, iterator) { + return Some(frame.add_upvalue(res)); } } None } + fn find_variable(&mut self, name: &str) -> Option<Variable> { + if let Some(res) = self.frame().find_local(name) { + return Some(res); + } + + if let Some(res) = self.frame().find_upvalue(name) { + return Some(res); + } + + return Self::find_and_capture_variable(name, self.frames.iter_mut().rev()); + } + fn call(&mut self, block: &mut Block) { expect!(self, Token::LeftParen, "Expected '(' at start of function call."); @@ -423,17 +495,15 @@ impl Compiler { } block.add(Op::Call(arity), self.line()); - - for _ in 0..arity { - block.add(Op::Pop, self.line()); - } } fn function(&mut self, block: &mut Block) { expect!(self, Token::Fn, "Expected 'fn' at start of function."); - let name = if !self.stack()[self.stack().len() - 1].active { - &self.stack()[self.stack().len() - 1].name + let top = self.stack().len() - 1; + let name = if !self.stack()[top].active { + self.stack_mut()[top].active = true; + &self.stack()[top].name } else { "anonumus function" }; @@ -441,6 +511,7 @@ impl Compiler { let mut args = Vec::new(); let mut return_type = Type::Void; let mut function_block = Block::new(name, &self.current_file, self.line()); + let _ret = push_frame!(self, function_block, { loop { match self.peek() { @@ -479,17 +550,35 @@ impl Compiler { } self.scope(&mut function_block); + + for var in self.frame().upvalues.iter() { + function_block.ups.push((var.outer_slot, var.outer_upvalue, var.typ.clone())); + } + println!("{:?}", function_block.ups); + // TODO(ed): Send the original place to find the upvalues, + // so we know from where to copy them. }); - if !matches!(function_block.last_op(), Some(&Op::Return)) { - function_block.add(Op::Constant(Value::Nil), self.line()); - function_block.add(Op::Return, self.line()); + let mut prev = function_block.ops.len() - 1; + loop { + match function_block.ops[prev] { + Op::Pop | Op::PopUpvalue => {} + Op::Return => { break; } , + _ => { + function_block.add(Op::Constant(Value::Nil), self.line()); + function_block.add(Op::Return, self.line()); + break; + } + } + prev -= 1; } function_block.ty = Type::Function(args, Box::new(return_type)); let function_block = Rc::new(function_block); - block.add(Op::Constant(Value::Function(Rc::clone(&function_block))), self.line()); + + let func = Op::Constant(Value::Function(Vec::new(), Rc::clone(&function_block))); + block.add(func, self.line()); self.blocks.push(function_block); } @@ -498,16 +587,20 @@ impl Compiler { Token::Identifier(name) => name, __ => unreachable!(), }; - if let Some((slot, _, _)) = self.find_local(&name, block) { - block.add(Op::ReadLocal(slot), self.line()); + if let Some(var) = self.find_variable(&name) { + if var.upvalue { + block.add(Op::ReadUpvalue(var.slot), self.line()); + } else { + block.add(Op::ReadLocal(var.slot), self.line()); + } } else { error!(self, format!("Using undefined variable {}.", name)); } } fn define_variable(&mut self, name: &str, typ: Type, block: &mut Block) -> Result<usize, ()> { - if let Some((_, _, level)) = self.find_local(&name, block) { - if level == self.frame().scope { + if let Some(var) = self.find_variable(&name) { + if var.scope == self.frame().scope { error!(self, format!("Multiple definitions of {} in this block.", name)); return Err(()); } @@ -517,9 +610,14 @@ impl Compiler { let scope = self.frame().scope; self.stack_mut().push(Variable { name: String::from(name), + captured: false, + outer_upvalue: false, + outer_slot: 0, + slot, typ, scope, - active: false + active: false, + upvalue: false, }); Ok(slot) } @@ -535,9 +633,13 @@ impl Compiler { } fn assign(&mut self, name: &str, block: &mut Block) { - if let Some((slot, _, _)) = self.find_local(&name, block) { + if let Some(var) = self.find_variable(&name) { self.expression(block); - block.add(Op::Assign(slot), self.line()); + if var.upvalue { + block.add(Op::AssignUpvalue(var.slot), self.line()); + } else { + block.add(Op::AssignLocal(var.slot), self.line()); + } } else { error!(self, format!("Using undefined variable {}.", name)); } @@ -747,8 +849,13 @@ impl Compiler { self.stack_mut().push(Variable { name: String::from("/main/"), typ: Type::Void, + outer_upvalue: false, + outer_slot: 0, + slot: 0, scope: 0, active: false, + captured: false, + upvalue: false, }); let mut block = Block::new(name, file, 0); @@ -3,6 +3,7 @@ use std::collections::HashMap; use std::fmt::Debug; use std::path::{Path, PathBuf}; use std::rc::Rc; +use std::cell::RefCell; use crate::compiler::Type; use crate::error::{Error, ErrorKind}; @@ -22,11 +23,53 @@ pub enum Value { Int(i64), Bool(bool), String(Rc<String>), - Function(Rc<Block>), + Function(Vec<Rc<RefCell<UpValue>>>, Rc<Block>), Unkown, Nil, } +#[derive(Clone, Debug)] +pub struct UpValue { + slot: usize, + value: Value, +} + +impl UpValue { + + fn new(value: usize) -> Self { + Self { + slot: value, + value: Value::Nil, + } + } + + fn get(&self, stack: &[Value]) -> Value { + if self.is_closed() { + self.value.clone() + } else { + stack[self.slot].clone() + } + } + + fn set(&mut self, stack: &mut [Value], value: Value) { + if self.is_closed() { + self.value = value; + } else { + stack[self.slot] = value; + } + } + + + fn is_closed(&self) -> bool { + self.slot == 0 + } + + fn close(&mut self, value: Value) { + self.slot = 0; + self.value = value; + } +} + impl Debug for Value { fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { match self { @@ -34,7 +77,7 @@ impl Debug for Value { Value::Int(i) => write!(fmt, "(int {})", i), Value::Bool(b) => write!(fmt, "(bool {})", b), Value::String(s) => write!(fmt, "(string \"{}\")", s), - Value::Function(block) => write!(fmt, "(fn {}: {:?})", block.name, block.ty), + Value::Function(_, block) => write!(fmt, "(fn {}: {:?})", block.name, block.ty), Value::Unkown => write!(fmt, "(unkown)"), Value::Nil => write!(fmt, "(nil)"), } @@ -57,7 +100,7 @@ impl Value { Value::Int(_) => Type::Int, Value::Bool(_) => Type::Bool, Value::String(_) => Type::String, - Value::Function(block) => block.ty.clone(), + Value::Function(_, block) => block.ty.clone(), Value::Unkown => Type::UnknownType, Value::Nil => Type::Void, } @@ -69,6 +112,7 @@ pub enum Op { Illegal, Pop, + PopUpvalue, Constant(Value), Add, @@ -92,7 +136,10 @@ pub enum Op { Unreachable, ReadLocal(usize), - Assign(usize), + AssignLocal(usize), + + ReadUpvalue(usize), + AssignUpvalue(usize), Define(Type), @@ -105,6 +152,7 @@ pub enum Op { #[derive(Debug)] pub struct Block { pub ty: Type, + pub ups: Vec<(usize, bool, Type)>, pub name: String, pub file: PathBuf, @@ -118,6 +166,7 @@ impl Block { pub fn new(name: &str, file: &Path, line: usize) -> Self { Self { ty: Type::Void, + ups: Vec::new(), name: String::from(name), file: file.to_owned(), ops: Vec::new(), @@ -222,6 +271,8 @@ struct Frame { #[derive(Debug)] pub struct VM { + upvalues: HashMap<usize, Rc<RefCell<UpValue>>>, + stack: Vec<Value>, frames: Vec<Frame>, print_blocks: bool, @@ -236,6 +287,7 @@ enum OpResult { impl VM { pub fn new() -> Self { Self { + upvalues: HashMap::new(), stack: Vec::new(), frames: Vec::new(), print_blocks: false, @@ -253,6 +305,11 @@ impl VM { self } + fn find_upvalue(&mut self, slot: usize) -> &mut Rc<RefCell<UpValue>> { + self.upvalues.entry(slot).or_insert( + Rc::new(RefCell::new(UpValue::new(slot)))) + } + fn pop(&mut self) -> Value { self.stack.pop().unwrap() } @@ -304,11 +361,37 @@ impl VM { } Op::Pop => { - self.stack.pop(); + self.stack.pop().unwrap(); + } + + Op::PopUpvalue => { + self.stack.pop().unwrap(); } Op::Constant(value) => { - self.stack.push(value.clone()); + let offset = self.frame().stack_offset; + let value = match value { + Value::Function(_, block) => { + let mut ups = Vec::new(); + println!("UPS: {:?}", block.ups); + for (slot, is_up, _) in block.ups.iter() { + let up = if *is_up { + if let Value::Function(local_ups, _) = &self.stack[offset] { + Rc::clone(&local_ups[*slot]) + } else { + unreachable!() + } + } else { + let slot = self.frame().stack_offset + slot; + Rc::clone(self.find_upvalue(slot)) + }; + ups.push(up); + } + Value::Function(ups, block) + }, + _ => value.clone(), + }; + self.stack.push(value); } Op::Neg => { @@ -424,12 +507,33 @@ impl VM { self.stack.push(Value::Bool(true)); } + Op::ReadUpvalue(slot) => { + let offset = self.frame().stack_offset; + let value = match &self.stack[offset] { + Value::Function(ups, _) => { + ups[slot].borrow().get(&self.stack) + } + _ => unreachable!(), + }; + self.stack.push(value); + } + + Op::AssignUpvalue(slot) => { + let offset = self.frame().stack_offset; + let value = self.stack.pop().unwrap(); + let slot = match &self.stack[offset] { + Value::Function(ups, _) => Rc::clone(&ups[slot]), + _ => unreachable!(), + }; + slot.borrow_mut().set(&mut self.stack, value); + } + Op::ReadLocal(slot) => { let slot = self.frame().stack_offset + slot; self.stack.push(self.stack[slot].clone()); } - Op::Assign(slot) => { + Op::AssignLocal(slot) => { let slot = self.frame().stack_offset + slot; self.stack[slot] = self.stack.pop().unwrap(); } @@ -439,7 +543,7 @@ impl VM { Op::Call(num_args) => { let new_base = self.stack.len() - 1 - num_args; match &self.stack[new_base] { - Value::Function(block) => { + Value::Function(_, block) => { let args = block.args(); if args.len() != num_args { error!(self, @@ -473,6 +577,7 @@ impl VM { return Ok(OpResult::Done); } else { self.stack[last.stack_offset] = self.stack.pop().unwrap(); + self.stack.truncate(last.stack_offset + 1); } } } @@ -501,7 +606,7 @@ impl VM { self.stack.clear(); self.frames.clear(); - self.stack.push(Value::Function(Rc::clone(&block))); + self.stack.push(Value::Function(Vec::new(), Rc::clone(&block))); self.frames.push(Frame { stack_offset: 0, @@ -531,6 +636,23 @@ impl VM { Op::Jmp(_line) => {} + Op::Constant(value) => { + self.stack.push(value.clone()); + } + + Op::ReadUpvalue(slot) => { + self.stack.push(self.frame().block.ups[slot].2.as_value()); + } + + Op::AssignUpvalue(slot) => { + let var = self.frame().block.ups[slot].2.clone(); + let up = self.stack.pop().unwrap().as_type(); + if var != up { + error!(self, ErrorKind::TypeError(op, vec![var, up]), + "Incorrect type for upvalue.".to_string()); + } + } + Op::Return => { let a = self.stack.pop().unwrap(); let ret = self.frame().block.ret(); @@ -565,7 +687,7 @@ impl VM { Op::Call(num_args) => { let new_base = self.stack.len() - 1 - num_args; match &self.stack[new_base] { - Value::Function(block) => { + Value::Function(_, block) => { let args = block.args(); if args.len() != num_args { error!(self, @@ -612,7 +734,7 @@ impl VM { self.stack.clear(); self.frames.clear(); - self.stack.push(Value::Function(Rc::clone(&block))); + self.stack.push(Value::Function(Vec::new(), Rc::clone(&block))); for arg in block.args() { self.stack.push(arg.as_value()); } @@ -656,6 +778,7 @@ impl VM { let mut errors = Vec::new(); for block in blocks.iter() { + let ups: Vec<_> = block.ups.iter().map(|x| x.2.as_value()).collect(); errors.append(&mut self.typecheck_block(Rc::clone(block))); } diff --git a/tests/simple.tdy b/tests/simple.tdy index f7929f4..28bd5e2 100644 --- a/tests/simple.tdy +++ b/tests/simple.tdy @@ -1,19 +1,11 @@ -a : fn int, int -> int = fn b: int, c: int -> int { - ret b + c +fac : fn int -> int = fn a: int -> int { + if a <= 1 { + ret 1 + } + b := fac(a - 1) + ret a * b } - -print a(1, 2) + 1 - -b := fn c: fn int -> -> int { - c(2) - ret 1 -} - -c := fn a: int { - print a -} - -b(c) +print fac(5) // print b(fn a: int -> { // print a |