diff options
| -rw-r--r-- | src/compiler.rs | 153 | ||||
| -rw-r--r-- | src/lib.rs | 184 | ||||
| -rw-r--r-- | src/vm.rs | 77 |
3 files changed, 311 insertions, 103 deletions
diff --git a/src/compiler.rs b/src/compiler.rs index f2daa6e..94ae2aa 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -1,6 +1,6 @@ use std::{borrow::Cow, path::{Path, PathBuf}}; use std::cell::RefCell; -use std::collections::HashMap; +use std::collections::{HashMap, hash_map::Entry}; use std::rc::Rc; use crate::{Blob, Block, Op, Prog, RustFunction, Type, Value}; @@ -151,16 +151,6 @@ impl Frame { } } - fn count_this_scope(&self) -> usize { - for (i, var) in self.stack.iter().rev().enumerate() { - println!("i:{} - {} == {}", i, var.scope, self.scope); - if var.scope != self.scope { - // return i; - } - } - return self.stack.len(); - } - fn push_loop(&mut self) { self.loops.push(Vec::new()); } @@ -177,7 +167,7 @@ impl Frame { } } - fn add_continue(&mut self, addr: usize, stacksize: usize, block: &mut Block) -> Result<(), ()> { + fn add_continue(&mut self, addr: usize, stacksize: usize) -> Result<(), ()> { if let Some(top) = self.loops.last_mut() { top.push((addr, stacksize, LoopOp::Continue)); Ok(()) @@ -186,7 +176,7 @@ impl Frame { } } - fn add_break(&mut self, addr: usize, stacksize: usize, block: &mut Block) -> Result<(), ()> { + fn add_break(&mut self, addr: usize, stacksize: usize) -> Result<(), ()> { if let Some(top) = self.loops.last_mut() { top.push((addr, stacksize, LoopOp::Break)); Ok(()) @@ -238,7 +228,8 @@ pub(crate) struct Compiler { errors: Vec<Error>, blocks: Vec<Rc<RefCell<Block>>>, - blobs: Vec<Blob>, + blob_id: usize, + unknown: HashMap<String, (usize, usize)>, functions: HashMap<String, (usize, RustFunction)>, constants: Vec<Value>, @@ -300,7 +291,8 @@ impl Compiler { errors: vec![], blocks: Vec::new(), - blobs: Vec::new(), + blob_id: 0, + unknown: HashMap::new(), functions: HashMap::new(), @@ -319,6 +311,12 @@ impl Compiler { }).unwrap() } + fn new_blob_id(&mut self) -> usize { + let id = self.blob_id; + self.blob_id += 1; + id + } + fn add_constant(&mut self, value: Value) -> usize { self.constants.push(value); self.constants.len() - 1 @@ -363,16 +361,21 @@ impl Compiler { } fn error(&mut self, kind: ErrorKind, message: Option<String>) { + self.error_on_line(kind, self.line(), message); + } + + fn error_on_line(&mut self, kind: ErrorKind, line: usize, message: Option<String>) { if self.panic { return } self.panic = true; self.errors.push(Error { kind, file: self.current_file.clone(), - line: self.line(), + line, message, }); } + fn peek(&self) -> Token { self.peek_at(0) } @@ -570,7 +573,7 @@ impl Compiler { /// Entry point for all expression parsing. fn expression(&mut self, block: &mut Block) { match self.peek_four() { - (Token::Fn, ..) => self.function(block), + (Token::Fn, ..) => { self.function(block, None); }, _ => self.parse_precedence(block, Prec::No), } } @@ -621,10 +624,19 @@ impl Compiler { Self::find_and_capture_variable(name, self.frames.iter_mut().rev()) } - fn find_blob(&self, name: &str) -> Option<usize> { - self.blobs.iter().enumerate() - .find(|(_, x)| x.name == name) - .map(|(i, _)| i) + fn find_constant(&mut self, name: &str) -> usize { + let res = self.constants.iter().enumerate().find_map(|(i, x)| match x { + Value::Blob(b) if b.name == name => Some(i), + Value::Function(_, b) if b.borrow().name == name => Some(i), + _ => None, + }); + if let Some(res) = res { + return res; + } + let constant = self.add_constant(Value::Nil); + let line = self.line(); + let entry = self.unknown.entry(name.to_string()); + entry.or_insert((constant, line)).0 } fn call(&mut self, block: &mut Block) { @@ -681,9 +693,6 @@ impl Compiler { break; } } - if !self.panic { - println!("LINE {} -- ", self.line()); - } } _ => { @@ -695,11 +704,13 @@ impl Compiler { } // TODO(ed): de-complexify - fn function(&mut self, block: &mut Block) { + fn function(&mut self, block: &mut Block, name: Option<&str>) { expect!(self, Token::Fn, "Expected 'fn' at start of function."); let top = self.stack().len() - 1; - let name = if !self.stack()[top].active { + let name = if let Some(name) = name { + Cow::Owned(String::from(name)) + } else if !self.stack()[top].active { self.stack_mut()[top].active = true; Cow::Borrowed(&self.stack()[top].name) } else { @@ -779,8 +790,11 @@ impl Compiler { let function_block = Rc::new(RefCell::new(function_block)); - let constant = self.add_constant(Value::Function(Vec::new(), Rc::clone(&function_block))); + // Note(ed): We deliberately add the constant as late as possible. + // This behaviour is used in `constant_statement`. + let function = Value::Function(Vec::new(), Rc::clone(&function_block)); self.blocks[block_id] = function_block; + let constant = self.add_constant(function); add_op(self, block, Op::Constant(constant)); } @@ -789,6 +803,16 @@ impl Compiler { Token::Identifier(name) => name, _ => unreachable!(), }; + + // Global functions take precedence + if let Some(slot) = self.find_extern_function(&name) { + let string = self.add_constant(Value::ExternFunction(slot)); + add_op(self, block, Op::Constant(string)); + self.call(block); + return; + } + + // Variables if let Some(var) = self.find_variable(&name) { if var.upvalue { add_op(self, block, Op::ReadUpvalue(var.slot)); @@ -804,27 +828,22 @@ impl Compiler { add_op(self, block, Op::Get(string)); } else { error!(self, "Expected fieldname after '.'."); - break; + return; } } _ => { if !parse_branch!(self, block, self.call(block)) { - break + return; } } } } - } else if let Some(blob) = self.find_blob(&name) { - let string = self.add_constant(Value::Blob(blob)); - add_op(self, block, Op::Constant(string)); - parse_branch!(self, block, self.call(block)); - } else if let Some(slot) = self.find_extern_function(&name) { - let string = self.add_constant(Value::ExternFunction(slot)); - add_op(self, block, Op::Constant(string)); - self.call(block); - } else { - error!(self, format!("Using undefined variable {}.", name)); } + + // Blobs - Always returns a blob since it's filled in if it isn't used. + let con = self.find_constant(&name); + add_op(self, block, Op::Constant(con)); + parse_branch!(self, block, self.call(block)); } fn define_variable(&mut self, name: &str, typ: Type, _block: &mut Block) -> Result<usize, ()> { @@ -889,6 +908,23 @@ impl Compiler { } fn constant_statement(&mut self, name: &str, typ: Type, block: &mut Block) { + // Magical global constants + if self.frames.len() <= 1 { + if parse_branch!(self, block, self.function(block, Some(name))) { + // Remove the function, since it's a constant and we already + // added it. + block.ops.pop().unwrap(); + if let Entry::Occupied(entry) = self.unknown.entry(String::from(name)) { + let (_, (slot, _)) = entry.remove_entry(); + self.constants[slot] = self.constants.pop().unwrap(); + add_op(self, block, Op::Link(slot)); + } else { + add_op(self, block, Op::Link(self.constants.len() - 1)); + } + return; + } + } + let slot = self.define_constant(name, typ.clone(), block); self.expression(block); @@ -1095,7 +1131,17 @@ impl Compiler { "float" => Ok(Type::Float), "bool" => Ok(Type::Bool), "str" => Ok(Type::String), - x => self.find_blob(x).map(|blob| Type::BlobInstance(blob)).ok_or(()), + x => { + let blob = self.find_constant(x); + if let Value::Blob(blob) = &self.constants[blob] { + Ok(Type::Instance(Rc::clone(blob))) + } else { + // TODO(ed): This is kinda bad. If the type cannot + // be found it tries to infer it during runtime + // and doesn't verify it. + Ok(Type::Unknown) + } + } } } _ => Err(()), @@ -1113,7 +1159,7 @@ impl Compiler { expect!(self, Token::LeftBrace, "Expected 'blob' body. AKA '{'."); - let mut blob = Blob::new(&name); + let mut blob = Blob::new(self.new_blob_id(), &name); loop { if matches!(self.peek(), Token::EOF | Token::RightBrace) { break; } if matches!(self.peek(), Token::Newline) { self.eat(); continue; } @@ -1141,7 +1187,13 @@ impl Compiler { expect!(self, Token::RightBrace, "Expected '}' after 'blob' body. AKA '}'."); - self.blobs.push(blob); + let blob = Value::Blob(Rc::new(blob)); + if let Entry::Occupied(entry) = self.unknown.entry(name) { + let (_, (slot, _)) = entry.remove_entry(); + self.constants[slot] = blob; + } else { + self.constants.push(blob); + } } fn blob_field(&mut self, block: &mut Block) { @@ -1278,7 +1330,7 @@ impl Compiler { self.eat(); let addr = add_op(self, block, Op::Illegal); let stack_size = self.frame().stack.len(); - if self.frame_mut().add_break(addr, stack_size, block).is_err() {; + if self.frame_mut().add_break(addr, stack_size).is_err() { error!(self, "Cannot place 'break' outside of loop."); } } @@ -1287,7 +1339,7 @@ impl Compiler { self.eat(); let addr = add_op(self, block, Op::Illegal); let stack_size = self.frame().stack.len(); - if self.frame_mut().add_continue(addr, stack_size, block).is_err() { + if self.frame_mut().add_continue(addr, stack_size).is_err() { error!(self, "Cannot place 'continue' outside of loop."); } } @@ -1346,12 +1398,23 @@ impl Compiler { add_op(self, &mut block, Op::Return); block.ty = Type::Function(Vec::new(), Box::new(Type::Void)); + if self.unknown.len() != 0 { + let errors: Vec<_> = self.unknown.iter().map(|(name, (_, line))| + (ErrorKind::SyntaxError(*line, Token::Identifier(name.clone())), + *line, + format!("Usage of undefined value: '{}'.", name,) + )) + .collect(); + for (e, l, m) in errors.iter() { + self.error_on_line(e.clone(), *l, Some(m.clone())); + } + } + self.blocks.insert(0, Rc::new(RefCell::new(block))); if self.errors.is_empty() { Ok(Prog { blocks: self.blocks.clone(), - blobs: self.blobs.iter().map(|x| Rc::new(x.clone())).collect(), functions: functions.iter().map(|(_, f)| *f).collect(), constants: self.constants.clone(), strings: self.strings.clone(), @@ -84,16 +84,16 @@ pub enum Type { String, Tuple(Vec<Type>), Function(Vec<Type>, Box<Type>), - Blob(usize), - BlobInstance(usize), + Blob(Rc<Blob>), + Instance(Rc<Blob>), } impl PartialEq for Type { fn eq(&self, other: &Self) -> bool { match (self, other) { (Type::Void, Type::Void) => true, - (Type::BlobInstance(a), Type::BlobInstance(b)) => a == b, - (Type::Blob(a), Type::Blob(b)) => a == b, + (Type::Instance(a), Type::Instance(b)) => *a == *b, + (Type::Blob(a), Type::Blob(b)) => *a == *b, (Type::Int, Type::Int) => true, (Type::Float, Type::Float) => true, (Type::Bool, Type::Bool) => true, @@ -111,8 +111,8 @@ impl PartialEq for Type { impl From<&Value> for Type { fn from(value: &Value) -> Type { match value { - Value::BlobInstance(i, _) => Type::BlobInstance(*i), - Value::Blob(i) => Type::Blob(*i), + Value::Instance(b, _) => Type::Instance(Rc::clone(b)), + Value::Blob(b) => Type::Blob(Rc::clone(b)), Value::Tuple(v) => { Type::Tuple(v.iter().map(|x| Type::from(x)).collect()) } @@ -136,8 +136,11 @@ impl From<&Type> for Value { fn from(ty: &Type) -> Self { match ty { Type::Void => Value::Nil, - Type::Blob(i) => Value::Blob(*i), - Type::BlobInstance(i) => Value::BlobInstance(*i, Rc::new(RefCell::new(Vec::new()))), + Type::Blob(b) => Value::Blob(Rc::clone(b)), + Type::Instance(b) => { + Value::Instance(Rc::clone(b), + Rc::new(RefCell::new(Vec::new()))) + } Type::Tuple(fields) => { Value::Tuple(Rc::new(fields.iter().map(Value::from).collect())) } @@ -163,8 +166,8 @@ impl From<Type> for Value { #[derive(Clone)] pub enum Value { Ty(Type), - Blob(usize), - BlobInstance(usize, Rc<RefCell<Vec<Value>>>), + Blob(Rc<Blob>), + Instance(Rc<Blob>, Rc<RefCell<Vec<Value>>>), Tuple(Rc<Vec<Value>>), Float(f64), Int(i64), @@ -180,8 +183,8 @@ impl Debug for Value { fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { match self { Value::Ty(ty) => write!(fmt, "(type {:?})", ty), - Value::Blob(i) => write!(fmt, "(blob {})", i), - Value::BlobInstance(i, v) => write!(fmt, "(inst {} {:?})", i, v), + Value::Blob(b) => write!(fmt, "(blob {})", b.name), + Value::Instance(b, v) => write!(fmt, "(inst {} {:?})", b.name, v), Value::Float(f) => write!(fmt, "(float {})", f), Value::Int(i) => write!(fmt, "(int {})", i), Value::Bool(b) => write!(fmt, "(bool {})", b), @@ -257,14 +260,22 @@ impl UpValue { #[derive(Debug, Clone)] pub struct Blob { + pub id: usize, pub name: String, /// Maps field names to their slot and type. pub fields: HashMap<String, (usize, Type)>, } +impl PartialEq for Blob { + fn eq(&self, other: &Self) -> bool { + self.id == other.id + } +} + impl Blob { - fn new(name: &str) -> Self { + fn new(id: usize, name: &str) -> Self { Self { + id: id, name: String::from(name), fields: HashMap::new(), } @@ -469,6 +480,12 @@ pub enum Op { /// Does not affect the stack. Define(usize), + /// Links the upvalues for the given constant + /// function. This updates the constant stack. + /// + /// Does not affect the stack. + Link(usize), + /// Calls "something" with the given number /// of arguments. The callable value is /// then replaced with the result. @@ -677,6 +694,8 @@ impl Block { pub fn debug_print(&self) { println!(" === {} ===", self.name.blue()); for (i, s) in self.ops.iter().enumerate() { + // TODO(ed): This print should only do one call to print. + // Otherwise we can get race conditions in a single line. if self.line_offsets.contains_key(&i) { print!("{:5} ", self.line_offsets[&i].red()); } else { @@ -713,7 +732,6 @@ impl Block { #[derive(Clone)] pub struct Prog { pub blocks: Vec<Rc<RefCell<Block>>>, - pub blobs: Vec<Rc<Blob>>, pub functions: Vec<RustFunction>, pub constants: Vec<Value>, pub strings: Vec<String>, @@ -747,6 +765,7 @@ mod tests { use std::time::Duration; use std::sync::mpsc; use std::thread; + use owo_colors::OwoColorize; // Shamelessly stolen from https://github.com/rust-lang/rfcs/issues/2798 pub fn panic_after<T, F>(d: Duration, f: F) -> T @@ -762,10 +781,19 @@ mod tests { val }); - match done_rx.recv_timeout(d) { - Ok(_) => handle.join().expect("Thread panicked"), - Err(_) => panic!("Thread took too long"), - } + let msg = match done_rx.recv_timeout(d) { + Ok(_) => { + return handle.join().expect("Thread panicked"); + } + Err(mpsc::RecvTimeoutError::Timeout) => { + "Test took too long to complete" + }, + Err(mpsc::RecvTimeoutError::Disconnected) => { + "Test produced incorrect result" + }, + }; + println!(" #### {} ####", msg.red()); + panic!(msg); } #[macro_export] @@ -823,6 +851,12 @@ mod tests { assert_errs!(run_string("a :: 2\nq :: fn { a = 2 }\n", true, Vec::new()), [ErrorKind::SyntaxError(_, _)]); } + #[test] + fn undefined_blob() { + assert_errs!(run_string("a :: B()\n", true, Vec::new()), [ErrorKind::SyntaxError(_, _)]); + } + + macro_rules! test_multiple { ($mod:ident, $( $fn:ident : $prog:literal ),+ $( , )? ) => { mod $mod { @@ -988,23 +1022,7 @@ 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 { - 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_multiple!( @@ -1029,7 +1047,11 @@ a() <=> 4 a.a = 2 a.b = 3 a.a + a.b <=> 5 - 5 <=> a.a + a.b" + 5 <=> a.a + a.b", + blob_infer: " +blob A { } +a : A = A() +", ); test_multiple!(tuples, @@ -1173,4 +1195,94 @@ a := 0 a <=> -1 ", ); + + test_multiple!( + declaration_order, + blob_simple: " +a := A() + +blob A { + a: int +} +", + + blob_complex: " +a := A() +b := B() +c := C() +b2 := B() + +blob A { + c: C +} +blob C { } +blob B { } +", + + blob_infer: " +blob A { } + +a : A = A() +", + + + constant_function: " +a() +a :: fn {} +", + + constant_function_complex: " +h :: fn -> int { + ret 3 +} + +a() <=> 3 + +k :: fn -> int { + ret h() +} + +a :: fn -> int { + ret q() +} + +q :: fn -> int { + ret k() +} +", + + constant_function_closure: " +q := 1 + +f :: fn -> int { + q += 1 + ret q +} + +f() <=> 2 +f() <=> 3 +f() <=> 4 +f() <=> 5 +", + + constants_in_inner_functions: " +q : int = 0 + +f :: fn -> fn -> { + g :: fn { + q += 1 + } + ret g +} + +g := f() +g() +q <=> 1 +g() +q <=> 2 +g() +q <=> 3 +", + + ); } @@ -6,7 +6,7 @@ use std::rc::Rc; use owo_colors::OwoColorize; -use crate::{Blob, Block, Op, Prog, UpValue, Value, op}; +use crate::{Block, Op, Prog, UpValue, Value, op}; use crate::error::{Error, ErrorKind}; use crate::RustFunction; use crate::Type; @@ -57,7 +57,6 @@ pub struct VM { stack: Vec<Value>, frames: Vec<Frame>, - blobs: Vec<Rc<Blob>>, constants: Vec<Value>, strings: Vec<String>, @@ -87,7 +86,6 @@ impl VM { stack: Vec::new(), frames: Vec::new(), - blobs: Vec::new(), constants: Vec::new(), strings: Vec::new(), @@ -260,6 +258,34 @@ impl VM { self.push(value); } + Op::Link(slot) => { + let offset = self.frame().stack_offset; + let constant = self.constant(slot).clone(); + let constant = match constant { + Value::Function(_, block) => { + let mut ups = Vec::new(); + for (slot, is_up, _) in block.borrow().upvalues.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 => error!(self, + ErrorKind::RuntimeTypeError(op, vec![value.clone()]), + format!("Not a function {:?}.", value)), + }; + self.constants[slot] = constant; + } + Op::Index => { let slot = self.stack.pop().unwrap(); let val = self.stack.pop().unwrap(); @@ -283,8 +309,8 @@ impl VM { Op::Get(field) => { let inst = self.pop(); let field = self.string(field); - if let Value::BlobInstance(ty, values) = inst { - let slot = self.blobs[ty].fields.get(field).unwrap().0; + if let Value::Instance(ty, values) = inst { + let slot = ty.fields.get(field).unwrap().0; self.push(values.borrow()[slot].clone()); } else { error!(self, ErrorKind::RuntimeTypeError(op, vec![inst])); @@ -294,8 +320,8 @@ impl VM { Op::Set(field) => { let (inst, value) = self.poppop(); let field = self.string(field); - if let Value::BlobInstance(ty, values) = inst { - let slot = self.blobs[ty].fields.get(field).unwrap().0; + if let Value::Instance(ty, values) = inst { + let slot = ty.fields.get(field).unwrap().0; values.borrow_mut()[slot] = value; } else { error!(self, ErrorKind::RuntimeTypeError(op, vec![inst])); @@ -393,16 +419,14 @@ impl VM { Op::Call(num_args) => { let new_base = self.stack.len() - 1 - num_args; match self.stack[new_base].clone() { - Value::Blob(blob_id) => { - let blob = &self.blobs[blob_id]; - + Value::Blob(blob) => { let mut values = Vec::with_capacity(blob.fields.len()); for _ in 0..values.capacity() { values.push(Value::Nil); } self.pop(); - self.push(Value::BlobInstance(blob_id, Rc::new(RefCell::new(values)))); + self.push(Value::Instance(blob, Rc::new(RefCell::new(values)))); } Value::Function(_, block) => { let inner = block.borrow(); @@ -483,7 +507,6 @@ impl VM { #[doc(hidden)] pub fn init(&mut self, prog: &Prog) { let block = Rc::clone(&prog.blocks[0]); - self.blobs = prog.blobs.clone(); self.constants = prog.constants.clone(); self.strings = prog.strings.clone(); @@ -569,8 +592,8 @@ impl VM { Op::Get(field) => { let inst = self.pop(); let field = self.string(field); - if let Value::BlobInstance(ty, _) = inst { - let value = Value::from(&self.blobs[ty].fields.get(field).unwrap().1); + if let Value::Instance(ty, _) = inst { + let value = Value::from(ty.fields.get(field).unwrap().1.clone()); self.push(value); } else { self.push(Value::Nil); @@ -582,10 +605,10 @@ impl VM { let (inst, value) = self.poppop(); let field = self.string(field); - if let Value::BlobInstance(ty, _) = inst { - let ty = &self.blobs[ty].fields.get(field).unwrap().1; + if let Value::Instance(ty, _) = inst { + let ty = &ty.fields.get(field).unwrap().1; if ty != &Type::from(&value) { - error!(self, ErrorKind::RuntimeTypeError(op, vec![inst])); + error!(self, ErrorKind::RuntimeTypeError(op, vec![Value::from(ty)])); } } else { error!(self, ErrorKind::RuntimeTypeError(op, vec![inst])); @@ -643,12 +666,23 @@ impl VM { } } + Op::Link(slot) => { + println!("{:?}", self.constants); + println!("{:?} - {}", self.constant(slot), slot); + match self.constant(slot).clone() { + Value::Function(_, _) => {} + value => { + error!(self, + ErrorKind::TypeError(op, vec![Type::from(&value)]), + format!("Cannot link non-function {:?}.", value)); + } + }; + } + Op::Call(num_args) => { let new_base = self.stack.len() - 1 - num_args; match self.stack[new_base].clone() { - Value::Blob(blob_id) => { - let blob = &self.blobs[blob_id]; - + Value::Blob(blob) => { let mut values = Vec::with_capacity(blob.fields.len()); for _ in 0..values.capacity() { values.push(Value::Nil); @@ -659,7 +693,7 @@ impl VM { } self.pop(); - self.push(Value::BlobInstance(blob_id, Rc::new(RefCell::new(values)))); + self.push(Value::Instance(blob, Rc::new(RefCell::new(values)))); } Value::Function(_, block) => { let inner = block.borrow(); @@ -771,7 +805,6 @@ impl VM { pub(crate) fn typecheck(&mut self, prog: &Prog) -> Result<(), Vec<Error>> { let mut errors = Vec::new(); - self.blobs = prog.blobs.clone(); self.constants = prog.constants.clone(); self.strings = prog.strings.clone(); self.runtime = false; |