From f437bb2cc353ba0463b31c48851673b1f4a7dd28 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Sun, 21 Feb 2021 17:12:01 +0100 Subject: don't store multiple versions of same constant --- src/compiler.rs | 51 +++++++++++++++++++++++++++++++++------------------ src/lib.rs | 38 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 71 insertions(+), 18 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index cd4ffda..26c70de 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -255,8 +255,12 @@ pub(crate) struct Compiler { unknown: HashMap, functions: HashMap, - constants: Vec, + strings: Vec, + + constants: Vec, + values: HashMap, + } macro_rules! push_frame { @@ -353,19 +357,11 @@ impl Compiler { functions: HashMap::new(), - constants: vec![Value::Nil], strings: Vec::new(), - } - } - fn nil_value(&self) -> usize { - self.constants.iter() - .enumerate() - .find_map(|(i, x)| - match x { - Value::Nil => Some(i), - _ => None, - }).unwrap() + constants: vec![], + values: HashMap::new(), + } } fn new_blob_id(&mut self) -> usize { @@ -375,8 +371,25 @@ impl Compiler { } fn add_constant(&mut self, value: Value) -> usize { - self.constants.push(value); - self.constants.len() - 1 + if matches!(value, Value::Float(_) + | Value::Int(_) + | Value::Bool(_) + | Value::String(_) + | Value::Tuple(_) + | Value::Nil) { + let entry = self.values.entry(value.clone()); + if let Entry::Occupied(entry) = entry { + *entry.get() + } else { + let slot = self.constants.len(); + self.constants.push(value); + entry.or_insert(slot); + slot + } + } else { + self.constants.push(value); + self.constants.len() - 1 + } } fn intern_string(&mut self, string: String) -> usize { @@ -710,7 +723,7 @@ impl Compiler { if let Some(res) = res { return res; } - let constant = self.add_constant(Value::Nil); + let constant = self.add_constant(Value::Unknown); let line = self.line(); let entry = self.unknown.entry(name.to_string()); entry.or_insert((constant, line)).0 @@ -847,12 +860,13 @@ impl Compiler { } }); + let nil = self.add_constant(Value::Nil); for op in function_block.ops.iter().rev() { match op { Op::Pop | Op::PopUpvalue => {} Op::Return => { break; } , _ => { - add_op(self, &mut function_block, Op::Constant(self.nil_value())); + add_op(self, &mut function_block, Op::Constant(nil)); add_op(self, &mut function_block, Op::Return); break; } @@ -860,7 +874,7 @@ impl Compiler { } if function_block.ops.is_empty() { - add_op(self, &mut function_block, Op::Constant(self.nil_value())); + add_op(self, &mut function_block, Op::Constant(nil)); add_op(self, &mut function_block, Op::Return); } @@ -1440,7 +1454,8 @@ impl Compiler { expect!(self, Token::Newline | Token::EOF, "Expect newline or EOF after expression."); } - add_op(self, &mut block, Op::Constant(self.nil_value())); + let tmp = self.add_constant(Value::Unknown); + add_op(self, &mut block, Op::Constant(tmp)); add_op(self, &mut block, Op::Return); block.ty = Type::Function(Vec::new(), Box::new(Type::Void)); diff --git a/src/lib.rs b/src/lib.rs index 91938f1..5908fa4 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -4,6 +4,7 @@ use std::collections::hash_map::Entry; use std::fmt::Debug; use std::path::{Path, PathBuf}; use std::rc::Rc; +use std::hash::{Hash, Hasher}; use owo_colors::OwoColorize; @@ -198,6 +199,43 @@ impl Debug for Value { } } +impl PartialEq for Value { + fn eq(&self, other: &Value) -> bool { + match (self, other) { + (Value::Float(a), Value::Float(b)) => a == b, + (Value::Int(a), Value::Int(b)) => a == b, + (Value::Bool(a), Value::Bool(b)) => a == b, + (Value::String(a), Value::String(b)) => a == b, + (Value::Tuple(a), Value::Tuple(b)) => { + a.len() == b.len() && a.iter().zip(b.iter()).all(|(a, b)| a == b) + } + (Value::Nil, Value::Nil) => true, + _ => false, + } + } +} + +impl Eq for Value {} + +impl Hash for Value { + fn hash(&self, state: &mut H) { + match self { + Value::Float(a) => { + // We have to limit the values, because + // floats are wierd. + assert!(a.is_finite()); + a.to_bits().hash(state); + }, + Value::Int(a) => a.hash(state), + Value::Bool(a) => a.hash(state), + Value::String(a) => a.hash(state), + Value::Tuple(a) => a.hash(state), + Value::Nil => state.write_i8(0), + _ => {}, + }; + } +} + impl Value { fn identity(self) -> Self { match self { -- cgit v1.2.1 From 839f0b458323f94550071b7d53e38d150439d970 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Mon, 22 Feb 2021 18:38:39 +0100 Subject: WIP: Try to make this work --- src/compiler.rs | 96 ++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 58 insertions(+), 38 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index 26c70de..3c494b2 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -240,6 +240,12 @@ impl Frame { } } +enum Name { + Slot(usize, usize), + Unknown(usize, usize), + Space(HashMap), +} + pub(crate) struct Compiler { curr: usize, tokens: TokenStream, @@ -252,7 +258,6 @@ pub(crate) struct Compiler { blocks: Vec>>, blob_id: usize, - unknown: HashMap, functions: HashMap, @@ -260,7 +265,7 @@ pub(crate) struct Compiler { constants: Vec, values: HashMap, - + names: HashMap, } macro_rules! push_frame { @@ -353,7 +358,6 @@ impl Compiler { blocks: Vec::new(), blob_id: 0, - unknown: HashMap::new(), functions: HashMap::new(), @@ -361,6 +365,7 @@ impl Compiler { constants: vec![], values: HashMap::new(), + names: HashMap::new(), } } @@ -715,18 +720,42 @@ impl Compiler { } 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::Unknown); + match self.names.entry(name.to_string()) { + Entry::Occupied(entry) => { + match entry.get() { + Name::Slot(i, _) => { return *i; }, + Name::Unknown(i, _) => { return *i; }, + _ => unreachable!(), + } + }, + Entry::Vacant(_) => {}, + }; + + let slot = self.add_constant(Value::Unknown); let line = self.line(); - let entry = self.unknown.entry(name.to_string()); - entry.or_insert((constant, line)).0 + self.names.insert(name.to_string(), Name::Unknown(slot, line)); + slot + } + + fn named_constant(&mut self, name: String, value: Value) -> usize { + let line = self.line(); + match self.names.entry(name.clone()) { + Entry::Occupied(mut entry) => { + let slot = if let Name::Unknown(slot, _) = entry.get() { + *slot + } else { + error!(self, format!("Constant named \"{}\" already has a value.", name)); + return 0; + }; + entry.insert(Name::Slot(slot, line)); + self.constants[slot] = value; + return slot; + }, + Entry::Vacant(_) => {}, + } + let slot = self.add_constant(value); + self.names.insert(name, Name::Unknown(slot, line)); + slot } fn call(&mut self, block: &mut Block) { @@ -799,12 +828,12 @@ impl Compiler { let top = self.stack().len() - 1; let name = if let Some(name) = name { - Cow::Owned(String::from(name)) + String::from(name) } else if !self.stack()[top].active { self.stack_mut()[top].active = true; - Cow::Borrowed(&self.stack()[top].name) + self.stack()[top].name.clone() } else { - Cow::Owned(format!("λ {}@{:03}", self.current_file.display(), self.line())) + format!("λ {}@{:03}", self.current_file.display(), self.line()) }; let mut args = Vec::new(); @@ -886,7 +915,7 @@ impl Compiler { // 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); + let constant = self.named_constant(name, function); add_op(self, block, Op::Constant(constant)); } @@ -975,13 +1004,7 @@ impl Compiler { // Remove the function, since it's a constant and we already // added it. block.ops.pop().unwrap(); - let slot = if let Entry::Occupied(entry) = self.unknown.entry(String::from(name)) { - let (_, (slot, _)) = entry.remove_entry(); - self.constants[slot] = self.constants.pop().unwrap(); - slot - } else { - self.constants.len() - 1 - }; + let slot = self.find_constant(name); add_op(self, block, Op::Link(slot)); if let Value::Function(_, block) = &self.constants[slot] { block.borrow_mut().mark_constant(); @@ -1256,12 +1279,7 @@ impl Compiler { expect!(self, Token::RightBrace, "Expected '}' after 'blob' body. AKA '}'."); 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); - } + self.named_constant(name, blob); } fn blob_field(&mut self, block: &mut Block) { @@ -1459,13 +1477,15 @@ 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(); + if self.names.len() != 0 { + let errors: Vec<_> = self.names.iter().filter_map(|(name, kind)| + if let Name::Unknown(_, line) = kind { + Some((ErrorKind::SyntaxError(*line, Token::Identifier(name.clone())), + *line, + format!("Usage of undefined value: '{}'.", name,))) + } else { + None + }) .collect(); for (e, l, m) in errors.iter() { self.error_on_line(e.clone(), *l, Some(m.clone())); } -- cgit v1.2.1 From c4b2781aa8ebfa79a706dec53d1bc459978f51b8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Mon, 22 Feb 2021 19:30:58 +0100 Subject: WIP: Fix some bugs... --- src/compiler.rs | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index 3c494b2..5642a82 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -240,6 +240,7 @@ impl Frame { } } +#[derive(Debug)] enum Name { Slot(usize, usize), Unknown(usize, usize), @@ -827,12 +828,16 @@ impl Compiler { expect!(self, Token::Fn, "Expected 'fn' at start of function."); let top = self.stack().len() - 1; + let constant; let name = if let Some(name) = name { + constant = true; String::from(name) } else if !self.stack()[top].active { + constant = false; self.stack_mut()[top].active = true; self.stack()[top].name.clone() } else { + constant = false; format!("λ {}@{:03}", self.current_file.display(), self.line()) }; @@ -915,7 +920,11 @@ impl Compiler { // 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.named_constant(name, function); + let constant = if constant { + self.named_constant(name, function) + } else { + self.add_constant(function) + }; add_op(self, block, Op::Constant(constant)); } @@ -1477,6 +1486,7 @@ impl Compiler { add_op(self, &mut block, Op::Return); block.ty = Type::Function(Vec::new(), Box::new(Type::Void)); + println!("{:?}", self.names); if self.names.len() != 0 { let errors: Vec<_> = self.names.iter().filter_map(|(name, kind)| if let Name::Unknown(_, line) = kind { @@ -1500,6 +1510,7 @@ impl Compiler { self.panic = false; } + block.debug_print(); self.blocks.insert(0, Rc::new(RefCell::new(block))); if self.errors.is_empty() { -- cgit v1.2.1 From a4113803a4c5aee84987487065b429bbad8d4813 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Mon, 22 Feb 2021 20:53:02 +0100 Subject: fix part of the bugs --- src/compiler.rs | 37 ++++++++++++++++--------------------- 1 file changed, 16 insertions(+), 21 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index 5642a82..b3150ba 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -755,7 +755,7 @@ impl Compiler { Entry::Vacant(_) => {}, } let slot = self.add_constant(value); - self.names.insert(name, Name::Unknown(slot, line)); + self.names.insert(name, Name::Slot(slot, line)); slot } @@ -824,20 +824,16 @@ impl Compiler { } // TODO(ed): de-complexify - fn function(&mut self, block: &mut Block, name: Option<&str>) { + fn function(&mut self, block: &mut Block, in_name: Option<&str>) { expect!(self, Token::Fn, "Expected 'fn' at start of function."); let top = self.stack().len() - 1; - let constant; - let name = if let Some(name) = name { - constant = true; + let name = if let Some(name) = in_name { String::from(name) } else if !self.stack()[top].active { - constant = false; self.stack_mut()[top].active = true; self.stack()[top].name.clone() } else { - constant = false; format!("λ {}@{:03}", self.current_file.display(), self.line()) }; @@ -920,7 +916,7 @@ impl Compiler { // 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 = if constant { + let constant = if in_name.is_some() { self.named_constant(name, function) } else { self.add_constant(function) @@ -1008,20 +1004,19 @@ 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(); - let slot = self.find_constant(name); - add_op(self, block, Op::Link(slot)); - if let Value::Function(_, block) = &self.constants[slot] { - block.borrow_mut().mark_constant(); - } else { - unreachable!(); - } - return; + if self.frames.len() <= 1 && self.peek() == Token::Fn { + self.function(block, Some(name)); + // Remove the function, since it's a constant and we already + // added it. + block.ops.pop().unwrap(); + let slot = self.find_constant(name); + add_op(self, block, Op::Link(slot)); + if let Value::Function(_, block) = &self.constants[slot] { + block.borrow_mut().mark_constant(); + } else { + unreachable!(); } + return; } let var = Variable::new(name, false, typ); -- cgit v1.2.1 From 40f2c2cabfdfbace9bc9116be7228b2db9348c13 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Mon, 22 Feb 2021 21:19:17 +0100 Subject: fix another bug?? --- src/compiler.rs | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index b3150ba..89ef9e0 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -322,7 +322,7 @@ macro_rules! push_scope { errors.push(( e, var.line, - format!("Usage of undefined value: '{}'.", var.name),) + format!("Variable is unused: '{}'.", var.name),) ); } if var.captured { @@ -853,7 +853,8 @@ impl Compiler { expect!(self, Token::Colon, "Expected ':' after parameter name."); if let Ok(typ) = self.parse_type() { args.push(typ.clone()); - let var = Variable::new(&name, true, typ); + let mut var = Variable::new(&name, true, typ); + var.read = true; if let Ok(slot) = self.define(var) { self.stack_mut()[slot].active = true; } @@ -959,7 +960,9 @@ impl Compiler { } } _ => { - if !parse_branch!(self, block, self.call(block)) { + if matches!(self.peek(), Token::Bang | Token::LeftParen) { + self.call(block) + } else { return; } } -- cgit v1.2.1 From 8e001b54fb2f74e4e68ea2c75ab0be8db5ea9de5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Mon, 22 Feb 2021 21:19:29 +0100 Subject: fix all the tests that had unused variables --- src/lib.rs | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'src') diff --git a/src/lib.rs b/src/lib.rs index 5908fa4..9b938ab 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1244,6 +1244,11 @@ for i := 0, i < 10, i += 1 { if i == 2 { break } + + q + qq + qqq + qqqq } a <=> 3 ", @@ -1260,6 +1265,11 @@ for i := 0, i < 4, i += 1 { continue } a = a + 1 + + q + qq + qqq + qqqq } a <=> 3 ", @@ -1301,7 +1311,9 @@ a := 0 b := 99999 { a := 99999 + a } + b a -= 1 } a <=> -1 -- cgit v1.2.1 From 02d8f7592ff7bcdf356df7256db20fbd23c5afa9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Edvard=20Th=C3=B6rnros?= Date: Mon, 22 Feb 2021 21:24:12 +0100 Subject: remove parse_branch(..., call()) --- src/compiler.rs | 20 +++++++++++++++----- 1 file changed, 15 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/compiler.rs b/src/compiler.rs index 89ef9e0..ec3a52c 100644 --- a/src/compiler.rs +++ b/src/compiler.rs @@ -39,6 +39,9 @@ macro_rules! expect { }; } +// NOTE(ed): This can cause some strange bugs. It would be nice if we could +// remove this function, but to do that we need to rewrite some code. Like +// tuples and fields. Might be worth it tough. macro_rules! parse_branch { ($compiler:expr, $block:expr, [ $( $call:expr ),* ]) => { { @@ -759,6 +762,15 @@ impl Compiler { slot } + fn call_maybe(&mut self, block: &mut Block) -> bool { + if matches!(self.peek(), Token::Bang | Token::LeftParen) { + self.call(block); + true + } else { + false + } + } + fn call(&mut self, block: &mut Block) { let mut arity = 0; match self.peek() { @@ -960,9 +972,7 @@ impl Compiler { } } _ => { - if matches!(self.peek(), Token::Bang | Token::LeftParen) { - self.call(block) - } else { + if !self.call_maybe(block) { return; } } @@ -973,7 +983,7 @@ impl Compiler { // 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)); + self.call_maybe(block); } fn define(&mut self, mut var: Variable) -> Result { @@ -1343,7 +1353,7 @@ impl Compiler { return; } _ => { - if !parse_branch!(self, block, self.call(block)) { + if !self.call_maybe(block) { error!(self, "Unexpected token when parsing blob-field."); return; } -- cgit v1.2.1