diff options
| author | Edvard Thörnros <edvard.thornros@gmail.com> | 2021-01-14 21:10:07 +0100 |
|---|---|---|
| committer | Gustav Sörnäs <gustav@sornas.net> | 2021-01-15 16:57:56 +0100 |
| commit | 7ec991b8d6654aaf27a005804347346e16500a47 (patch) | |
| tree | bf36be24f2a8dffa4589aecfce75d0f0bf55f440 | |
| parent | 4e6071aee97a26610aeee423d830a695b8c4d563 (diff) | |
| download | sylt-7ec991b8d6654aaf27a005804347346e16500a47.tar.gz | |
Start of typesystem
There's a type system, that kinda works
There needs to be better parsing of types, since not all types are
currently parsable. Some of them are, and the simple stuff works!
:D
| -rw-r--r-- | src/compiler.rs | 87 | ||||
| -rw-r--r-- | src/error.rs | 14 | ||||
| -rw-r--r-- | src/lib.rs | 1 | ||||
| -rw-r--r-- | src/typer.rs | 323 | ||||
| -rw-r--r-- | src/vm.rs | 57 | ||||
| -rw-r--r-- | tests/fun.tdy | 16 | ||||
| -rw-r--r-- | tests/simple.tdy | 44 |
7 files changed, 452 insertions, 90 deletions
diff --git a/src/compiler.rs b/src/compiler.rs index 18599ae..3c5e8a4 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -47,26 +47,45 @@ nextable_enum!(Prec { Factor }); -#[derive(Debug, Copy, Clone)] -enum Type { +#[derive(Debug, Clone)] +pub enum Type { NoType, UnkownType, Int, Float, Bool, String, + Function(Rc<Block>), } -impl TryFrom<&str> for Type { - type Error = (); +impl PartialEq for Type { + fn eq(&self, other: &Self) -> bool { + match (self, other) { + (Type::NoType, Type::NoType) => true, + (Type::Int, Type::Int) => true, + (Type::Float, Type::Float) => true, + (Type::Bool, Type::Bool) => true, + (Type::String, Type::String) => true, + (Type::Function(a), Type::Function(b)) => { + a.args == b.args && a.ret == b.ret + }, + _ => false, + } + } +} + +impl From<&Value> for Type { - fn try_from(value: &str) -> Result<Self, Self::Error> { + fn from(value: &Value) -> Type { match value { - "int" => Ok(Type::Int), - "float" => Ok(Type::Float), - "bool" => Ok(Type::Bool), - "str" => Ok(Type::String), - _ => Err(()), + Value::Int(_) => Type::Int, + Value::Float(_) => Type::Float, + Value::Bool(_) => Type::Bool, + Value::String(_) => Type::String, + Value::Function(_, block) => { + Type::Function(Rc::clone(block)) + }, + _ => Type::NoType, } } } @@ -360,7 +379,7 @@ impl Compiler { let frame = self.frame(); for (slot, var) in frame.stack.iter().enumerate().rev() { if var.name == name && var.active { - return Some((slot, var.typ, var.scope)); + return Some((slot, var.typ.clone(), var.scope)); } } None @@ -406,8 +425,8 @@ impl Compiler { "anonumus function" }; - let mut _return_type = None; - let mut function_block = Block::new(name, &self.current_file); + let mut return_type = None; + let mut function_block = Block::new(name, &self.current_file, self.line()); let arity; let _ret = push_frame!(self, function_block, { loop { @@ -416,6 +435,7 @@ impl Compiler { self.eat(); expect!(self, Token::Colon, "Expected ':' after parameter name."); if let Ok(typ) = self.type_ident() { + function_block.args.push(typ.clone()); if let Ok(slot) = self.define_variable(&name, typ, &mut function_block) { self.stack_mut()[slot].active = true; } @@ -427,13 +447,13 @@ impl Compiler { } } Token::LeftBrace => { - _return_type = Some(Type::NoType); + return_type = Some(Type::NoType); break; } Token::Arrow => { self.eat(); if let Ok(typ) = self.type_ident() { - _return_type = Some(typ); + return_type = Some(typ); } else { error!(self, "Failed to parse return type."); } @@ -450,8 +470,11 @@ impl Compiler { self.scope(&mut function_block); }); + match return_type { + Some(typ) => function_block.ret = typ, + None => error!(self, "No returntype secified!"), + } - function_block.add(Op::Constant(Value::Bool(true)), self.line()); function_block.add(Op::Return, self.line()); block.add(Op::Constant(Value::Function(arity, Rc::new(function_block))), self.line()); @@ -555,17 +578,7 @@ impl Compiler { push_scope!(self, block, { // Definition match self.peek_four() { - (Token::Identifier(name), Token::Identifier(typ), Token::ColonEqual, ..) => { - self.eat(); - self.eat(); - self.eat(); - if let Ok(typ) = Type::try_from(typ.as_ref()) { - self.definition_statement(&name, typ, block); - } else { - error!(self, format!("Failed to parse type '{}'.", typ)); - } - } - + // TODO(ed): Typed definitions aswell! (Token::Identifier(name), Token::ColonEqual, ..) => { self.eat(); self.eat(); @@ -602,11 +615,18 @@ impl Compiler { } fn type_ident(&mut self) -> Result<Type, ()> { - if let Token::Identifier(typ) = self.peek() { - self.eat(); - Type::try_from(typ.as_ref()) - } else { - Err(()) + match self.eat() { + Token::Identifier(x) => { + match x.as_str() { + "int" => Ok(Type::Int), + "float" => Ok(Type::Float), + "bool" => Ok(Type::Bool), + "str" => Ok(Type::String), + _ => Err(()), + } + }, + _ => Err(()), + } } @@ -683,13 +703,14 @@ impl Compiler { } pub fn compile(&mut self, name: &str, file: &Path) -> Result<Block, Vec<Error>> { - let mut block = Block::new(name, file); + let mut block = Block::new(name, file, 0); while self.peek() != Token::EOF { self.statement(&mut block); expect!(self, Token::Newline, "Expect newline after expression."); } block.add(Op::Return, self.line()); + block.ret = Type::NoType; if self.errors.is_empty() { Ok(block) diff --git a/src/error.rs b/src/error.rs index 979ca07..6d8a14c 100644 --- a/src/error.rs +++ b/src/error.rs @@ -1,11 +1,13 @@ use std::fmt; use std::path::PathBuf; use crate::vm::{Op, Value}; +use crate::compiler::Type; use crate::tokenizer::Token; #[derive(Debug, Clone)] pub enum ErrorKind { - TypeError(Op, Vec<Value>), + TypeError(Op, Vec<Type>), + RuntimeTypeError(Op, Vec<Value>), Assert, InvalidProgram, Unreachable, @@ -24,7 +26,13 @@ pub struct Error { impl fmt::Display for ErrorKind { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { - ErrorKind::TypeError(op, values) => { + ErrorKind::TypeError(op, types) => { + let types = types + .iter() + .fold(String::new(), |a, v| { format!("{}, {:?}", a, v) }); + write!(f, "Cannot apply {:?} to types {}", op, types) + } + ErrorKind::RuntimeTypeError(op, values) => { let values = values .iter() .fold(String::new(), |a, v| { format!("{}, {:?}", a, v) }); @@ -52,7 +60,7 @@ impl fmt::Display for Error { Some(s) => format!("\n{}", s), None => String::from(""), }; - write!(f, "{:?}:{} [Runtime Error] {}{}", self.file, self.line, self.kind, message) + write!(f, "{:?}:{} {}{}", self.file, self.line, self.kind, message) } } @@ -4,6 +4,7 @@ use std::rc::Rc; pub mod compiler; pub mod tokenizer; pub mod vm; +pub mod typer; mod error; diff --git a/src/typer.rs b/src/typer.rs new file mode 100644 index 0000000..99f5487 --- /dev/null +++ b/src/typer.rs @@ -0,0 +1,323 @@ +use std::fmt::Debug; +use std::rc::Rc; +use owo_colors::OwoColorize; +use std::path::PathBuf; +use std::collections::HashSet; + +use crate::compiler::Type; +use crate::vm::{Op, Block}; +use crate::error::{Error, ErrorKind}; + +macro_rules! error { + ( $thing:expr, $kind:expr) => { + return Err($thing.error($kind, None)); + }; + ( $thing:expr, $kind:expr, $msg:expr) => { + return Err($thing.error($kind, Some(String::from($msg)))); + }; +} + +#[derive(Debug)] +struct Frame { + stack_offset: usize, + block: Rc<Block>, + ip: usize, +} + +#[derive(Debug)] +pub struct VM { + checked: HashSet<(PathBuf, usize)>, + + stack: Vec<Type>, + frames: Vec<Frame>, + + print_blocks: bool, + print_ops: bool, +} + +impl VM { + pub fn new() -> Self { + Self { + checked: HashSet::new(), + + stack: Vec::new(), + frames: Vec::new(), + print_blocks: false, + print_ops: false, + } + } + + pub fn print_blocks(mut self, b: bool) -> Self { + self.print_blocks = b; + self + } + + pub fn print_ops(mut self, b: bool) -> Self { + self.print_ops = b; + self + } + + fn pop(&mut self) -> Type { + let len = self.stack.len(); + let res = self.stack[len-1].clone(); + self.stack.truncate(len - 1); + res + } + + + fn pop_twice(&mut self) -> (Type, Type) { + let len = self.stack.len(); + let res = (self.stack[len-2].clone(), self.stack[len-1].clone()); + self.stack.truncate(len - 2); + res + } + + fn peek_up(&self, amount: usize) -> Type { + self.stack[self.stack.len() - amount].clone() + } + + fn frame(&self) -> &Frame { + let last = self.frames.len() - 1; + &self.frames[last] + } + + fn frame_mut(&mut self) -> &mut Frame { + let last = self.frames.len() - 1; + &mut self.frames[last] + } + + fn error(&self, kind: ErrorKind, message: Option<String>) -> Error { + let frame = self.frames.last().unwrap(); + Error { + kind, + file: frame.block.file.clone(), + line: frame.block.line(frame.ip), + message, + } + } + + pub fn typecheck(&mut self, block: Rc<Block>) -> Result<(), Error>{ + let id = block.id(); + if self.checked.contains(&id) { + return Ok(()); + } + self.checked.insert(id); + + self.frames.push(Frame { + stack_offset: 0, + block, + ip: 0 + }); + + let outer = self.stack.is_empty(); + + if self.print_blocks { + self.frame().block.debug_print(); + } + + loop { + let ip = self.frame().ip; + let op = self.frame().block.ops.get(ip); + if op.is_none() { + return Ok(()); + } + let op = op.unwrap().clone(); + + if self.print_ops { + let start = self.frame().stack_offset; + print!(" {:3} [", start); + for (i, s) in self.stack.iter().skip(start).enumerate() { + if i != 0 { + print!(" "); + } + match s { + s => print!("{:?}", s.green()), + Type::Function(block) => print!("Function({:?} -> {:?})", block.args, block.ret), + } + } + println!("]"); + + println!("{:5} {:05} {:?}", + self.frame().block.line(self.frame().ip).red(), + self.frame().ip.blue(), + self.frame().block.ops[self.frame().ip]); + } + + match op { + Op::Illegal => {} + + Op::Unreachable => {} + + Op::Pop => { + self.stack.pop(); + } + + Op::Constant(value) => { + let typ = Type::from(&value); + self.stack.push(typ); + } + + Op::Neg => { + match self.peek_up(0) { + Type::Float | Type::Int => {}, + a => error!(self, ErrorKind::TypeError(op.clone(), vec![a.clone()])), + } + } + + Op::Add => { + let (a, b) = self.pop_twice(); + match (&a, &b) { + (Type::Float, Type::Float) + | (Type::Int, Type::Int) + | (Type::String, Type::String) => { + self.stack.push(a) + } + _ => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + } + } + + Op::Sub | Op::Mul | Op::Div => { + let (a, b) = self.pop_twice(); + match (&a, &b) { + (Type::Float, Type::Float) + | (Type::Int, Type::Int) => self.stack.push(a), + _ => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + } + } + + Op::Equal | Op::Less | Op::Greater => { + match self.pop_twice() { + (a, b) if (&[&a, &b]).contains(&&Type::UnkownType) => + error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) if a == b => self.stack.push(Type::Bool), + (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + } + } + + Op::And | Op::Or => { + match self.pop_twice() { + (Type::Bool, Type::Bool) => self.stack.push(Type::Bool), + (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + } + } + + Op::Not => { + match self.pop() { + Type::Bool => { self.stack.push(Type::Bool); }, + a => { error!(self, ErrorKind::TypeError(op.clone(), vec![a])) }, + } + } + + Op::Jmp(_line) => { + } + + Op::JmpFalse(_line) => { + match self.pop() { + Type::Bool => {}, + a => { error!(self, ErrorKind::TypeError(op.clone(), vec![a])) }, + } + } + + Op::Assert => { + match self.pop() { + Type::Bool => { self.stack.push(Type::Bool); }, + a => { error!(self, ErrorKind::TypeError(op.clone(), vec![a])) }, + } + } + + Op::ReadLocal(slot) => { + let slot = self.frame().stack_offset + slot; + self.stack.push(self.stack[slot].clone()); + } + + Op::Assign(slot) => { + let slot = self.frame().stack_offset + slot; + let lhs = self.stack[slot].clone(); + let rhs = self.pop(); + match (&lhs, &rhs) { + (Type::UnkownType, rhs) => { + if rhs == &Type::UnkownType { + error!(self, ErrorKind::TypeError(op.clone(), vec![lhs, rhs.clone()]), "Cannot infer type."); + } else { + self.stack[slot] = rhs.clone(); + } + } + (lhs, rhs) if lhs == rhs => {}, + (lhs, rhs) => error!(self, ErrorKind::TypeError(op.clone(), + vec![lhs.clone(), rhs.clone()])), + } + } + + Op::Call(num_args) => { + let new_base = self.stack.len() - 1 - num_args; + match &self.stack[new_base] { + Type::Function(block) => { + let arity = block.args.len(); + if arity != num_args { + error!(self, + ErrorKind::InvalidProgram, + format!("Invalid number of arguments, got {} expected {}.", + num_args, arity)); + } + if self.print_blocks { + block.debug_print(); + } + + let stack_args = &self.stack[self.stack.len() - arity..]; + if block.args != stack_args { + error!(self, + ErrorKind::TypeError(op.clone(), vec![]), + format!("Expected args of type {:?} but got {:?}.", + block.args, stack_args)); + } + + let mut stack = vec![block.ret.clone()]; + stack.extend_from_slice(stack_args); + + let mut sub = VM { + checked: self.checked.clone(), + stack, + frames: vec![], + print_blocks: self.print_blocks, + print_ops: self.print_ops, + }; + + sub.typecheck(Rc::clone(block))?; + + self.checked = sub.checked; + + self.stack[new_base] = block.ret.clone(); + }, + _ => { + unreachable!() + } + } + } + + Op::Print => { + self.pop(); + } + + Op::Return => { + if outer { + return Ok(()); + } + + match self.frame().block.ops[self.frame().ip - 2] { + Op::Return => { + continue; + } + _ => {} + } + + let a = self.stack.pop().unwrap_or(Type::NoType); + let b = self.frame().block.ret.clone(); + if a != b { + error!(self, ErrorKind::TypeError(op, vec![a, b]), "Not matching return type."); + } + } + } + self.frame_mut().ip += 1; + } + } +} @@ -4,6 +4,7 @@ use std::rc::Rc; use std::collections::HashMap; use owo_colors::OwoColorize; +use crate::compiler::Type; use crate::error::{Error, ErrorKind}; macro_rules! error { @@ -74,24 +75,36 @@ pub enum Op { #[derive(Debug)] pub struct Block { - name: String, - file: PathBuf, - ops: Vec<Op>, - last_line_offset: usize, - line_offsets: HashMap<usize, usize>, + pub args: Vec<Type>, + pub ret: Type, + + pub name: String, + pub file: PathBuf, + pub ops: Vec<Op>, + pub last_line_offset: usize, + pub line_offsets: HashMap<usize, usize>, + pub line: usize, } impl Block { - pub fn new(name: &str, file: &Path) -> Self { + pub fn new(name: &str, file: &Path, line: usize) -> Self { Self { + args: Vec::new(), + ret: Type::UnkownType, + name: String::from(name), file: file.to_owned(), ops: Vec::new(), last_line_offset: 0, line_offsets: HashMap::new(), + line, } } + pub fn id(&self) -> (PathBuf, usize) { + (self.file.clone(), self.line) + } + pub fn add_line(&mut self, token_position: usize) { if token_position != self.last_line_offset { self.line_offsets.insert(self.curr(), token_position); @@ -99,7 +112,7 @@ impl Block { } } - fn line(&self, ip: usize) -> usize { + pub fn line(&self, ip: usize) -> usize { for i in (0..=ip).rev() { if let Some(line) = self.line_offsets.get(&i) { return *line; @@ -121,6 +134,10 @@ impl Block { println!(""); } + pub fn last_instruction(&mut self) -> &Op { + self.ops.last().unwrap() + } + pub fn add(&mut self, op: Op, token_position: usize) -> usize { let len = self.curr(); self.add_line(token_position); @@ -211,6 +228,10 @@ impl VM { } pub fn run(&mut self, block: Rc<Block>) -> Result<(), Error>{ + if let Err(err) = crate::typer::VM::new().print_ops(true).typecheck(Rc::clone(&block)) { + println!("TYPE ERROR: {}", err); + } + self.frames.push(Frame { stack_offset: 0, block, @@ -261,7 +282,7 @@ impl VM { match self.stack.pop().unwrap() { Value::Float(a) => self.stack.push(Value::Float(-a)), Value::Int(a) => self.stack.push(Value::Int(-a)), - a => error!(self, ErrorKind::TypeError(op.clone(), vec![a])), + a => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a])), } } @@ -272,7 +293,7 @@ impl VM { (Value::String(a), Value::String(b)) => { self.stack.push(Value::String(Rc::from(format!("{}{}", a, b)))) } - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } @@ -280,7 +301,7 @@ impl VM { match self.pop_twice() { (Value::Float(a), Value::Float(b)) => self.stack.push(Value::Float(a - b)), (Value::Int(a), Value::Int(b)) => self.stack.push(Value::Int(a - b)), - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } @@ -288,7 +309,7 @@ impl VM { match self.pop_twice() { (Value::Float(a), Value::Float(b)) => self.stack.push(Value::Float(a * b)), (Value::Int(a), Value::Int(b)) => self.stack.push(Value::Int(a * b)), - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } @@ -296,7 +317,7 @@ impl VM { match self.pop_twice() { (Value::Float(a), Value::Float(b)) => self.stack.push(Value::Float(a / b)), (Value::Int(a), Value::Int(b)) => self.stack.push(Value::Int(a / b)), - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } @@ -306,7 +327,7 @@ impl VM { (Value::Int(a), Value::Int(b)) => self.stack.push(Value::Bool(a == b)), (Value::String(a), Value::String(b)) => self.stack.push(Value::Bool(a == b)), (Value::Bool(a), Value::Bool(b)) => self.stack.push(Value::Bool(a == b)), - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } @@ -316,7 +337,7 @@ impl VM { (Value::Int(a), Value::Int(b)) => self.stack.push(Value::Bool(a < b)), (Value::String(a), Value::String(b)) => self.stack.push(Value::Bool(a < b)), (Value::Bool(a), Value::Bool(b)) => self.stack.push(Value::Bool(a < b)), - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } @@ -326,28 +347,28 @@ impl VM { (Value::Int(a), Value::Int(b)) => self.stack.push(Value::Bool(a > b)), (Value::String(a), Value::String(b)) => self.stack.push(Value::Bool(a > b)), (Value::Bool(a), Value::Bool(b)) => self.stack.push(Value::Bool(a > b)), - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } Op::And => { match self.pop_twice() { (Value::Bool(a), Value::Bool(b)) => self.stack.push(Value::Bool(a && b)), - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } Op::Or => { match self.pop_twice() { (Value::Bool(a), Value::Bool(b)) => self.stack.push(Value::Bool(a || b)), - (a, b) => error!(self, ErrorKind::TypeError(op.clone(), vec![a, b])), + (a, b) => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a, b])), } } Op::Not => { match self.stack.pop().unwrap() { Value::Bool(a) => self.stack.push(Value::Bool(!a)), - a => error!(self, ErrorKind::TypeError(op.clone(), vec![a])), + a => error!(self, ErrorKind::RuntimeTypeError(op.clone(), vec![a])), } } diff --git a/tests/fun.tdy b/tests/fun.tdy index 8b94cad..8dc3b77 100644 --- a/tests/fun.tdy +++ b/tests/fun.tdy @@ -2,13 +2,13 @@ f := fn { print 1 } -f() <=> true +f() // Simple f2 := fn a: int { print a } -f2(2) <=> true +f2(2) // Return value f3 := fn -> int { @@ -39,3 +39,15 @@ g := fn f: int { } g(h) <=> 1 + + +q := fn i: int -> int { + if i == 1 { + ret 2 + } else { + ret 3 + } +} + +q(1) <=> 2 +q(0) <=> 3 diff --git a/tests/simple.tdy b/tests/simple.tdy index 2f0f606..6dde932 100644 --- a/tests/simple.tdy +++ b/tests/simple.tdy @@ -1,38 +1,14 @@ -// 1 + 1 <=> 2 -// // asdlkjasl -// print 1 + 3 -// // OwO - -// a int := 0 -// b int := 1 -// c int := 3 -// d int := 2 +// a := 1 +// a = 2 + 1 +// a = 3 // -// print a -// print b -// print d -// print c +// for i := 0, i < 10, i = i + 1 { +// print i + 1 +// print i + 2 +// } -for a := 0, a < 10, print a { - print a - a = a + 1 +f := fn b: int -> int { + ret b + 1 } -// 1, 2, 3, 4 - - -// -// === main === -// | Constant(Int(0)) -// | ReadLocal(0) -// | Constant(Int(10)) -// | Less -// | JmpFalse(12) -// | Jmp(11) -// | Jmp(1) -// | ReadLocal(0) -// | Constant(Int(1)) -// | Add -// | Assign(0) -// | Jmp(7) -// | Return +f(1) |
