From d200cad16a3582d80855b379d55fd759995c4444 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Mon, 18 Jan 2021 22:16:19 +0100 Subject: big think, no progress --- src/compiler.rs | 40 ++++++++++++++++++++++++++++++++++------ 1 file changed, 34 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index 1a6cfc6..ecd0180 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -104,14 +104,33 @@ struct Variable { typ: Type, scope: usize, active: bool, + upvalue: bool, } struct Frame { stack: Vec, + upvalues: Vec<(usize, Variable, bool)>, scope: usize, variables_below: usize, } +impl Frame { + fn find_local(&self, name: &str) -> Option<(usize, Type, usize, bool)> { + for (slot, var) in self.stack.iter().enumerate().rev() { + if var.name == name && var.active { + return Some((slot, var.typ.clone(), var.scope, false)); + } + } + None + } + + fn find_upvalue(&self, name: &str) -> Option<(usize, Type, usize, bool)> { + for (slot, upvalue) in self.upvalues.iter().enumerate() { + //TODO ?? + } + } +} + struct Compiler { curr: usize, tokens: TokenStream, @@ -388,11 +407,18 @@ 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_upvalue(&self, name: &str, start_at: usize) -> Option<(usize, Type, usize, bool)> { + + } + + fn find_variable(&mut self, name: &str, mut iterator: I) -> Option<(usize, Type, usize, bool)> + where I: Iterator { + if let Some(frame) = i.next() { + if let Some(res) = frame.find_local(name) { + return Some(res); + } + if let Some(res) = frame.find_upvalue(name) { + return Some(res); } } None @@ -519,7 +545,8 @@ impl Compiler { name: String::from(name), typ, scope, - active: false + active: false, + upvalue: false, }); Ok(slot) } @@ -749,6 +776,7 @@ impl Compiler { typ: Type::Void, scope: 0, active: false, + upvalue: false, }); let mut block = Block::new(name, file, 0); -- cgit v1.2.1 From 85411e444826fc239fb268da03572993d9c9fd83 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Wed, 20 Jan 2021 21:04:18 +0100 Subject: Add in upvalues --- src/compiler.rs | 112 +++++++++++++++++++++++++++++++++++++++++++------------- src/vm.rs | 102 ++++++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 179 insertions(+), 35 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index ecd0180..c4afbf3 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,40 +94,64 @@ 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, active: bool, upvalue: bool, + captured: bool, } struct Frame { stack: Vec, - upvalues: Vec<(usize, Variable, bool)>, + upvalues: Vec, scope: usize, variables_below: usize, } impl Frame { - fn find_local(&self, name: &str) -> Option<(usize, Type, usize, bool)> { - for (slot, var) in self.stack.iter().enumerate().rev() { + fn find_local(&self, name: &str) -> Option { + println!("LOCAL!"); + for var in self.stack.iter().rev() { if var.name == name && var.active { - return Some((slot, var.typ.clone(), var.scope, false)); + return Some(var.clone()); } } None } - fn find_upvalue(&self, name: &str) -> Option<(usize, Type, usize, bool)> { - for (slot, upvalue) in self.upvalues.iter().enumerate() { - //TODO ?? + fn find_upvalue(&self, name: &str) -> Option { + println!("UPVALUE!"); + 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_slot: variable.slot, + slot: self.upvalues.len(), + active: true, + upvalue: true, + ..variable + }; + self.upvalues.push(new_variable.clone()); + new_variable } } @@ -149,6 +173,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(), }); @@ -173,8 +198,12 @@ 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); }; @@ -189,6 +218,7 @@ impl Compiler { frames: vec![Frame { stack: Vec::new(), + upvalues: Vec::new(), scope: 0, variables_below: 0, }], @@ -407,23 +437,36 @@ impl Compiler { } } - fn find_upvalue(&self, name: &str, start_at: usize) -> Option<(usize, Type, usize, bool)> { - - } - - fn find_variable(&mut self, name: &str, mut iterator: I) -> Option<(usize, Type, usize, bool)> - where I: Iterator { - if let Some(frame) = i.next() { + fn find_and_capture_variable<'a, I>(name: &str, mut iterator: I) -> Option + where I: Iterator { + 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 { + 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."); @@ -467,6 +510,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() { @@ -505,6 +549,8 @@ impl Compiler { } self.scope(&mut function_block); + // 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)) { @@ -515,7 +561,9 @@ impl Compiler { 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); } @@ -524,16 +572,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 { - 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(()); } @@ -543,6 +595,9 @@ impl Compiler { let scope = self.frame().scope; self.stack_mut().push(Variable { name: String::from(name), + captured: false, + outer_slot: 0, + slot, typ, scope, active: false, @@ -562,9 +617,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)); } @@ -774,8 +833,11 @@ impl Compiler { self.stack_mut().push(Variable { name: String::from("/main/"), typ: Type::Void, + outer_slot: 0, + slot: 0, scope: 0, active: false, + captured: false, upvalue: false, }); diff --git a/src/vm.rs b/src/vm.rs index 3041628..7b48b4e 100644 --- a/src/vm.rs +++ b/src/vm.rs @@ -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), - Function(Rc), + Function(Vec>>, Rc), 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, 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>>, + stack: Vec, frames: Vec, 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> { + self.upvalues.entry(slot).or_insert( + Rc::new(RefCell::new(UpValue::new(slot)))) + } + fn pop(&mut self) -> Value { self.stack.pop().unwrap() } @@ -304,7 +361,11 @@ impl VM { } Op::Pop => { - self.stack.pop(); + self.stack.pop().unwrap(); + } + + Op::PopUpvalue => { + self.stack.pop().unwrap(); } Op::Constant(value) => { @@ -424,12 +485,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 +521,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, @@ -501,7 +583,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, @@ -565,7 +647,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 +694,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()); } -- cgit v1.2.1 From d13695d2452e0468168240800a4cde88f220b646 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Wed, 20 Jan 2021 21:26:14 +0100 Subject: Typecheck upvalues --- src/compiler.rs | 11 +++++++++++ src/vm.rs | 18 ++++++++++++++++-- 2 files changed, 27 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index c4afbf3..b7dad75 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -107,7 +107,10 @@ struct Variable { typ: Type, scope: usize, slot: usize, + outer_slot: usize, + outer_upvalue: bool, + active: bool, upvalue: bool, captured: bool, @@ -144,6 +147,7 @@ impl Frame { 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, @@ -549,6 +553,11 @@ 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. }); @@ -596,6 +605,7 @@ impl Compiler { self.stack_mut().push(Variable { name: String::from(name), captured: false, + outer_upvalue: false, outer_slot: 0, slot, typ, @@ -833,6 +843,7 @@ impl Compiler { self.stack_mut().push(Variable { name: String::from("/main/"), typ: Type::Void, + outer_upvalue: false, outer_slot: 0, slot: 0, scope: 0, diff --git a/src/vm.rs b/src/vm.rs index 7b48b4e..abe7874 100644 --- a/src/vm.rs +++ b/src/vm.rs @@ -152,7 +152,7 @@ pub enum Op { #[derive(Debug)] pub struct Block { pub ty: Type, - pub ups: Vec, + pub ups: Vec<(usize, bool, Type)>, pub name: String, pub file: PathBuf, @@ -521,7 +521,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(ups, block) => { let args = block.args(); if args.len() != num_args { error!(self, @@ -613,6 +613,19 @@ impl VM { Op::Jmp(_line) => {} + 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(); @@ -738,6 +751,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))); } -- cgit v1.2.1 From 5d43ce4ab4b9c8d3ca8a0cb21f99b25e87e58fb4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Wed, 20 Jan 2021 22:30:57 +0100 Subject: Calling of functions, in functions --- src/compiler.rs | 28 +++++++++++++++++----------- src/vm.rs | 31 +++++++++++++++++++++++++++++-- 2 files changed, 46 insertions(+), 13 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index b7dad75..ad97783 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -125,7 +125,6 @@ struct Frame { impl Frame { fn find_local(&self, name: &str) -> Option { - println!("LOCAL!"); for var in self.stack.iter().rev() { if var.name == name && var.active { return Some(var.clone()); @@ -135,7 +134,6 @@ impl Frame { } fn find_upvalue(&self, name: &str) -> Option { - println!("UPVALUE!"); for var in self.upvalues.iter().rev() { if var.name == name && var.active { return Some(var.clone()); @@ -202,6 +200,7 @@ macro_rules! push_scope { $code; $compiler.frame_mut().scope -= 1; + for var in $compiler.frame().stack[ss..$compiler.stack().len()].iter().rev() { if var.captured { $block.add(Op::PopUpvalue, $compiler.line()); @@ -496,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" }; @@ -562,9 +559,18 @@ impl Compiler { // 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)); diff --git a/src/vm.rs b/src/vm.rs index abe7874..cb2285f 100644 --- a/src/vm.rs +++ b/src/vm.rs @@ -369,7 +369,29 @@ impl VM { } 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 => { @@ -521,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(ups, block) => { + Value::Function(_, block) => { let args = block.args(); if args.len() != num_args { error!(self, @@ -555,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); } } } @@ -613,6 +636,10 @@ 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()); } -- cgit v1.2.1 From 914bc87fd0525ce042d279bff6a4c97477bfeb61 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Wed, 20 Jan 2021 22:56:30 +0100 Subject: allow empty functions --- src/compiler.rs | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index ad97783..727f177 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -559,9 +559,8 @@ impl Compiler { // so we know from where to copy them. }); - let mut prev = function_block.ops.len() - 1; - loop { - match function_block.ops[prev] { + for op in function_block.ops.iter().rev() { + match op { Op::Pop | Op::PopUpvalue => {} Op::Return => { break; } , _ => { @@ -570,7 +569,11 @@ impl Compiler { break; } } - prev -= 1; + } + + if function_block.ops.is_empty() { + function_block.add(Op::Constant(Value::Nil), self.line()); + function_block.add(Op::Return, self.line()); } function_block.ty = Type::Function(args, Box::new(return_type)); -- cgit v1.2.1 From 34fc35ce55fa31b30cbb3491b0bce9c2289abbdc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Wed, 20 Jan 2021 22:56:50 +0100 Subject: trailing comma on nextable enum --- src/compiler.rs | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index 727f177..e45e611 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -6,7 +6,7 @@ use crate::tokenizer::{Token, TokenStream}; use crate::vm::{Value, Block, Op}; macro_rules! nextable_enum { - ( $name:ident { $( $thing:ident ),* } ) => { + ( $name:ident { $( $thing:ident ),* $( , )? } ) => { #[derive(PartialEq, PartialOrd, Clone, Copy, Debug)] enum $name { $( $thing, )* @@ -43,7 +43,7 @@ nextable_enum!(Prec { Bool, Comp, Term, - Factor + Factor, }); #[derive(Debug, Clone)] -- cgit v1.2.1 From 13cf2875b0e1ae66c7bbb77745225cb01aa2e3a7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Wed, 20 Jan 2021 23:07:46 +0100 Subject: also truncate in typechecker --- src/vm.rs | 2 ++ 1 file changed, 2 insertions(+) (limited to 'src') diff --git a/src/vm.rs b/src/vm.rs index cb2285f..c5891f4 100644 --- a/src/vm.rs +++ b/src/vm.rs @@ -706,6 +706,8 @@ impl VM { } self.stack[new_base] = block.ret().as_value(); + + self.stack.truncate(new_base + 1); }, _ => { error!(self, -- cgit v1.2.1 From 1626c2bb70e369c25bbd0fe713bf03e3ff52dff6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Wed, 20 Jan 2021 23:11:49 +0100 Subject: parse function precedence --- src/compiler.rs | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index e45e611..aca1b26 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -363,8 +363,6 @@ impl Compiler { | Token::NotEqual => self.binary(block), - Token::LeftParen => self.call(block), - _ => { return false; }, } return true; @@ -596,6 +594,9 @@ impl Compiler { } else { block.add(Op::ReadLocal(var.slot), self.line()); } + if self.peek() == Token::LeftParen { + self.call(block); + } } else { error!(self, format!("Using undefined variable {}.", name)); } -- cgit v1.2.1 From f663999eccd693ddbfd581a51213b816c461f092 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Wed, 20 Jan 2021 23:45:36 +0100 Subject: add recursive tests --- src/lib.rs | 25 +++++++++++++++++++++++-- 1 file changed, 23 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/lib.rs b/src/lib.rs index 82905de..328d3ea 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -169,7 +169,7 @@ mod tests { simplest: "f := fn {} f()", param_1: "f := fn a: int {} - f(1)", + f(1)", return_1: "f := fn -> int { ret 1 } @@ -222,7 +222,28 @@ mod tests { } 1 + f(2, 3) <=> 6 2 * f(2, 3) <=> 10 - f(2, 3) - (2 + 3) <=> 0" + f(2, 3) - (2 + 3) <=> 0", + factorial: "factorial : fn int -> int = fn n: int -> int { + if n <= 1 { + ret 1 + } + ret n * factorial(n - 1) + } + factorial(5) <=> 120 + factorial(6) <=> 720 + factorial(12) <=> 479001600", + fibonacci: "fibonacci : fn int -> int = fn n: int -> int { + if n == 0 { + ret 0 + } else if n == 1 { + ret 1 + } else if n < 0 { + + } + ret fibonacci(n - 1) + fibonacci(n - 2) + } + fibonacci(10) <=> 55 + fibonacci(20) <=> 6765" ); test_file!(scoping, "tests/scoping.tdy"); -- cgit v1.2.1 From 9626aa05496a0e745252ba30bf64e8d020c6ec2a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Wed, 20 Jan 2021 23:45:47 +0100 Subject: cleanup --- src/compiler.rs | 8 ++------ src/vm.rs | 3 +-- 2 files changed, 3 insertions(+), 8 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index aca1b26..d72b8d3 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -143,7 +143,6 @@ impl Frame { } fn add_upvalue(&mut self, variable: Variable) -> Variable { - println!("{} - UPDOG", variable.name); let new_variable = Variable { outer_upvalue: variable.upvalue, outer_slot: variable.slot, @@ -552,9 +551,6 @@ impl Compiler { 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. }); for op in function_block.ops.iter().rev() { @@ -586,7 +582,7 @@ impl Compiler { fn variable_expression(&mut self, block: &mut Block) { let name = match self.eat() { Token::Identifier(name) => name, - __ => unreachable!(), + _ => unreachable!(), }; if let Some(var) = self.find_variable(&name) { if var.upvalue { @@ -602,7 +598,7 @@ impl Compiler { } } - fn define_variable(&mut self, name: &str, typ: Type, block: &mut Block) -> Result { + fn define_variable(&mut self, name: &str, typ: Type, _block: &mut Block) -> Result { if let Some(var) = self.find_variable(&name) { if var.scope == self.frame().scope { error!(self, format!("Multiple definitions of {} in this block.", name)); diff --git a/src/vm.rs b/src/vm.rs index c5891f4..56b87f0 100644 --- a/src/vm.rs +++ b/src/vm.rs @@ -373,7 +373,6 @@ impl VM { 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] { @@ -743,7 +742,7 @@ impl VM { self.frames.push(Frame { stack_offset: 0, - block: block, + block, ip: 0 }); -- cgit v1.2.1 From dc0014f9007fa96fb37f5b03779fc003b0ce54ad Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Wed, 20 Jan 2021 23:56:42 +0100 Subject: todo --- src/lib.rs | 1 + 1 file changed, 1 insertion(+) (limited to 'src') diff --git a/src/lib.rs b/src/lib.rs index 328d3ea..4352ae1 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -232,6 +232,7 @@ mod tests { factorial(5) <=> 120 factorial(6) <=> 720 factorial(12) <=> 479001600", + //TODO this tests doesn't terminate in proper time if we print blocks and ops fibonacci: "fibonacci : fn int -> int = fn n: int -> int { if n == 0 { ret 0 -- cgit v1.2.1 From d261da01634c5fd62cd68f8c9c39a89422bdd398 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Thu, 21 Jan 2021 19:55:22 +0100 Subject: Rc> and closing upvalues --- src/compiler.rs | 15 ++++++------ src/lib.rs | 2 ++ src/vm.rs | 76 ++++++++++++++++++++++++++++++++++----------------------- 3 files changed, 56 insertions(+), 37 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index d72b8d3..409d6a6 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -1,5 +1,6 @@ use std::path::{Path, PathBuf}; use std::rc::Rc; +use std::cell::RefCell; use crate::error::{Error, ErrorKind}; use crate::tokenizer::{Token, TokenStream}; @@ -79,7 +80,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.borrow().ty.clone(), _ => Type::Void, } } @@ -96,7 +97,7 @@ impl Type { Type::String => Value::String(Rc::new("".to_string())), Type::Function(_, _) => Value::Function( Vec::new(), - Rc::new(Block::from_type(self))), + Rc::new(RefCell::new(Block::from_type(self)))), } } } @@ -166,7 +167,7 @@ struct Compiler { panic: bool, errors: Vec, - blocks: Vec>, + blocks: Vec>>, } macro_rules! push_frame { @@ -571,7 +572,7 @@ impl Compiler { } function_block.ty = Type::Function(args, Box::new(return_type)); - let function_block = Rc::new(function_block); + let function_block = Rc::new(RefCell::new(function_block)); let func = Op::Constant(Value::Function(Vec::new(), Rc::clone(&function_block))); @@ -845,7 +846,7 @@ impl Compiler { } - pub fn compile(&mut self, name: &str, file: &Path) -> Result>, Vec> { + pub fn compile(&mut self, name: &str, file: &Path) -> Result>>, Vec> { self.stack_mut().push(Variable { name: String::from("/main/"), typ: Type::Void, @@ -867,7 +868,7 @@ impl Compiler { block.add(Op::Return, self.line()); block.ty = Type::Function(Vec::new(), Box::new(Type::Void)); - self.blocks.insert(0, Rc::new(block)); + self.blocks.insert(0, Rc::new(RefCell::new(block))); if self.errors.is_empty() { Ok(self.blocks.clone()) @@ -877,6 +878,6 @@ impl Compiler { } } -pub fn compile(name: &str, file: &Path, tokens: TokenStream) -> Result>, Vec> { +pub fn compile(name: &str, file: &Path, tokens: TokenStream) -> Result>>, Vec> { Compiler::new(file, tokens).compile(name, file) } diff --git a/src/lib.rs b/src/lib.rs index 4352ae1..794bbea 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -233,6 +233,7 @@ mod tests { factorial(6) <=> 720 factorial(12) <=> 479001600", //TODO this tests doesn't terminate in proper time if we print blocks and ops + /* fibonacci: "fibonacci : fn int -> int = fn n: int -> int { if n == 0 { ret 0 @@ -245,6 +246,7 @@ mod tests { } fibonacci(10) <=> 55 fibonacci(20) <=> 6765" + */ ); test_file!(scoping, "tests/scoping.tdy"); diff --git a/src/vm.rs b/src/vm.rs index 56b87f0..3a3e752 100644 --- a/src/vm.rs +++ b/src/vm.rs @@ -1,5 +1,6 @@ use owo_colors::OwoColorize; use std::collections::HashMap; +use std::collections::hash_map::Entry; use std::fmt::Debug; use std::path::{Path, PathBuf}; use std::rc::Rc; @@ -23,7 +24,7 @@ pub enum Value { Int(i64), Bool(bool), String(Rc), - Function(Vec>>, Rc), + Function(Vec>>, Rc>), Unkown, Nil, } @@ -77,7 +78,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.borrow().name, block.borrow().ty), Value::Unkown => write!(fmt, "(unkown)"), Value::Nil => write!(fmt, "(nil)"), } @@ -100,7 +101,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.borrow().ty.clone(), Value::Unkown => Type::UnknownType, Value::Nil => Type::Void, } @@ -265,7 +266,7 @@ impl Block { #[derive(Debug)] struct Frame { stack_offset: usize, - block: Rc, + block: Rc>, ip: usize, } @@ -305,6 +306,15 @@ impl VM { self } + fn drop_upvalue(&mut self, slot: usize, value: Value) { + if let Entry::Occupied(entry) = self.upvalues.entry(slot) { + entry.get().borrow_mut().close(value); + entry.remove(); + } else { + unreachable!(); + } + } + fn find_upvalue(&mut self, slot: usize) -> &mut Rc> { self.upvalues.entry(slot).or_insert( Rc::new(RefCell::new(UpValue::new(slot)))) @@ -335,17 +345,17 @@ impl VM { &mut self.frames[last] } - fn op(&self) -> &Op { + fn op(&self) -> Op { let ip = self.frame().ip; - &self.frame().block.ops[ip] + self.frame().block.borrow().ops[ip].clone() } fn error(&self, kind: ErrorKind, message: Option) -> Error { let frame = self.frames.last().unwrap(); Error { kind, - file: frame.block.file.clone(), - line: frame.block.line(frame.ip), + file: frame.block.borrow().file.clone(), + line: frame.block.borrow().line(frame.ip), message, } } @@ -365,7 +375,9 @@ impl VM { } Op::PopUpvalue => { - self.stack.pop().unwrap(); + let value = self.stack.pop().unwrap(); + let slot = self.stack.len(); + self.drop_upvalue(slot, value); } Op::Constant(value) => { @@ -373,7 +385,7 @@ impl VM { let value = match value { Value::Function(_, block) => { let mut ups = Vec::new(); - for (slot, is_up, _) in block.ups.iter() { + for (slot, is_up, _) in block.borrow().ups.iter() { let up = if *is_up { if let Value::Function(local_ups, _) = &self.stack[offset] { Rc::clone(&local_ups[*slot]) @@ -543,15 +555,17 @@ impl VM { let new_base = self.stack.len() - 1 - num_args; match &self.stack[new_base] { Value::Function(_, block) => { - let args = block.args(); + let inner = block.borrow(); + let args = inner.args(); if args.len() != num_args { error!(self, ErrorKind::InvalidProgram, format!("Invalid number of arguments, got {} expected {}.", num_args, args.len())); } + if self.print_blocks { - block.debug_print(); + inner.debug_print(); } self.frames.push(Frame { stack_offset: new_base, @@ -596,12 +610,12 @@ impl VM { println!("]"); println!("{:5} {:05} {:?}", - self.frame().block.line(self.frame().ip).red(), + self.frame().block.borrow().line(self.frame().ip).red(), self.frame().ip.blue(), - self.frame().block.ops[self.frame().ip]); + self.frame().block.borrow().ops[self.frame().ip]); } - pub fn run(&mut self, block: Rc) -> Result<(), Error>{ + pub fn run(&mut self, block: Rc>) -> Result<(), Error>{ self.stack.clear(); self.frames.clear(); @@ -615,7 +629,7 @@ impl VM { if self.print_blocks { println!("\n [[{}]]\n", "RUNNING".red()); - self.frame().block.debug_print(); + self.frame().block.borrow().debug_print(); } loop { @@ -623,7 +637,7 @@ impl VM { self.print_stack() } - if matches!(self.eval_op(self.op().clone())?, OpResult::Done) { + if matches!(self.eval_op(self.op())?, OpResult::Done) { return Ok(()); } } @@ -640,11 +654,12 @@ impl VM { } Op::ReadUpvalue(slot) => { - self.stack.push(self.frame().block.ups[slot].2.as_value()); + let value = self.frame().block.borrow().ups[slot].2.as_value(); + self.stack.push(value); } Op::AssignUpvalue(slot) => { - let var = self.frame().block.ups[slot].2.clone(); + let var = self.frame().block.borrow().ups[slot].2.clone(); let up = self.stack.pop().unwrap().as_type(); if var != up { error!(self, ErrorKind::TypeError(op, vec![var, up]), @@ -654,7 +669,8 @@ impl VM { Op::Return => { let a = self.stack.pop().unwrap(); - let ret = self.frame().block.ret(); + let inner = self.frame().block.borrow(); + let ret = inner.ret(); if a.as_type() != *ret { error!(self, ErrorKind::TypeError(op, vec![a.as_type(), ret.clone()]), @@ -685,9 +701,10 @@ impl VM { Op::Call(num_args) => { let new_base = self.stack.len() - 1 - num_args; - match &self.stack[new_base] { + match self.stack[new_base].clone() { Value::Function(_, block) => { - let args = block.args(); + let inner = block.borrow(); + let args = inner.args(); if args.len() != num_args { error!(self, ErrorKind::InvalidProgram, @@ -704,7 +721,7 @@ impl VM { args, stack_args)); } - self.stack[new_base] = block.ret().as_value(); + self.stack[new_base] = block.borrow().ret().as_value(); self.stack.truncate(new_base + 1); }, @@ -731,12 +748,12 @@ impl VM { Ok(()) } - fn typecheck_block(&mut self, block: Rc) -> Vec { + fn typecheck_block(&mut self, block: Rc>) -> Vec { self.stack.clear(); self.frames.clear(); self.stack.push(Value::Function(Vec::new(), Rc::clone(&block))); - for arg in block.args() { + for arg in block.borrow().args() { self.stack.push(arg.as_value()); } @@ -748,13 +765,13 @@ impl VM { if self.print_blocks { println!("\n [[{}]]\n", "TYPECHECK".purple()); - self.frame().block.debug_print(); + self.frame().block.borrow().debug_print(); } let mut errors = Vec::new(); loop { let ip = self.frame().ip; - if ip >= self.frame().block.ops.len() { + if ip >= self.frame().block.borrow().ops.len() { break; } @@ -762,7 +779,7 @@ impl VM { self.print_stack() } - if let Err(e) = self.check_op(self.op().clone()) { + if let Err(e) = self.check_op(self.op()) { errors.push(e); self.frame_mut().ip += 1; } @@ -775,11 +792,10 @@ impl VM { errors } - pub fn typecheck(&mut self, blocks: &Vec>) -> Result<(), Vec> { + pub fn typecheck(&mut self, blocks: &Vec>>) -> Result<(), Vec> { 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))); } -- cgit v1.2.1 From 18e7483580c000ee512f4a1f266b39c8f206ba65 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Thu, 21 Jan 2021 20:09:00 +0100 Subject: Pop upvalues --- src/lib.rs | 24 ++++++++++++++++++++++++ src/vm.rs | 10 ++++++++++ 2 files changed, 34 insertions(+) (limited to 'src') diff --git a/src/lib.rs b/src/lib.rs index 794bbea..e83d11f 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -232,6 +232,30 @@ mod tests { factorial(5) <=> 120 factorial(6) <=> 720 factorial(12) <=> 479001600", + + returning_closures: " +f : fn -> fn -> int = fn -> fn -> int { + x : int = 0 + f := fn -> int { + x = x + 1 + ret x + } + f() <=> 1 + ret f +} + +a := f() +b := f() + +a() <=> 2 +a() <=> 3 + +b() <=> 2 +b() <=> 3 + +a() <=> 4 +" + //TODO this tests doesn't terminate in proper time if we print blocks and ops /* fibonacci: "fibonacci : fn int -> int = fn n: int -> int { diff --git a/src/vm.rs b/src/vm.rs index 3a3e752..177c547 100644 --- a/src/vm.rs +++ b/src/vm.rs @@ -590,6 +590,12 @@ impl VM { return Ok(OpResult::Done); } else { self.stack[last.stack_offset] = self.stack.pop().unwrap(); + for slot in last.stack_offset+1..self.stack.len() { + if self.upvalues.contains_key(&slot) { + let value = self.stack[slot].clone(); + self.drop_upvalue(slot, value); + } + } self.stack.truncate(last.stack_offset + 1); } } @@ -653,6 +659,10 @@ impl VM { self.stack.push(value.clone()); } + Op::PopUpvalue => { + self.stack.pop().unwrap(); + } + Op::ReadUpvalue(slot) => { let value = self.frame().block.borrow().ups[slot].2.as_value(); self.stack.push(value); -- cgit v1.2.1 From 4448657f8443842e3ef75353c5fa87dfebb3cffd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Thu, 21 Jan 2021 20:56:38 +0100 Subject: Add type inference for upvalues --- src/compiler.rs | 7 +++++++ src/vm.rs | 37 +++++++++++++++++++++++++++++++++++-- 2 files changed, 42 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index 409d6a6..70c9a51 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -87,6 +87,13 @@ impl From<&Value> for Type { } impl Type { + pub fn is_unkown(&self) -> bool { + match self { + Type::UnknownType => true, + _ => false, + } + } + pub fn as_value(&self) -> Value { match self { Type::Void => Value::Nil, diff --git a/src/vm.rs b/src/vm.rs index 177c547..c7b6c0f 100644 --- a/src/vm.rs +++ b/src/vm.rs @@ -655,8 +655,41 @@ impl VM { Op::Jmp(_line) => {} - Op::Constant(value) => { - self.stack.push(value.clone()); + Op::Constant(ref value) => { + match value.clone() { + Value::Function(_, block) => { + self.stack.push(Value::Function(Vec::new(), block.clone())); + + let mut types = Vec::new(); + for (slot, is_up, _) in block.borrow().ups.iter() { + if *is_up { + types.push(Type::Void); + } else { + types.push(self.stack[*slot].as_type()); + } + } + + let mut block_mut = block.borrow_mut(); + for (i, (_, is_up, ty)) in block_mut.ups.iter_mut().enumerate() { + if *is_up { continue; } + + let suggestion = &types[i]; + if ty.is_unkown() { + *ty = suggestion.clone(); + } else { + if ty != suggestion { + error!(self, + ErrorKind::TypeError(op.clone(), + vec![ty.clone(), suggestion.clone()]), + "Failed to infer type.".to_string()); + } + } + }; + }, + _ => { + self.stack.push(value.clone()); + } + } } Op::PopUpvalue => { -- cgit v1.2.1