diff options
Diffstat (limited to 'matrix-lang')
25 files changed, 6463 insertions, 0 deletions
diff --git a/matrix-lang/Cargo.lock b/matrix-lang/Cargo.lock new file mode 100644 index 0000000..ed6e714 --- /dev/null +++ b/matrix-lang/Cargo.lock @@ -0,0 +1,119 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "aho-corasick" +version = "1.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b2969dcb958b36655471fc61f7e416fa76033bdd4bfed0678d8fee1e2d07a1f0" +dependencies = [ + "memchr", +] + +[[package]] +name = "anyhow" +version = "1.0.79" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "080e9890a082662b09c1ad45f567faeeb47f22b5fb23895fbe1e651e718e25ca" + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "matrix" +version = "0.1.0" +dependencies = [ + "anyhow", + "num-complex", + "num-rational", + "regex", +] + +[[package]] +name = "memchr" +version = "2.7.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "523dc4f511e55ab87b694dc30d0f820d60906ef06413f93d4d7a1385599cc149" + +[[package]] +name = "num-bigint" +version = "0.4.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "608e7659b5c3d7cba262d894801b9ec9d00de989e8a82bd4bef91d08da45cdc0" +dependencies = [ + "autocfg", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-complex" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "23c6602fda94a57c990fe0df199a035d83576b496aa29f4e634a8ac6004e68a6" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-integer" +version = "0.1.46" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7969661fd2958a5cb096e56c8e1ad0444ac2bbcd0061bd28660485a44879858f" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-rational" +version = "0.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0638a1c9d0a3c0914158145bc76cff373a75a627e6ecbfb71cbe6f453a5a19b0" +dependencies = [ + "autocfg", + "num-bigint", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "da0df0e5185db44f69b44f26786fe401b6c293d1907744beaa7fa62b2e5a517a" +dependencies = [ + "autocfg", +] + +[[package]] +name = "regex" +version = "1.10.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b62dbe01f0b06f9d8dc7d49e05a0785f153b00b2c227856282f671e0318c9b15" +dependencies = [ + "aho-corasick", + "memchr", + "regex-automata", + "regex-syntax", +] + +[[package]] +name = "regex-automata" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5bb987efffd3c6d0d8f5f89510bb458559eab11e4f869acb20bf845e016259cd" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax", +] + +[[package]] +name = "regex-syntax" +version = "0.8.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c08c74e62047bb2de4ff487b251e4a92e24f48745648451635cec7d591162d9f" diff --git a/matrix-lang/Cargo.toml b/matrix-lang/Cargo.toml new file mode 100644 index 0000000..067f77c --- /dev/null +++ b/matrix-lang/Cargo.toml @@ -0,0 +1,12 @@ +[package] +name = "matrix-lang" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +anyhow = "1" +num-complex = "0.4" +num-rational = "0.4" +regex = "1" diff --git a/matrix-lang/src/ast.rs b/matrix-lang/src/ast.rs new file mode 100644 index 0000000..5720f76 --- /dev/null +++ b/matrix-lang/src/ast.rs @@ -0,0 +1,482 @@ +use std::{ops::{Neg, Not}, fmt::{Debug, Display}}; + +use crate::prelude::*; + +pub type AstName = (Rc<str>, Position); +pub type InlineList = Vec<Expr>; +pub type InlineMatrix = (usize, usize, Vec<Expr>); +pub type InlineTable = Vec<(Expr, Expr)>; + +#[derive(Debug, Clone, Copy, Eq, PartialEq)] +pub enum UnaryOp { + // normal math + Negate = 1, + // equality + Not = 2, +} + +impl TryFrom<u8> for UnaryOp { + type Error = Exception; + + fn try_from(value: u8) -> std::prelude::v1::Result<Self, Self::Error> { + if value < 1 || value > 2 { + Err(exception!(BINARY_EXCEPTION, "cannot convert {value} to UnaryOp")) + } else { + unsafe { Ok(std::mem::transmute(value)) } + } + } +} + +#[derive(Debug, Clone, Copy, Eq, PartialEq)] +pub enum BinaryOp { + // normal math + Add = 1, + Subtract = 2, + Multiply = 3, + Divide = 4, + Modulo = 5, + Power = 6, + // binary math + BitwiseAnd = 7, + BitwiseOr = 8, + BitwiseXor = 9, + BitwiseShiftLeft = 10, + BitwiseShiftRight = 11, + // equality + Equals = 12, + NotEquals = 13, + GreaterEquals = 14, + LessEquals = 15, + GreaterThan = 16, + LessThan = 17, + // iter + Range = 18, + RangeEq = 19 +} + +impl TryFrom<u8> for BinaryOp { + type Error = Exception; + + fn try_from(value: u8) -> std::prelude::v1::Result<Self, Self::Error> { + if value < 1 || value > 19 { + Err(exception!(BINARY_EXCEPTION, "cannot convert {value} to BinaryOp")) + } else { + unsafe { Ok(std::mem::transmute(value)) } + } + } +} + +#[derive(Debug, Clone, PartialEq)] +pub enum ExprData { + NoOp, + + Literal(Value), + Ident(Rc<str>), + + UnaryOp(Box<Expr>, UnaryOp), + BinaryOp(Box<Expr>, Box<Expr>, BinaryOp), + + Index(Box<Expr>, Vec<Expr>), + FnCall(Box<Expr>, Vec<Expr>), + FieldAccess(Box<Expr>, AstName), + + List(InlineList), + Matrix(InlineMatrix), + Table(InlineTable), + + And(Box<Expr>, Box<Expr>), + Or(Box<Expr>, Box<Expr>), + + Assign(Box<Expr>, Box<Expr>), + + If(Box<Expr>, Box<Expr>, Option<Box<Expr>>), + Function(AstName, Vec<AstName>, Box<Expr>, bool), + Lambda(Vec<AstName>, Box<Expr>, bool), + + Loop(Box<Expr>), + While(Box<Expr>, Box<Expr>), + DoWhile(Box<Expr>, Box<Expr>), + For(AstName, Box<Expr>, Box<Expr>), + + Block(Vec<Expr>), + + Try(Box<Expr>, AstName, Box<Expr>), + + Let(AstName, Box<Expr>), + Const(AstName, Box<Expr>), + + Pipeline(Box<Expr>, Box<Expr>), + + Continue, + Break, + Return(Box<Expr>), +} + +impl Display for Expr { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{self:?}") + } +} + +impl Debug for Expr { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{:?}", self.data) + } +} + +#[derive(Clone, PartialEq)] +pub struct Expr { + pub data: ExprData, + pub pos: Position +} + +impl From<(ExprData, Position)> for Expr { + fn from(value: (ExprData, Position)) -> Self { + Self { data: value.0, pos: value.1 } + } +} + +impl Neg for BinaryOp { + type Output = Option<Self>; + fn neg(self) -> Self::Output { + use BinaryOp::*; + Some(match self { + Add => Subtract, + Subtract => Add, + _ => return None + }) + } +} + +impl Not for BinaryOp { + type Output = Option<Self>; + fn not(self) -> Self::Output { + use BinaryOp::*; + Some(match self { + Equals => NotEquals, + NotEquals => Equals, + GreaterEquals => LessThan, + LessEquals => GreaterThan, + GreaterThan => LessEquals, + LessThan => GreaterEquals, + _ => return None + }) + } +} + +impl Neg for Expr { + type Output = std::result::Result<Self, Self>; + fn neg(mut self) -> Self::Output { + use ExprData as E; + let mut pos = self.pos; + let data = match self.data { + E::Literal(v) => E::Literal(-v), + E::BinaryOp(lhs, rhs, op) => { + let Some(op_n) = -op else { + return Err((E::BinaryOp(lhs, rhs, op), pos).into()); + }; + if let Ok(lhs) = -*lhs.clone() { + pos = lhs.pos; + E::BinaryOp(Box::new(lhs), rhs, op_n) + } else if let Ok(rhs) = -*rhs.clone() { + pos = rhs.pos; + E::BinaryOp(lhs, Box::new(rhs), op_n) + } else { + return Err((E::BinaryOp(lhs, rhs, op), pos).into()); + } + }, + E::UnaryOp(expr, op) => { + match op { + UnaryOp::Negate => { + pos = expr.pos; + expr.data + }, + _ => return Err((E::UnaryOp(expr, op), pos).into()) + } + } + data => return Err((data, pos).into()) + }; + self.data = data; + self.pos = pos; + Ok(self) + } +} + +impl Not for Expr { + type Output = std::result::Result<Self, Self>; + fn not(mut self) -> Self::Output { + use ExprData as E; + let mut pos = self.pos; + let data = match self.data { + E::Literal(v) => E::Literal(Value::Bool(!v)), + E::UnaryOp(expr, op) => { + match op { + self::UnaryOp::Not => { + pos = expr.pos; + expr.data + }, + _ => return Err((E::UnaryOp(expr, op), pos).into()) + } + } + data => return Err((data, pos).into()) + }; + self.data = data; + self.pos = pos; + Ok(self) + } +} + +pub fn optimize(mut expr: Expr) -> Result<Expr> { + use ExprData as E; + let mut pos = expr.pos; + let data: ExprData = match expr.data { + E::UnaryOp(expr, op) => { + let expr = optimize(*expr)?; + match match op { + UnaryOp::Negate => -expr, + UnaryOp::Not => !expr, + } { + Ok(expr) => { + pos = expr.pos; + expr.data + }, + Err(expr) => E::UnaryOp(Box::new(expr), op) + } + }, + E::BinaryOp(lhs, rhs, op) => { + let lhs = optimize(*lhs)?; + let rhs = optimize(*rhs)?; + if let (E::Literal(l), E::Literal(r)) = (lhs.clone().data, rhs.clone().data) { + match Value::binary_op(op, l, r) { + Err(err) => return Err(err), + Ok(value) => E::Literal(value), + } + } else { + E::BinaryOp(Box::new(lhs), Box::new(rhs), op) + } + }, + E::FnCall(ident, values) => { + E::FnCall(ident, values + .into_iter() + .map(optimize) + .collect::<Result<Vec<Expr>>>()?) + } + E::FieldAccess(expr, ident) => { + let expr = optimize(*expr)?; + E::FieldAccess(Box::new(expr), ident) + }, + E::List(list) => + E::List(list.into_iter() + .map(optimize) + .collect::<Result<Vec<Expr>>>()?), + E::Matrix(mat) => + E::Matrix((mat.0, mat.1, + mat.2.into_iter().map(optimize) + .collect::<Result<Vec<Expr>>>()?)), + E::Table(table) => + E::Table(table + .into_iter() + .map(|(k, v)| { + let k = optimize(k)?; + let v = optimize(v)?; + Ok((k, v)) + }).collect::<Result<Vec<(Expr, Expr)>>>()?), + E::And(lhs, rhs) => { + let lhs = optimize(*lhs)?; + let rhs = optimize(*rhs)?; + if let (E::Literal(l), r) = (lhs.clone().data, rhs.clone().data) { + match !!l.clone() { + true => { + pos = rhs.pos; + r + }, + false => { + pos = lhs.pos; + E::Literal(l) + }, + } + } else { + E::And(Box::new(lhs), Box::new(rhs)) + } + }, + E::Or(lhs, rhs) => { + let lhs = optimize(*lhs)?; + let rhs = optimize(*rhs)?; + if let (E::Literal(l), r) = (lhs.clone().data, rhs.clone().data) { + match !l.clone() { + true => { + pos = rhs.pos; + r + }, + false => { + pos = lhs.pos; + E::Literal(l) + }, + } + } else { + E::And(Box::new(lhs), Box::new(rhs)) + } + }, + E::Block(b) => { + let len = b.len(); + let b: Vec<Expr> = + b.into_iter() + .map(optimize) + .collect::<Result<Vec<Expr>>>()? + .into_iter() + .enumerate() + .filter(|(i, e)| { + if let E::Literal(_) = e.data { + return i + 1 == len + } + E::NoOp != e.data + }) + .map(|e| e.1) + .collect(); + if b.is_empty() { + E::NoOp + } else { + E::Block(b) + } + }, + E::If(cond, block, else_block) => { + let cond = optimize(*cond)?; + let block = optimize(*block)?; + let else_block = else_block.map(|e| optimize(*e)).transpose()?; + if let E::Literal(lit) = cond.data { + if !!lit { + pos = block.pos; + block.data + } else if let Some(else_block) = else_block { + pos = else_block.pos; + else_block.data + } else { + E::NoOp + } + } else { + E::If(Box::new(cond), Box::new(block), else_block.map(|e| Box::new(e))) + } + }, + E::While(cond, block) => { + let cond = optimize(*cond)?; + let block = optimize(*block)?; + if let E::Literal(lit) = cond.data { + if !!lit { + E::Loop(Box::new(block)) + } else { + E::NoOp + } + } else { + E::While(Box::new(cond), Box::new(block)) + } + }, + E::For(name, cond, block) => { + let cond = optimize(*cond)?; + let block = optimize(*block)?; + E::For(name, Box::new(cond), Box::new(block)) + } + E::DoWhile(block, cond) => { + let cond = optimize(*cond)?; + let block = optimize(*block)?; + if let E::Literal(lit) = &cond.data { + if !!lit.clone() { + E::Loop(Box::new(block)) + } else { + E::DoWhile(Box::new(block), Box::new(cond)) + } + } else { + E::DoWhile(Box::new(block), Box::new(cond)) + } + } + E::Loop(block) => { + let block = Box::new(optimize(*block)?); + E::Loop(block) + }, + E::Try(expr, err, catch) => { + let expr = Box::new(optimize(*expr)?); + let catch = Box::new(optimize(*catch)?); + E::Try(expr, err, catch) + }, + E::Function(ident, params, stmt, varadic) => { + let stmt = Box::new(optimize(*stmt)?); + E::Function(ident, params, stmt, varadic) + } + E::Lambda(params, stmt, varadic) => { + let stmt = Box::new(optimize(*stmt)?); + E::Lambda(params, stmt, varadic) + }, + E::Let(ident, expr) => { + E::Let(ident, Box::new(optimize(*expr)?)) + }, + E::Const(ident, expr) => { + E::Const(ident, Box::new(optimize(*expr)?)) + }, + E::Assign(lhs, rhs) => { + let lhs = Box::new(optimize(*lhs)?); + let rhs = Box::new(optimize(*rhs)?); + E::Assign(lhs, rhs) + }, + E::Return(expr) => { + let expr = Box::new(optimize(*expr)?); + E::Return(expr) + }, + E::Pipeline(lhs, rhs) => { + let lhs = Box::new(optimize(*lhs)?); + let rhs = Box::new(optimize(*rhs)?); + E::Pipeline(lhs, rhs) + } + data => data + }; + expr.data = data; + expr.pos = pos; + Ok(expr) +} + +impl From<TokenData> for UnaryOp { + fn from(value: TokenData) -> Self { + use TokenData as T; + match value { + T::Subtract => Self::Negate, + T::Not => Self::Not, + _ => panic!("aaaaa") + } + } +} + +impl From<TokenData> for BinaryOp { + fn from(value: TokenData) -> Self { + use TokenData as T; + match value { + T::Equal => Self::Equals, + T::NotEqual => Self::NotEquals, + T::GreaterEqual => Self::GreaterEquals, + T::LessEqual => Self::LessEquals, + T::GreaterThan => Self::GreaterThan, + T::LessThan => Self::LessThan, + T::BitwiseShiftLeft => Self::BitwiseShiftLeft, + T::BitwiseShiftRight => Self::BitwiseShiftRight, + T::BitwiseAnd => Self::BitwiseAnd, + T::BitwiseOr => Self::BitwiseOr, + T::BitwiseXor => Self::BitwiseXor, + T::Add => Self::Add, + T::Subtract => Self::Subtract, + T::Multiply => Self::Multiply, + T::Divide => Self::Divide, + T::Modulo => Self::Modulo, + T::Power => Self::Power, + _ => panic!("aaaaa") + } + } +} + +impl Expr { + pub fn is_assignable(&self) -> bool { + use ExprData as E; + match self.data { + E::Ident(_) => true, + E::Index(_, _) => true, + E::FieldAccess(_, _) => true, + _ => false, + } + } +} diff --git a/matrix-lang/src/binary/deserialize.rs b/matrix-lang/src/binary/deserialize.rs new file mode 100644 index 0000000..679f6e5 --- /dev/null +++ b/matrix-lang/src/binary/deserialize.rs @@ -0,0 +1,160 @@ +use crate::prelude::*; + +use super::{prim::VarInt, Deserialize, Deserializer}; + +macro_rules! error { + ($($arg:tt)*) => { + exception!(BINARY_EXCEPTION, $($arg)*) + }; +} + +impl Deserialize for Program { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + for _ in 0..5 { s.read::<u8>()?; } // skip header + let version: u8 = s.read()?; + if version != 0 { + return Err(error!("invalid program version {version}")) + } + let fun = <Rc<Function>>::deserialize(s)?; + Ok(Self { version, fun }) + } +} + +impl Deserialize for Instruction { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + use Instruction as I; + let ins: u8 = s.read()?; + let ins = match ins { + 0 => I::NoOp, + 1 => I::CreateLocal, + 2 => I::LoadLocal(s.read()?), + 3 => I::StoreLocal(s.read()?), + 4 => I::DiscardLocals(s.read()?), + 5 => I::LoadGlobal(s.read()?), + 6 => I::StoreGlobal(s.read()?), + 7 => I::Const(s.read()?), + 8 => I::Int(s.read()?), + 9 => I::True, + 10 => I::False, + 11 => I::Nil, + 12 => I::Dup, + 13 => I::Discard(s.read()?), + 14 => I::UnaryOp(UnaryOp::try_from(s.read::<u8>()?)?), + 15 => I::BinaryOp(BinaryOp::try_from(s.read::<u8>()?)?), + 16 => I::NewList(s.read()?), + 17 => I::NewTable(s.read()?), + 18 => I::NewMatrix(s.read()?, s.read()?), + 19 => I::Field(s.read()?), + 20 => I::StoreField(s.read()?), + 21 => I::Index(s.read()?), + 22 => I::StoreIndex(s.read()?), + 23 => I::Jump(s.read()?), + 24 => I::JumpTrue(s.read()?), + 25 => I::JumpFalse(s.read()?), + 26 => I::JumpNil(s.read()?), + 27 => I::IterCreate, + 28 => I::IterNext, + 29 => I::Try(s.read()?), + 30 => I::TryEnd, + 31 => I::Call(s.read()?), + 32 => I::Return, + n => return Err(error!("invalid instruction op code {n}")) + }; + Ok(ins) + } +} + +impl<T: Deserialize> Deserialize for Vec<T> { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + let len = s.read::<VarInt>()?.0; + let mut vec = Vec::with_capacity(len); + for _ in 0..len { + let v = T::deserialize(s)?; + vec.push(v); + } + Ok(vec) + } +} + +impl<T: Deserialize> Deserialize for Gc<T> { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + Ok(Gc::new(T::deserialize(s)?)) + } +} + +impl<T: Deserialize> Deserialize for Rc<T> { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + Ok(Rc::new(T::deserialize(s)?)) + } +} + +impl Deserialize for Position { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + let row = s.read::<VarInt>()?.0; + let col = s.read::<VarInt>()?.0; + Ok(Self { row, col }) + } +} + +impl Deserialize for Chunk { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + let constants = <Vec<Value>>::deserialize(s)?; + let code = <Vec<Instruction>>::deserialize(s)?; + let pos = <Vec<Position>>::deserialize(s)?; + Ok(Self { constants, code, pos }) + } +} + +impl Deserialize for Value { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + use Value as V; + let ty = s.read::<u8>()?; + let value = match ty { + 0 => V::Nil, + 1 => V::Bool(s.read()?), + 2 => V::Int(s.read()?), + 3 => V::Float(s.read()?), + 4 => V::Ratio(Rational64::new(s.read()?, s.read()?)), + 5 => V::Complex(Complex64::new(s.read()?, s.read()?)), + 6 => V::to_regex(s.read::<String>()?.as_str())?, + 7 => V::String(s.read::<String>()?.into()), + 8 => V::List(<Vec<Value>>::deserialize(s)?.into()), + 9 => { + let domain = s.read()?; + let codomain = s.read()?; + let values = <Vec<Value>>::deserialize(s)?; + V::Matrix(Matrix::new(domain, codomain, values).into()) + }, + 10 => { + let len = s.read::<VarInt>()?.0; + let mut table = ValueMap::new(); + for _ in 0..len { + let key = <Value>::deserialize(s)?; + let value = <Value>::deserialize(s)?; + table.insert(key, value)?; + } + V::Table(table.into()) + }, + 11 => V::Function(<Rc<Function>>::deserialize(s)?), + 12 => V::Range((s.read()?, s.read()?, s.read()?).into()), + 13 => V::Iter(<Rc<Function>>::deserialize(s)?), + n => return Err(error!("invalid value code {n}")) + }; + Ok(value) + } +} + +impl Deserialize for Function { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self> { + let name = s.read::<String>()?; + let arity = s.read()?; + let variadic = s.read()?; + let chunk = <Chunk>::deserialize(s)?; + Ok(Function { + name: Rc::from(name.as_str()), + arity, + variadic, + fun: InnerFunction::Compiled(chunk.into()) + }) + } +} diff --git a/matrix-lang/src/binary/mod.rs b/matrix-lang/src/binary/mod.rs new file mode 100644 index 0000000..53b3fe5 --- /dev/null +++ b/matrix-lang/src/binary/mod.rs @@ -0,0 +1,154 @@ +use crate::prelude::*; +use std::io::{self, Read, Write}; + +mod serialize; +mod deserialize; +mod prim; + +pub struct Program { + version: u8, + fun: Rc<Function> +} + +const PROGRAM_HEADER: [u8; 5] = [0x00, 0x4d, 0x41, 0x54, 0x0a]; + +impl Program { + pub fn load(body: &str) -> Result<Option<Rc<Function>>> { + let mut bytes = body.as_bytes(); + if bytes.len() < 6 { + return Ok(None) + } + let header = &bytes[0..5]; + if header != &PROGRAM_HEADER { + return Ok(None) + } + let mut s = ProgramDeserializer::from(&mut bytes); + let program = <Self>::deserialize(&mut s)?; + s.finish()?; + Ok(Some(program.fun.clone())) + } + + pub fn save<W: Write>(fun: Rc<Function>, w: &mut W) -> Result<()> { + let mut s = ProgramSerializer::from(w); + let p = Program { + version: 0, + fun + }; + s.serialize(&p)?; + s.finish()?; + Ok(()) + } +} + +pub trait Primitive : Sized { + fn write<W: Write>(&self, w: &mut W) -> io::Result<()>; + fn read<R: Read>(r: &mut R) -> io::Result<Self>; +} + +pub trait Serialize : Sized { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()>; +} + +pub trait Serializer : Sized { + fn serialize<S: Serialize>(&mut self, val: &S) -> Result<()> { + val.serialize(self) + } + fn write<P: Primitive>(&mut self, val: P) -> Result<()>; +} + +pub trait Deserialize : Sized { + fn deserialize<S: Deserializer>(s: &mut S) -> Result<Self>; +} + +pub trait Deserializer : Sized { + fn deserialize<D: Deserialize>(&mut self) -> Result<D> { + D::deserialize(self) + } + fn read<P: Primitive>(&mut self) -> Result<P>; +} + +macro_rules! error { + ($($arg:tt)*) => { + exception!(BINARY_EXCEPTION, $($arg)*) + }; +} + +pub struct ProgramSerializer<'w, W: Write> { + writer: &'w mut W, + checksum: u64, +} + +impl<'w, W: Write> ProgramSerializer<'w, W> { + fn finish(self) -> Result<()> { + let bytes = self.checksum.to_le_bytes(); + self.writer.write(&bytes).map_err(|e| error!("{e}"))?; + Ok(()) + } +} + +impl<'w, W: Write> Serializer for ProgramSerializer<'w, W> { + fn write<P: Primitive>(&mut self, val: P) -> Result<()> { + val.write(self).map_err(|e| error!("{e}")) + } +} + +impl<'w, W: Write> Write for ProgramSerializer<'w, W> { + fn write(&mut self, buf: &[u8]) -> io::Result<usize> { + for b in buf { + self.checksum %= 0xf1e3beef; + self.checksum += *b as u64; + } + self.writer.write(buf) + } + + fn flush(&mut self) -> io::Result<()> { + self.writer.flush() + } +} + +impl<'w, W: Write> From<&'w mut W> for ProgramSerializer<'w, W> { + fn from(writer: &'w mut W) -> Self { + Self { writer, checksum: 0xfe } + } +} + +pub struct ProgramDeserializer<'r, R: Read> { + reader: &'r mut R, + checksum: u64, +} + +impl<'r, R: Read> ProgramDeserializer<'r, R> { + fn finish(self) -> Result<()> { + let mut bytes = [0u8; 8]; + self.reader.read_exact(&mut bytes).map_err(|e| error!("{e}"))?; + let checksum = u64::from_le_bytes(bytes); + if self.checksum != checksum { + return Err(error!("checksum doesnt match")) + } + Ok(()) + } +} + +impl<'r, R: Read> Deserializer for ProgramDeserializer<'r, R> { + fn read<P: Primitive>(&mut self) -> Result<P> { + P::read(self).map_err(|e| error!("{e}")) + } +} + +impl<'r, R: Read> Read for ProgramDeserializer<'r, R> { + fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> { + let c = self.reader.read(buf)?; + for i in 0..c { + let b = buf[i]; + self.checksum %= 0xf1e3beef; + self.checksum += b as u64; + } + Ok(c) + } +} + +impl<'r, R: Read> From<&'r mut R> for ProgramDeserializer<'r, R> { + fn from(reader: &'r mut R) -> Self { + Self { reader, checksum: 0xfe } + } +} diff --git a/matrix-lang/src/binary/prim.rs b/matrix-lang/src/binary/prim.rs new file mode 100644 index 0000000..44e6898 --- /dev/null +++ b/matrix-lang/src/binary/prim.rs @@ -0,0 +1,109 @@ +use super::Primitive; +use std::io::{self, Read, Write}; + +macro_rules! marshal_number { + ($type:ident, $byte:expr) => { + impl Primitive for $type { + fn write<W: Write>(&self, write: &mut W) -> io::Result<()> { + write.write(&self.to_le_bytes())?; + Ok(()) + } + + fn read<R: Read>(read: &mut R) -> io::Result<Self> { + let mut bytes = [0u8; $byte]; + read.read_exact(&mut bytes)?; + Ok(Self::from_le_bytes(bytes)) + } + } + }; +} + +marshal_number!(u8, 1); +marshal_number!(u16, 2); +marshal_number!(i16, 2); +marshal_number!(u32, 4); +marshal_number!(i64, 8); +marshal_number!(f64, 8); + +impl Primitive for bool { + fn write<W: Write>(&self, write: &mut W) -> io::Result<()> { + if *self { + write.write(&[1u8; 1])?; + } else { + write.write(&[0u8; 1])?; + } + Ok(()) + } + + fn read<R: Read>(read: &mut R) -> io::Result<Self> { + let mut bytes = [0u8; 1]; + read.read_exact(&mut bytes)?; + if bytes[0] == 1 { + Ok(true) + } else { + Ok(false) + } + } +} + +impl Primitive for String { + fn write<W: Write>(&self, write: &mut W) -> io::Result<()> { + let bytes = self.as_bytes(); + let len = bytes.len(); + write.write(&(len as u32).to_le_bytes())?; + write.write(&bytes)?; + Ok(()) + } + + fn read<R: Read>(read: &mut R) -> io::Result<Self> { + let len = usize::read(read)?; + let mut bytes = vec![0u8; len]; + read.read_exact(&mut bytes)?; + Ok(String::from_utf8_lossy(bytes.as_slice()).to_string()) + } +} + +impl Primitive for usize { + fn write<W: Write>(&self, write: &mut W) -> io::Result<()> { + (*self as u32).write(write) + } + + fn read<R: Read>(read: &mut R) -> io::Result<Self> { + Ok(u32::read(read)? as usize) + } +} + +pub struct VarInt(pub usize); + +impl Primitive for VarInt { + fn write<W: Write>(&self, write: &mut W) -> io::Result<()> { + let mut data = self.0; + loop { + let mut byte = (data & 0x7F) as u8; + data >>= 7; + if data != 0 { + byte += 0x80; + } + write.write(&[byte; 1])?; + if data == 0 { + return Ok(()) + } + } + } + + fn read<R: Read>(read: &mut R) -> io::Result<Self> { + let mut buf = [0]; + let mut result = 0usize; + for count in 0..8 { + if read.read(&mut buf)? != 1 { + return Ok(Self(0)) + } + let byte = buf[0]; + result |= ((byte & 0x7F) as usize) << (7 * count); + if byte & 0x80 == 0 { + return Ok(Self(result)) + } + } + Ok(Self(0)) + } +} diff --git a/matrix-lang/src/binary/serialize.rs b/matrix-lang/src/binary/serialize.rs new file mode 100644 index 0000000..2f2b199 --- /dev/null +++ b/matrix-lang/src/binary/serialize.rs @@ -0,0 +1,283 @@ +use crate::{prelude::*, binary::PROGRAM_HEADER}; +use std::ops::Deref; +use super::{prim::VarInt, Program, Serializer, Serialize}; + +macro_rules! error { + ($($arg:tt)*) => { + exception!(BINARY_EXCEPTION, $($arg)*) + }; +} + +impl Serialize for Program { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + for b in PROGRAM_HEADER { + s.write(b)?; + } + s.write(self.version)?; + s.serialize(self.fun.as_ref())?; + Ok(()) + } +} + +impl Serialize for Instruction { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + use Instruction as I; + match self { + I::NoOp => { + s.write(0u8)?; + }, + I::CreateLocal => { + s.write(1u8)?; + }, + I::LoadLocal(idx) => { + s.write(2u8)?; + s.write(*idx)?; + }, + I::StoreLocal(idx) => { + s.write(3u8)?; + s.write(*idx)?; + }, + I::DiscardLocals(idx) => { + s.write(4u8)?; + s.write(*idx)?; + }, + I::LoadGlobal(idx) => { + s.write(5u8)?; + s.write(*idx)?; + } + I::StoreGlobal(idx) => { + s.write(6u8)?; + s.write(*idx)?; + }, + I::Const(idx) => { + s.write(7u8)?; + s.write(*idx)?; + }, + I::Int(i) => { + s.write(8u8)?; + s.write(*i)?; + }, + I::True => { + s.write(9u8)?; + }, + I::False => { + s.write(10u8)?; + }, + I::Nil => { + s.write(11u8)?; + }, + I::Dup => { + s.write(12u8)?; + }, + I::Discard(idx) => { + s.write(13u8)?; + s.write(*idx)?; + }, + I::UnaryOp(op) => { + s.write(14u8)?; + s.write(*op as u8)?; + }, + I::BinaryOp(op) => { + s.write(15u8)?; + s.write(*op as u8)?; + }, + I::NewList(len) => { + s.write(16u8)?; + s.write(*len)?; + }, + I::NewTable(len) => { + s.write(17u8)?; + s.write(*len)?; + }, + I::NewMatrix(d, c) => { + s.write(18u8)?; + s.write(*d)?; + s.write(*c)?; + }, + I::Field(idx) => { + s.write(19u8)?; + s.write(*idx)?; + }, + I::StoreField(idx) => { + s.write(20u8)?; + s.write(*idx)?; + }, + I::Index(idx) => { + s.write(21u8)?; + s.write(*idx)?; + }, + I::StoreIndex(idx) => { + s.write(22u8)?; + s.write(*idx)?; + }, + I::Jump(ip) => { + s.write(23u8)?; + s.write(*ip)?; + }, + I::JumpTrue(ip) => { + s.write(24u8)?; + s.write(*ip)?; + }, + I::JumpFalse(ip) => { + s.write(25u8)?; + s.write(*ip)?; + }, + I::JumpNil(ip) => { + s.write(26u8)?; + s.write(*ip)?; + }, + I::IterCreate => { + s.write(27u8)?; + }, + I::IterNext => { + s.write(28u8)?; + }, + I::Try(ip) => { + s.write(29u8)?; + s.write(*ip)?; + }, + I::TryEnd => { + s.write(30u8)?; + }, + I::Call(arity) => { + s.write(31u8)?; + s.write(*arity)?; + }, + I::Return => { + s.write(32u8)?; + }, + }; + Ok(()) + } +} + +impl<T: Serialize> Serialize for Vec<T> { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + s.write(VarInt(self.len()))?; + for val in self { + val.serialize(s)?; + } + Ok(()) + } +} + +impl<T: Serialize + Deref> Serialize for Gc<T> { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + self.deref().serialize(s) + } +} + +impl<T: Serialize + Deref> Serialize for Rc<T> { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + self.deref().serialize(s) + } +} + +impl Serialize for Position { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + s.write(VarInt(self.row))?; + s.write(VarInt(self.col))?; + Ok(()) + } +} + +impl Serialize for Chunk { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + self.constants.serialize(s)?; + self.code.serialize(s)?; + self.pos.serialize(s)?; + Ok(()) + } +} + +impl Serialize for Value { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + use Value as V; + match self { + V::Nil => { + s.write(0u8)?; + }, + V::Bool(b) => { + s.write(1u8)?; + s.write(*b)?; + }, + V::Int(i) => { + s.write(2u8)?; + s.write(*i)?; + }, + V::Float(f) => { + s.write(3u8)?; + s.write(*f)?; + }, + V::Ratio(r) => { + s.write(4u8)?; + s.write(*r.numer())?; + s.write(*r.denom())?; + }, + V::Complex(c) => { + s.write(5u8)?; + s.write(c.re)?; + s.write(c.im)?; + }, + V::Regex(r) => { + s.write(6u8)?; + s.write(r.to_string())?; + }, + V::String(str) => { + s.write(7u8)?; + s.write(str.to_string())?; + }, + V::List(l) => { + s.write(8u8)?; + l.serialize(s)?; + }, + V::Matrix(m) => { + s.write(9u8)?; + s.write(m.domain)?; + s.write(m.codomain)?; + m.values.serialize(s)?; + }, + V::Table(t) => { + s.write(10u8)?; + s.write(VarInt(t.len()))?; + for (key, value) in t.entries() { + key.serialize(s)?; + value.serialize(s)?; + } + }, + V::Function(f) => { + s.write(11u8)?; + f.serialize(s)?; + }, + V::Range(r) => { + s.write(12u8)?; + s.write(r.0)?; + s.write(r.1)?; + s.write(r.2)?; + }, + V::Iter(f) => { + s.write(13u8)?; + f.serialize(s)?; + }, + V::File(_) => return Err(error!("cannot compile file")), + V::Exception(_) => return Err(error!("cannot compile exception")), + }; + Ok(()) + } +} + +impl Serialize for Function { + fn serialize<S: Serializer>(&self, s: &mut S) -> Result<()> { + s.write(self.name.to_string())?; + s.write(self.arity)?; + s.write(self.variadic)?; + use InnerFunction as F; + match &self.fun { + F::Compiled(c) => { + c.serialize(s)?; + }, + F::Native(_) => return Err(error!("cannot compile native function")), + }; + Ok(()) + } +} diff --git a/matrix-lang/src/chunk.rs b/matrix-lang/src/chunk.rs new file mode 100644 index 0000000..2fc3d9e --- /dev/null +++ b/matrix-lang/src/chunk.rs @@ -0,0 +1,128 @@ +use std::fmt::{Debug, Display}; +use crate::prelude::*; + +#[derive(Clone, Default)] +pub struct Chunk { + pub constants: Vec<Value>, + pub code: Vec<Instruction>, + pub pos: Vec<Position>, +} + +impl Chunk { + pub fn new() -> Self { + Self { + constants: Vec::new(), + code: Vec::new(), + pos: Vec::new(), + } + } +} + +#[derive(Clone, Debug)] +#[repr(align(4))] +pub enum Instruction { + NoOp, + + CreateLocal, + LoadLocal(u16), + StoreLocal(u16), + DiscardLocals(u16), + + LoadGlobal(u16), + StoreGlobal(u16), + + Const(u16), + Int(i16), + True, + False, + Nil, + + Dup, Discard(u16), + + UnaryOp(UnaryOp), + BinaryOp(BinaryOp), + + NewList(u16), + NewTable(u16), + NewMatrix(u16, u8), + + Field(u16), + StoreField(u16), + Index(u8), + StoreIndex(u8), + + Jump(u16), + JumpTrue(u16), + JumpFalse(u16), + JumpNil(u16), + + IterCreate, + IterNext, + + Try(u16), + TryEnd, + + Call(u8), + Return, +} + +impl Debug for Chunk { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "[Chunk {}]", self.code.len()) + } +} + +impl Display for Chunk { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + writeln!(f, "constants: ")?; + for (i, c) in self.constants.iter().enumerate() { + writeln!(f, " {i:04}: {c}")?; + } + writeln!(f, "code:")?; + for (i, ins) in self.code.iter().enumerate() { + writeln!(f, " {i:04}: {ins}")?; + } + Ok(()) + } +} + +impl Display for Instruction { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + use Instruction::*; + match self { + NoOp => write!(f, "noop"), + CreateLocal => write!(f, "create local"), + LoadLocal(idx) => write!(f, "load local \x1b[33m{idx}\x1b[0m"), + StoreLocal(idx) => write!(f, "store local \x1b[33m{idx}\x1b[0m"), + DiscardLocals(count) => write!(f, "discard locals \x1b[35m{count}\x1b[0m"), + LoadGlobal(name) => write!(f, "load global \x1b[36m{name}\x1b[0m"), + StoreGlobal(name) => write!(f, "store global \x1b[36m{name}\x1b[0m"), + Const(idx) => write!(f, "const \x1b[33m{idx}\x1b[0m"), + Int(idx) => write!(f, "push \x1b[34m{idx}\x1b[0m"), + True => write!(f, "push \x1b[34mtrue\x1b[0m"), + False => write!(f, "push \x1b[34mfalse\x1b[0m"), + Nil => write!(f, "push \x1b[34mnil\x1b[0m"), + Dup => write!(f, "duplicate"), + Discard(count) => write!(f, "discard \x1b[35m{count}\x1b[0m"), + UnaryOp(op) => write!(f, "unary \x1b[32m{op:?}\x1b[0m"), + BinaryOp(op) => write!(f, "binary \x1b[32m{op:?}\x1b[0m"), + NewList(len) => write!(f, "list \x1b[35m{len}\x1b[0m"), + NewTable(len) => write!(f, "table \x1b[35m{len}\x1b[0m"), + NewMatrix(len, codomain) => write!(f, "matrix \x1b[35m{}\x1b[0mx\x1b[35m{}\x1b[0m", *len / (*codomain as u16), codomain), + Index(idx) => write!(f, "index \x1b[33m{idx}\x1b[0m"), + StoreIndex(idx) => write!(f, "store_index \x1b[33m{idx}\x1b[0m"), + Jump(idx) => write!(f, "jump \x1b[33m{idx}\x1b[0m"), + JumpTrue(idx) => write!(f, "jumpt \x1b[33m{idx}\x1b[0m"), + JumpFalse(idx) => write!(f, "jumpf \x1b[33m{idx}\x1b[0m"), + JumpNil(idx) => write!(f, "jumpn \x1b[33m{idx}\x1b[0m"), + Call(arity) => write!(f, "call \x1b[35m{arity}\x1b[0m"), + Return => write!(f, "return"), + IterCreate => write!(f, "iter create"), + IterNext => write!(f, "iter next"), + Field(name_idx) => write!(f, "field \x1b[33m{name_idx}\x1b[0m"), + StoreField(name_idx) => write!(f, "store field \x1b[33m{name_idx}\x1b[0m"), + Try(idx) => write!(f, "try \x1b[33m{idx}\x1b[0m"), + TryEnd => write!(f, "try end"), + } + } +} diff --git a/matrix-lang/src/compiler.rs b/matrix-lang/src/compiler.rs new file mode 100644 index 0000000..95c6ccf --- /dev/null +++ b/matrix-lang/src/compiler.rs @@ -0,0 +1,628 @@ +use crate::prelude::*; + +use Instruction as I; +use Value as V; +use ExprData as E; + +pub type NamesTable = Rc<RefCell<Vec<Rc<str>>>>; +pub type GlobalsTable = Rc<RefCell<Vec<Global>>>; + +pub struct CompilerBuilder<'c> { + globals: GlobalsTable, + names: NamesTable, + repl: bool, + debug: bool, + name: Rc<str>, + parent: Option<&'c Compiler<'c>>, +} + +impl<'c> CompilerBuilder<'c> { + + pub fn new() -> Self { + Self { + globals: Rc::new(RefCell::new(Vec::new())), + repl: false, + debug: false, + name: "<root>".into(), + parent: None, + names: Rc::new(RefCell::new(Vec::new())) + } + } + + pub fn repl(mut self, repl: bool) -> Self { + self.repl = repl; + self + } + + pub fn debug(mut self, debug: bool) -> Self { + self.debug = debug; + self + } + + pub fn globals(mut self, globals: GlobalsTable) -> Self { + self.globals = globals; + self + } + + pub fn names(mut self, names: NamesTable) -> Self { + self.names = names; + self + } + + pub fn parent(mut self, parent: &'c Compiler) -> Self { + self.parent = Some(parent); + self + } + + pub fn name(mut self, name: Rc<str>) -> Self { + self.name = name; + self + } + + pub fn build(self) -> Compiler<'c> { + Compiler { + name: self.name, + names: self.names, + parent: self.parent, + globals: self.globals, + repl: self.repl, + debug: self.debug, + scopes: Vec::new(), + locals: Vec::new(), + chunk: Chunk::new(), + loop_top: Vec::new(), + loop_bot: Vec::new(), + root_is_block: false, + } + } +} + +pub struct Compiler<'c> { + name: Rc<str>, + parent: Option<&'c Compiler<'c>>, + + locals: Vec<Local>, + globals: GlobalsTable, + names: NamesTable, + + root_is_block: bool, + + scopes: Vec<usize>, + chunk: Chunk, + + loop_top: Vec<(usize, usize)>, + loop_bot: Vec<usize>, + + repl: bool, + debug: bool, +} + +#[derive(Clone)] +struct Local { + name: Rc<str>, + idx: usize, + scope: usize, + is_const: bool, +} + +#[derive(Clone)] +pub struct Global { + pub name: Rc<str>, + pub idx: usize, + pub is_const: bool, +} + +macro_rules! error { + ($($arg:tt)*) => { + exception!(COMPILE_EXCEPTION, $($arg)*) + }; +} + +impl<'c> Compiler<'c> { + + fn child(&'c self, name: Rc<str>) -> Self { + CompilerBuilder::new() + .name(name) + .debug(self.debug) + .globals(self.globals.clone()) + .names(self.names.clone()) + .repl(false) + .parent(self) + .build() + } + + fn begin_scope(&mut self) { + if self.root_is_block { + self.root_is_block = false; + } else { + self.scopes.push(self.locals.len()) + } + } + + fn collapse_scopes(&mut self, top_scope: usize) { + let mut cutoff = usize::MAX; + while self.scopes.len() > top_scope { + cutoff = self.scopes.pop().unwrap() + } + if cutoff < self.locals.len() { + self.emit(Instruction::DiscardLocals((self.locals.len() - cutoff) as u16), self.last_pos()); + self.locals.truncate(cutoff); + }; + } + + fn end_scope(&mut self) { + let Some(cutoff) = self.scopes.pop() else { + return; + }; + if cutoff < self.locals.len() { + self.emit(Instruction::DiscardLocals((self.locals.len() - cutoff) as u16), self.last_pos()); + self.locals.truncate(cutoff); + }; + } + + fn create_local(&mut self, name: Rc<str>, is_const: bool) -> Local { + let local = Local { name, idx: self.locals.len(), scope: self.scopes.len(), is_const }; + self.locals.push(local.clone()); + local + } + + fn create_global(&mut self, name: Rc<str>, is_const: bool) -> Global { + let global = Global { name, idx: self.globals.borrow().len(), is_const }; + self.globals.borrow_mut().push(global.clone()); + global + } + + fn create_local_checked(&mut self, name: Rc<str>, is_const: bool, pos: Position) -> Result<Local> { + if let Some(local) = self.find_local(&name) { + if local.scope == self.scopes.len() { + return Err(error!("redefined {name}").pos(pos)) + } + }; + Ok(self.create_local(name, is_const)) + } + + fn create_global_checked(&mut self, name: Rc<str>, is_const: bool, pos: Position) -> Result<Global> { + if let Some(_) = self.find_global(&name) { + return Err(error!("redefined {name}").pos(pos)) + } + Ok(self.create_global(name, is_const)) + } + + fn find_local(&self, name: &str) -> Option<Local> { + for local in self.locals.iter().rev() { + if local.name.as_ref() == name { + return Some(local.clone()) + } + } + None + } + + fn find_global(&self, name: &str) -> Option<Global> { + if let Some(parent) = self.parent { + return parent.find_global(name) + } + for global in self.globals.borrow().iter() { + if global.name.as_ref() == name { + return Some(global.clone()) + } + } + None + } + + fn get_name(&mut self, name: Rc<str>) -> usize { + // TODO: find name if already exists + let idx = self.names.borrow().len(); + self.names.borrow_mut().push(name); + idx + } + + fn emit_const(&mut self, val: Value, pos: Position) { + // TODO: find constant if already exists + self.chunk.constants.push(val); + let c = self.chunk.constants.len() - 1; + self.emit(Instruction::Const(c as u16), pos); + } + + fn can_make_globals(&self) -> bool { + self.repl && self.parent.is_none() && self.scopes.len() == 0 + } + + fn compile_value(&mut self, val: &Value, pos: Position) { + match val { + V::Nil => self.emit(I::Nil, pos), + V::Bool(b) => if *b { self.emit(I::True, pos) } else { self.emit(I::False, pos) }, + V::Int(i) => { + if let Ok(i) = i16::try_from(*i) { + self.emit(I::Int(i), pos); + } else { + self.emit_const(val.clone(), pos); + } + }, + _ => self.emit_const(val.clone(), pos), + } + } + + + + fn finish_loop(&mut self) { + self.loop_top.pop(); + while let Some(tmp) = self.loop_bot.pop() { + self.re_emit(I::Jump(self.cur()), tmp as usize); + } + } + + fn compile_expr(&mut self, expr: &Expr) -> Result<()> { + match &expr.data { + E::NoOp => self.emit(I::Nil, expr.pos), + E::If(cond, ifb, elseb) => { + self.compile_expr(cond)?; + let jmpidx = self.emit_temp(expr.pos); + self.compile_expr(ifb)?; + let jmpidx2 = self.emit_temp(expr.pos); + self.re_emit(I::JumpFalse(self.cur()), jmpidx); + if let Some(elseb) = elseb { + self.compile_expr(elseb)?; + } + self.re_emit(I::Jump(self.cur()), jmpidx2); + }, + E::Function(name, params, body, varadic) => { + let chunk = self.compile_function(name.clone(), params, body)?; + let arity = params.len() - if *varadic { 1 } else { 0 }; + let fun = Value::Function(Rc::new( + Function { + name: name.0.clone(), + arity, + fun: InnerFunction::Compiled(chunk.into()), + variadic: *varadic + } + )); + self.emit_const(fun, expr.pos); + self.emit(I::Dup, expr.pos); + if self.can_make_globals() { + let global = self.create_global_checked(name.0.clone(), false, name.1)?; + self.emit(I::StoreGlobal(global.idx as u16), expr.pos); + } else { + self.create_local_checked(name.0.clone(), false, name.1)?; + self.emit(I::CreateLocal, expr.pos); + } + }, + E::Lambda(params, body, varadic) => { + let name: AstName = (Rc::from("<lambda>"), expr.pos); + let chunk = self.compile_function(name.clone(), params, body)?; + let arity = params.len() - if *varadic { 1 } else { 0 }; + let fun = Value::Function(Rc::new( + Function { + name: name.0.clone(), + arity, + fun: InnerFunction::Compiled(chunk.into()), + variadic: *varadic + } + )); + self.emit_const(fun, expr.pos); + }, + E::Loop(expr) => { + let idx = self.cur(); + self.loop_top.push((idx as usize, self.scopes.len())); + self.compile_expr(expr)?; + self.emit(I::Discard(1), expr.pos); + self.emit(I::Jump(idx), expr.pos); + self.finish_loop(); + self.emit(I::Nil, expr.pos); + }, + E::Try(expr, err, catch) => { + let jmpidx = self.emit_temp(expr.pos); + self.compile_expr(expr)?; + self.emit(I::TryEnd, expr.pos); + let jmpidx2 = self.emit_temp(expr.pos); + self.re_emit(I::Try(self.cur()), jmpidx); + self.begin_scope(); + self.create_local(err.0.clone(), true); + self.emit(I::CreateLocal, err.1); + self.compile_expr(catch)?; + self.end_scope(); + self.re_emit(I::Jump(self.cur() as u16), jmpidx2); + }, + E::While(cond, expr) => { + let top = self.cur(); + self.compile_expr(cond)?; + let jmpidx = self.emit_temp(expr.pos); + self.loop_top.push((top as usize, self.scopes.len())); + self.compile_expr(expr)?; + self.emit(I::Discard(1), expr.pos); + self.emit(I::Jump(top), expr.pos); + self.re_emit(I::JumpFalse(self.cur()), jmpidx); + self.finish_loop(); + self.emit(I::Nil, expr.pos); + }, + E::DoWhile(expr, cond) => { + let top = self.cur(); + self.loop_top.push((top as usize, self.scopes.len())); + self.compile_expr(expr)?; + self.emit(I::Discard(1), expr.pos); + self.compile_expr(cond)?; + self.emit(I::JumpTrue(top), expr.pos); + self.finish_loop(); + self.emit(I::Nil, expr.pos); + }, + E::For(name, cond, expr) => { + self.compile_expr(cond)?; + self.emit(I::IterCreate, cond.pos); + let top = self.cur(); + self.emit(I::IterNext, cond.pos); + self.emit(I::Dup, expr.pos); + let jumpidx = self.emit_temp(expr.pos); + self.loop_top.push((top as usize, self.scopes.len())); + self.begin_scope(); + self.create_local(name.0.clone(), true); + self.emit(I::CreateLocal, name.1); + self.compile_expr(expr)?; + self.emit(I::Discard(1), expr.pos); + self.end_scope(); + self.emit(I::Jump(top), expr.pos); + self.re_emit(I::JumpNil(self.cur()), jumpidx); + self.finish_loop(); + self.emit(I::Discard(2), expr.pos); + self.emit(I::Nil, expr.pos); + } + E::Block(block) => { + if block.len() == 0 { + self.emit(I::Nil, expr.pos); + return Ok(()); + } + self.begin_scope(); + for (i, expr) in block.iter().enumerate() { + self.compile_expr(expr)?; + if i + 1 != block.len() { + self.emit(I::Discard(1), expr.pos); + } + } + self.end_scope(); + }, + E::Let(name, expr) => { + self.compile_expr(expr)?; + self.emit(I::Dup, expr.pos); + if self.can_make_globals() { + let global = self.create_global_checked(name.0.clone(), false, name.1)?; + self.emit(I::StoreGlobal(global.idx as u16), expr.pos); + } else { + self.create_local_checked(name.0.clone(), false, name.1)?; + self.emit(I::CreateLocal, expr.pos); + } + }, + E::Const(name, expr) => { + self.compile_expr(expr)?; + self.emit(I::Dup, expr.pos); + if self.can_make_globals() { + let global = self.create_global_checked(name.0.clone(), true, name.1)?; + self.emit(I::StoreGlobal(global.idx as u16), expr.pos); + } else { + self.create_local_checked(name.0.clone(), true, name.1)?; + self.emit(I::CreateLocal, expr.pos); + } + }, + E::Continue => { + let top = self.loop_top.pop(); + if let Some((top, scope)) = top { + self.collapse_scopes(scope); + self.emit(I::Jump(top as u16), expr.pos); + } else { + return Err(error!("invalid continue outside loop").pos(expr.pos)) + } + }, + E::Break => { + let top = self.loop_top.pop(); + if let Some((_, scope)) = top { + self.collapse_scopes(scope); + let tmpidx = self.emit_temp(expr.pos); + self.loop_bot.push(tmpidx); + } else { + return Err(error!("invalid break outside loop").pos(expr.pos)) + } + }, + E::Return(expr) => { + self.compile_expr(expr)?; + self.emit(I::Return, expr.pos); + }, + E::Literal(val) => self.compile_value(val, expr.pos), + E::Ident(name) => { + if name.as_ref() == "_" { + self.emit(I::Nil, expr.pos); + } else if let Some(local) = self.find_local(name) { + self.emit(I::LoadLocal(local.idx as u16), expr.pos); + } else if let Some(global) = self.find_global(name) { + self.emit(I::LoadGlobal(global.idx as u16), expr.pos); + } else { + return Err(error!("variable '{name}' is undefined").pos(expr.pos)) + }; + }, + E::Assign(lhs, rhs) => { + self.compile_expr(rhs)?; + self.emit(I::Dup, rhs.pos); + match &lhs.data { + E::Ident(name) if name.as_ref() != "_" => { + if let Some(local) = self.find_local(&name) { + if local.is_const { + return Err(error!("cannot assign to const '{name}'").pos(lhs.pos)) + } + self.emit(I::StoreLocal(local.idx as u16), lhs.pos); + } else if let Some(global) = self.find_global(&name) { + if global.is_const { + return Err(error!("cannot assign to const '{name}'").pos(lhs.pos)) + } + self.emit(I::StoreGlobal(global.idx as u16), lhs.pos); + } else if self.can_make_globals() { + let global = self.create_global_checked(name.clone(), false, lhs.pos)?; + self.emit(I::StoreGlobal(global.idx as u16), lhs.pos); + } else { + self.create_local_checked(name.clone(), false, lhs.pos)?; + self.emit(I::CreateLocal, lhs.pos); + } + }, + E::Index(expr, params) => { + self.compile_expr(expr)?; + for param in params { + self.compile_expr(param)?; + } + self.emit(I::StoreIndex(params.len() as u8), expr.pos); + }, + E::FieldAccess(expr, ident) => { + self.compile_expr(expr)?; + let name = self.get_name(ident.0.clone()); + self.emit(I::StoreField(name as u16), expr.pos); + } + _ => return Err(error!("assignment to {lhs} is not allowed").pos(lhs.pos)) + } + } + E::UnaryOp(expr, op) => { + self.compile_expr(expr)?; + self.emit(I::UnaryOp(*op), expr.pos); + }, + E::BinaryOp(lhs, rhs, op) => { + self.compile_expr(lhs)?; + self.compile_expr(rhs)?; + self.emit(I::BinaryOp(*op), lhs.pos); + }, + E::Index(expr, params) => { + self.compile_expr(expr)?; + for param in params { + self.compile_expr(param)?; + } + self.emit(I::Index(params.len() as u8), expr.pos) + }, + E::FnCall(fun, params) => { + for expr in params { + self.compile_expr(expr)?; + } + self.compile_expr(fun)?; + self.emit(I::Call(params.len() as u8), expr.pos); + }, + E::FieldAccess(expr, field) => { + self.compile_expr(expr)?; + let idx = self.get_name(field.0.clone()); + self.emit(I::Field(idx as u16), expr.pos) + } + E::List(list) => { + for expr in list { + self.compile_expr(expr)?; + } + self.emit(I::NewList(list.len() as u16), expr.pos); + }, + E::Matrix(mat) => { + for expr in &mat.2 { + self.compile_expr(expr)?; + } + self.emit(I::NewMatrix(mat.2.len() as u16, mat.0 as u8), expr.pos); + }, + E::Table(table) => { + for (key, value) in table { + self.compile_expr(key)?; + self.compile_expr(value)?; + } + self.emit(I::NewTable(table.len() as u16), expr.pos); + }, + E::And(lhs, rhs) => { + self.compile_expr(lhs)?; + self.emit(I::Dup, lhs.pos); + let jmpidx = self.emit_temp(lhs.pos); + self.compile_expr(rhs)?; + self.re_emit(I::JumpFalse(self.cur()), jmpidx); + }, + E::Or(lhs, rhs) => { + self.compile_expr(lhs)?; + self.emit(I::Dup, lhs.pos); + let jmpidx = self.emit_temp(lhs.pos); + self.compile_expr(rhs)?; + self.re_emit(I::JumpTrue(self.cur()), jmpidx); + }, + E::Pipeline(lhs, rhs) => { + self.compile_expr(lhs)?; + self.compile_expr(rhs)?; + self.emit(I::Call(1), expr.pos); + } + }; + Ok(()) + } + + fn compile_function(&mut self, name: AstName, params: &Vec<AstName>, body: &Box<Expr>) -> Result<Chunk> { + let mut compiler = self.child(name.0); + for (name, pos) in params { + compiler.create_local(name.clone(), false); + compiler.emit(I::CreateLocal, *pos); + } + compiler.compile_expr(body)?; + compiler.finish(name.1)?; + Ok(compiler.chunk) + } + + fn cur(&self) -> u16 { + self.chunk.code.len() as u16 + } + + fn emit_temp(&mut self, pos: Position) -> usize { + let idx = self.chunk.code.len(); + self.emit(Instruction::NoOp, pos); + idx + } + + fn emit(&mut self, ins: Instruction, pos: Position) { + //println!("{}: {ins}", self.name); + self.chunk.code.push(ins); + self.chunk.pos.push(pos); + } + + fn re_emit(&mut self, ins: Instruction, idx: usize) { + //println!("{} at {}: {ins}", self.name, &self.chunk.code[idx]); + self.chunk.code[idx] = ins; + } + + fn last_pos(&self) -> Position { + if let Some(pos) = self.chunk.pos.last() { + *pos + } else { + Position::default() + } + } + + fn finish(&mut self, pos: Position) -> Result<()> { + let ins = match self.chunk.code.last() { + Some(ins) => ins.clone(), + None => { + self.emit(I::Nil, pos); + self.emit(I::Return, pos); + if self.debug { + println!("{}\n{}", self.name, self.chunk); + } + return Ok(()) + } + }; + match ins { + I::Return => {}, + _ => { + self.emit(I::Return, pos); + } + }; + + if self.loop_bot.len() > 0 { + return Err(error!("invalid break outside loop").pos(pos)) + } + + if self.debug { + println!("{}\n{}", self.name, self.chunk); + } + Ok(()) + } + + pub fn compile( + &mut self, + body: &Expr, + ) -> Result<Rc<Function>> { + if let ExprData::Block(_) = &body.data { + self.root_is_block = true; + } + self.chunk = Chunk::new(); + self.compile_expr(body)?; + self.finish(self.last_pos())?; + let fun = Function { name: self.name.clone(), fun: InnerFunction::Compiled(self.chunk.clone().into()), arity: 0, variadic: false }; + Ok(Rc::new(fun)) + } +} diff --git a/matrix-lang/src/lex.rs b/matrix-lang/src/lex.rs new file mode 100644 index 0000000..b2487ad --- /dev/null +++ b/matrix-lang/src/lex.rs @@ -0,0 +1,777 @@ +use std::fmt::{Debug, Display}; +use crate::prelude::*; + +pub struct RegexToken { + regex: Regex +} + +impl Debug for RegexToken { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{:?}", self.regex) + } +} + +impl PartialEq for RegexToken { + fn eq(&self, other: &Self) -> bool { + self.regex.as_str().eq(other.regex.as_str()) + } +} + +impl From<Regex> for RegexToken { + fn from(regex: Regex) -> Self { + Self { regex } + } +} + +impl From<RegexToken> for Regex { + fn from(value: RegexToken) -> Self { + value.regex + } +} + +#[derive(Debug, Clone, PartialEq, Eq, Copy)] +pub struct Position { + pub row: usize, + pub col: usize, +} + +impl Default for Position { + fn default() -> Self { + Self { row: 1, col: 1 } + } +} + +impl Display for Position { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}:{}", self.row, self.col) + } +} + +impl Display for TokenData { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{self:?}") + } +} + +impl Display for Token { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}", self.data) + } +} + +#[derive(Debug, PartialEq)] +pub enum TokenData { + //syntax + LeftParen, + RightParen, + LeftBrack, + RightBrack, + LeftBrace, + RightBrace, + Assign, + Access, + SemiColon, + Arrow, + ThinArrow, + Comma, + Range, + RangeEq, + Colon, + Backslash, + Varadic, + Pipe, + + // math + Regex(RegexToken), + Int(i64), + Float(f64), + Complex(f64), + String(Rc<str>), + Ident(Rc<str>), + + // equality + Equal, + NotEqual, + GreaterEqual, + LessEqual, + GreaterThan, + LessThan, + + And, + Or, + Not, + + BitwiseShiftLeft, + BitwiseShiftRight, + BitwiseAnd, + BitwiseOr, + BitwiseXor, + + Add, + Subtract, + Multiply, + Divide, + Modulo, + Power, + + AssignAnd, + AssignOr, + + AssignBitwiseShiftLeft, + AssignBitwiseShiftRight, + AssignBitwiseAnd, + AssignBitwiseOr, + AssignBitwiseXor, + + AssignAdd, + AssignSubtract, + AssignMultiply, + AssignDivide, + AssignModulo, + AssignPower, + + // keywords + If, + Else, + While, + Let, + Const, + Function, + True, + False, + Nil, + Continue, + Break, + Do, + Loop, + Return, + For, + In, + Try, + Catch, + + // eof + Eof, +} + +#[derive(Debug, PartialEq)] +pub struct Token { + pub data: TokenData, + pub pos: Position, + pub str: String, + pub bidx: usize, + pub blen: usize, +} + +pub struct Lexer { + pub index: usize, + len: usize, + data: Vec<char>, + pos: Position, + byte_len: usize, +} + +trait IsIdent { + fn is_initial_ident(&self) -> bool; + fn is_ident(&self) -> bool; +} + +impl IsIdent for char { + fn is_initial_ident(&self) -> bool { + self.is_alphabetic() || *self == '_' + } + fn is_ident(&self) -> bool { + self.is_alphanumeric() || *self == '_' + } +} + +impl<T: Into<String>> From<T> for Lexer { + fn from(value: T) -> Self { + Self::new(value) + } +} + +macro_rules! error { + ($($arg:tt)*) => { + exception!(PARSE_EXCEPTION, $($arg)*) + }; +} + +impl Lexer { + pub fn new<T: Into<String>>(input: T) -> Self { + let data: Vec<char> = input.into().chars().collect(); + Self { + index: 0, + len: data.len(), + data, + pos: Position::default(), + byte_len: 0 + } + } + + fn peek(&self) -> char { + if self.index >= self.len { + return '\0'; + } + self.data[self.index] + } + + fn next(&mut self) -> char { + let c = self.peek(); + self.index += 1; + self.byte_len += c.len_utf8(); + + self.pos.col += 1; + if c == '\n' { + self.pos.col = 1; + self.pos.row += 1; + } + + c + } + + fn next_not_eof(&mut self) -> Result<char> { + let c = self.next(); + if c == '\0' { + return Err(error!("unexpected end of file")) + } + Ok(c) + } + + fn next_expect(&mut self, expected: char) -> Result<char> { + let c = self.next(); + if c != expected { + return Err(error!("expected character '{c}'")) + } + Ok(c) + } + + fn skip_whitespace(&mut self, ignore_newlines: bool) { + while self.peek().is_whitespace() && (ignore_newlines || self.peek() != '\n') { + self.next(); + } + } + + fn lex_string(&mut self, delimit: char) -> Result<Rc<str>> { + + let mut buf = String::new(); + + loop { + let c = self.next_not_eof()?; + + if c == delimit { + break; + } + + if c != '\\' { + buf.push(c); + continue; + } + + let next = self.next_not_eof()?; + match next { + '\'' | '\"' | '\\' => buf.push(c), + '0' => buf.push('\0'), + 'a' => buf.push('\x07'), + 'b' => buf.push('\x08'), + 't' => buf.push('\t'), + 'n' => buf.push('\n'), + 'v' => buf.push('\x0b'), + 'f' => buf.push('\x0c'), + 'r' => buf.push('\r'), + 'e' => buf.push('\x1b'), + 'x' => { + let n1 = self.next_not_eof()?; + let n2 = self.next_not_eof()?; + buf.push(char::from_u32( + n1.to_digit(16).ok_or(error!("invalid digit '{n1}'"))? * 16 + + n2.to_digit(16).ok_or(error!("invalid digit '{n2}'"))? + ).unwrap()); + }, + 'u' => { + self.next_expect('{')?; + let mut n = 0u32; + loop { + let c = self.next_not_eof()?; + if c == '}' { break } + if n >= 0x1000_0000_u32 { + return Err(error!("invalid utf8 codepoint '{n}'")) + } + n = n * 16 + c.to_digit(16).ok_or(error!("invalid digit '{c}'"))?; + } + let ch = char::from_u32(n).ok_or(error!("invalid codepoint '{n}'"))?; + buf.push(ch); + + }, + _ => return Err(error!("invalid string escape '\\{next}'")) + } + } + + Ok(buf.into()) + } + + fn lex_ident(&mut self, initial: char) -> Result<TokenData> { + use TokenData as T; + + let mut buf = std::string::String::new(); + + if !initial.is_initial_ident() { + return Err(error!("unexpected character '{initial}'")) + } + + buf.push(initial); + + loop { + if self.peek().is_ident() { + buf.push(self.next()); + } else { + break; + } + } + + Ok(match buf.as_str() { + "if" => T::If, + "else" => T::Else, + "while" => T::While, + "let" => T::Let, + "const" => T::Const, + "fn" | "function" => T::Function, + "true" => T::True, + "false" => T::False, + "nil" => T::Nil, + "continue" => T::Continue, + "break" => T::Break, + "do" => T::Do, + "loop" => T::Loop, + "and" => T::And, + "or" => T::Or, + "not" => T::Not, + "return" => T::Return, + "for" => T::For, + "in" => T::In, + "try" => T::Try, + "catch" => T::Catch, + _ => T::Ident(buf.into()) + }) + } + + fn lex_radix(&mut self, radix: i64, radix_char: char) -> Result<TokenData> { + use TokenData as T; + + let mut n = 0i64; + let mut char_found = false; + + loop { + if let Some(i) = self.peek().to_digit(radix as u32) { + self.next(); + n = n * radix + (i as i64); + char_found = true; + } else if self.peek().is_ident() { + return Err(error!("invalid digit '{}'", self.peek())) + } else { + break; + } + } + + if char_found { + Ok(T::Int(n)) + } else { + Err(error!("invalid number radix specifier '0{radix_char}'")) + } + } + + fn lex_number(&mut self, initial: char) -> Result<TokenData> { + if initial == '0' { + match self.peek() { + 'x' => { + self.next(); + return self.lex_radix(16, 'x') + } + 'o' => { + self.next(); + return self.lex_radix(8, 'o'); + } + _ => () + } + } + + let mut buf = String::new(); + buf.push(initial); + + let mut pos = self.pos; + let mut idx = self.index; + let mut bidx = self.byte_len; + + if initial != '.' { + loop { + if !self.peek().is_ascii_digit() { break; } + buf.push(self.next()); + } + + if self.peek() == '.' { + pos = self.pos; + idx = self.index; + bidx = self.byte_len; + buf.push(self.next()); + } + } + + let last: char = buf.chars().last().unwrap(); + let is_range = initial != '.' && last == '.' && self.peek() == '.'; + + if is_range { + self.pos = pos; + self.index = idx; + self.byte_len = bidx; + buf.pop(); + } else { + loop { + if !self.peek().is_ascii_digit() { break; } + buf.push(self.next()); + } + + if self.peek() == 'e' || self.peek() == 'E' { + buf.push(self.next()); + if self.peek() == '+' || self.peek() == '-' { + buf.push(self.next()); + } + + loop { + if !self.peek().is_ascii_digit() { break; } + buf.push(self.next()); + } + } + } + + let complex = self.peek() == 'i'; + if complex { + self.next(); + } + + if self.peek().is_ident() { + return Err(error!("unexpected character '{}'", self.peek())) + } + + if let Ok(int) = buf.parse::<i64>() { + use TokenData as T; + if complex { + return Ok(T::Complex(int as f64)) + } + return Ok(T::Int(int)) + } + + if let Ok(float) = buf.parse::<f64>() { + use TokenData as T; + if complex { + return Ok(T::Complex(float)) + } + return Ok(T::Float(float)) + } + + Err(error!("invalid number '{buf}'")) + } + + fn read_token(&mut self, ignore_newlines: bool) -> Result<Token> { + use TokenData as T; + + self.skip_whitespace(ignore_newlines); + + let str_start = self.index; + let byte_start = self.byte_len; + + let pos = self.pos; + let char = self.next(); + let next = self.peek(); + + if char == '\0' { + let data = if ignore_newlines { T::Eof } else { T::SemiColon }; + return Ok(Token { + data, + pos, + str: String::new(), + bidx: byte_start, + blen: 0, + }) + } + + let data = match char { + '\n' => T::SemiColon, + '(' => T::LeftParen, + ')' => T::RightParen, + '[' => T::LeftBrack, + ']' => T::RightBrack, + '{' => T::LeftBrace, + '}' => T::RightBrace, + ':' => T::Colon, + '\\' => T::Backslash, + ';' => T::SemiColon, + '+' => { + match next { + '=' => { + self.next(); + T::AssignAdd + } + _ => T::Add + } + }, + '/' => { + match next { + '=' => { + self.next(); + T::AssignDivide + } + _ => T::Divide + } + }, + '%' => { + match next { + '=' => { + self.next(); + T::AssignModulo + } + _ => T::Modulo + } + }, + ',' => T::Comma, + '*' => { + match next { + '*' => { + self.next(); + match self.peek() { + '=' => { + self.next(); + T::AssignPower + }, + _ => T::Power + } + }, + '=' => { + self.next(); + T::AssignMultiply + } + _ => T::Multiply + } + }, + '!' => { + match next { + '=' => { + self.next(); + T::NotEqual + } + _ => T::Not + } + } + '&' => { + match next { + '&' => { + self.next(); + match self.peek() { + '=' => { + self.next(); + T::AssignAnd + }, + _ => T::And + } + }, + '=' => { + self.next(); + T::AssignBitwiseAnd + }, + _ => T::BitwiseAnd + } + }, + '|' => { + match next { + '|' => { + self.next(); + match self.peek() { + '=' => { + self.next(); + T::AssignOr + }, + _ => T::Or + } + }, + '=' => { + self.next(); + T::AssignBitwiseOr + }, + '>' => { + self.next(); + T::Pipe + }, + _ => T::BitwiseOr + } + }, + '-' => { + match next { + '>' => { + self.next(); + T::ThinArrow + }, + '=' => { + self.next(); + T::AssignSubtract + }, + _ => T::Subtract + } + }, + '=' => { + match next { + '>' => { + self.next(); + T::Arrow + } + '=' => { + self.next(); + T::Equal + } + _ => T::Assign + } + }, + '>' => { + match next { + '>' => { + self.next(); + match self.peek() { + '=' => { + self.next(); + T::AssignBitwiseShiftRight + }, + _ => T::BitwiseShiftRight + } + } + '=' => { + self.next(); + T::GreaterEqual + } + _ => T::GreaterThan + } + }, + '<' => { + match next { + '<' => { + self.next(); + match self.peek() { + '=' => { + self.next(); + T::AssignBitwiseShiftLeft + }, + _ => T::BitwiseShiftLeft + } + } + '=' => { + self.next(); + T::LessEqual + } + _ => T::LessThan + } + }, + '^' => { + match next { + '=' => { + self.next(); + T::AssignBitwiseXor + }, + _ => T::BitwiseXor + } + } + '\'' | '\"' => T::String(self.lex_string(char)?), + 'r' => { + match next { + '\'' | '\"' => { + self.next(); + T::Regex(regex::Regex::new(&self.lex_string(next)?) + .map(|e| e.into()) + .map_err(|e| error!("invalid regex: '{e}'"))?) + } + _ => { + self.lex_ident(char)? + } + } + }, + '.' => { + if next == '.' { + self.next(); + match self.peek() { + '.' => { + self.next(); + T::Varadic + }, + '=' => { + self.next(); + T::RangeEq + }, + _ => T::Range + } + } else if next.is_digit(10) { + self.lex_number(char)? + } else { + T::Access + } + }, + _ => { + if char.is_digit(10) { + self.lex_number(char)? + } else { + self.lex_ident(char)? + } + }, + }; + + let str_end = self.index; + let byte_end = self.byte_len; + let str = self.data[str_start..str_end].to_owned().into_iter().collect(); + Ok(Token { + data, + pos, + str, + bidx: byte_start, + blen: byte_end - byte_start + }) + } + + pub fn next_token(&mut self) -> Result<Token> { + let pos = self.pos; + match self.read_token(true) { + Ok(token) => Ok(token), + Err(e) => Err(e.pos(pos)), + } + } + + pub fn next_token_nl(&mut self) -> Result<Token> { + let pos = self.pos; + match self.read_token(false) { + Ok(token) => Ok(token), + Err(e) => Err(e.pos(pos)), + } + } + + pub fn peek_token(&mut self) -> Result<Token> { + let idx = self.index; + let pos = self.pos; + let bidx = self.byte_len; + let token = self.read_token(true); + self.index = idx; + self.pos = pos; + self.byte_len = bidx; + match token { + Ok(token) => Ok(token), + Err(e) => Err(e.pos(pos)), + } + } + + pub fn peek_token_nl(&mut self) -> Result<Token> { + let idx = self.index; + let pos = self.pos; + let bidx = self.byte_len; + let token = self.read_token(false); + self.index = idx; + self.pos = pos; + self.byte_len = bidx; + match token { + Ok(token) => Ok(token), + Err(e) => Err(e.pos(pos)), + } + } +} diff --git a/matrix-lang/src/lib.rs b/matrix-lang/src/lib.rs new file mode 100644 index 0000000..1452a09 --- /dev/null +++ b/matrix-lang/src/lib.rs @@ -0,0 +1,42 @@ +mod compiler; +mod value; +mod lex; +mod vm; +mod parse; +mod chunk; +mod ast; +mod binary; + +pub mod prelude; + +#[macro_export] +macro_rules! iter { + ($fn:expr) => { + $crate::prelude::Value::Iter( + ::std::rc::Rc::new( + $crate::prelude::Function { + name: ::std::rc::Rc::from("<iterator>"), + arity: 0, + variadic: false, + fun: $crate::prelude::InnerFunction::Native( + ::std::rc::Rc::new($fn + ))})) + }; +} + +#[macro_export] +macro_rules! native { + ($name:expr, $arity:expr, $varadic:expr, $fn:expr) => { + $crate::prelude::Value::Function( + ::std::rc::Rc::new( $crate::prelude::Function { + name: std::rc::Rc::from($name), + arity: $arity, + variadic: $varadic, + fun: $crate::prelude::InnerFunction::Native( + ::std::rc::Rc::new($fn) + ) + }) + ) + } +} + diff --git a/matrix-lang/src/parse.rs b/matrix-lang/src/parse.rs new file mode 100644 index 0000000..3a4c5f2 --- /dev/null +++ b/matrix-lang/src/parse.rs @@ -0,0 +1,757 @@ +use crate::prelude::*; + +use Value as V; +use ExprData as E; +use TokenData as T; + +pub struct ParserBuilder { + optimize: bool +} + +impl ParserBuilder { + pub fn new() -> Self { + Self { optimize: true } + } + + pub fn optimize(mut self, optimize: bool) -> Self { + self.optimize = optimize; + self + } + + pub fn build(self) -> Parser { + Parser { + lexer: Lexer::new(""), + optimize: self.optimize + } + } +} + +pub struct Parser { + lexer: Lexer, + optimize: bool +} + +macro_rules! expr_parser { + ($parser:ident, $pattern:pat, $fn:ident) => {{ + let mut expr = $parser.$fn()?; + let pos = expr.pos; + loop { + let tok = $parser.lexer.peek_token_nl()?; + match tok.data { + $pattern => { + $parser.lexer.next_token_nl()?; + let temp = $parser.$fn()?; + expr = (E::BinaryOp(Box::new(expr), Box::new(temp), BinaryOp::from(tok.data)), pos).into() + } + _ => break + } + } + Ok(expr) + }}; +} + +macro_rules! expr_parser_reverse { + ($parser:ident, $pattern:pat, $fn:ident, $cur:ident) => {{ + let expr = $parser.$fn()?; + let tok = $parser.lexer.peek_token_nl()?; + let pos = tok.pos; + Ok(match tok.data { + $pattern => { + $parser.lexer.next_token_nl()?; + (E::BinaryOp(Box::new(expr), Box::new($parser.$cur()?), BinaryOp::from(tok.data)), pos).into() + } + _ => expr + }) + }}; +} + +macro_rules! error { + ($($arg:tt)*) => { + exception!(PARSE_EXCEPTION, $($arg)*) + }; +} + +impl Parser { + + fn force_token(&mut self, tok: TokenData) -> Result<TokenData> { + let next = self.lexer.next_token()?; + if next.data != tok { + Err(error!("expected token '{tok}'").pos(next.pos)) + } else { + Ok(tok) + } + } + + fn force_token_nl(&mut self, tok: TokenData) -> Result<TokenData> { + let next = self.lexer.next_token_nl()?; + if next.data != tok { + Err(error!("expected token '{tok}'").pos(next.pos)) + } else { + Ok(tok) + } + } + + fn parse_fn_call(&mut self) -> Result<Vec<Expr>> { + self.force_token(T::LeftParen)?; + let mut params = Vec::new(); + loop { + let expr = match self.lexer.peek_token()?.data { + T::RightParen => { + self.lexer.next_token()?; + break + }, + _ => self.parse_expr()? + }; + params.push(expr); + let next = self.lexer.next_token()?; + match next.data { + T::Comma => continue, + T::RightParen => break, + _ => return Err(error!("unexpected token '{next}'").pos(next.pos)) + }; + } + Ok(params) + } + + fn parse_index(&mut self) -> Result<Vec<Expr>> { + self.force_token(T::LeftBrack)?; + let mut indicies = Vec::new(); + loop { + let expr = match self.lexer.peek_token()?.data { + T::RightBrack => { + self.lexer.next_token()?; + break + }, + _ => self.parse_expr()? + }; + indicies.push(expr); + let next = self.lexer.next_token()?; + match next.data { + T::SemiColon => continue, + T::RightBrack => break, + _ => return Err(error!("unexpected token '{next}'").pos(next.pos)) + }; + } + Ok(indicies) + } + + fn parse_matrix_part(&mut self) -> Result<Vec<Expr>> { + let mut part = Vec::new(); + loop { + let expr = match self.lexer.peek_token()?.data { + T::SemiColon => break, + T::RightBrack => break, + _ => self.parse_expr()? + }; + part.push(expr); + match self.lexer.peek_token()?.data { + T::Comma => { + self.lexer.next_token()?; + }, + _ => {}, + }; + } + Ok(part) + } + + fn parse_matrix(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::LeftBrack)?; + let mut parts = Vec::new(); + loop { + let part = self.parse_matrix_part()?; + parts.push(part); + let next = self.lexer.next_token()?; + match next.data { + T::SemiColon => continue, + T::RightBrack => break, + _ => return Err(error!("unexpected token '{next}'").pos(next.pos)) + }; + } + if parts.len() == 1 { + Ok((E::List(parts.pop().unwrap()), pos).into()) + } else { + let codomain = parts.len(); + let domain = parts[0].len(); + for part in parts.iter() { + if part.len() != domain { + return Err(error!("matrix row domains do not match: {} != {}", domain, part.len()).pos(pos)) + } + } + let mut data = Vec::new(); + parts.reverse(); + while let Some(part) = parts.pop() { + data.extend(part); + } + Ok((E::Matrix((domain, codomain, data)), pos).into()) + } + } + + fn parse_table_key(&mut self) -> Result<Expr> { + let tok = self.lexer.next_token()?; + Ok(match tok.data { + T::LeftBrack => { + let expr = self.parse_expr()?; + self.force_token(T::RightBrack)?; + expr + }, + T::Ident(ident) => (E::Literal(V::String(ident.to_string().into())), tok.pos).into(), + T::String(string) => (E::Literal(V::String(string.to_string().into())), tok.pos).into(), + t => return Err(error!("unexpected token '{t}'").pos(tok.pos)) + }) + } + + fn parse_table(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Colon)?; + self.force_token(T::LeftBrace)?; + let mut table = Vec::new(); + if self.lexer.peek_token()?.data == T::RightBrace { + self.lexer.next_token()?; + return Ok((E::Table(table), pos).into()) + } + loop { + let key = self.parse_table_key()?; + self.force_token(T::Assign)?; + let value = self.parse_expr()?; + table.push((key, value)); + let next = self.lexer.next_token()?; + match next.data { + T::Comma => continue, + T::RightBrace => break, + _ => return Err(error!("unexpected token '{next}'").pos(next.pos)) + } + } + Ok((E::Table(table), pos).into()) + } + + fn parse_paren(&mut self) -> Result<Expr> { + self.force_token(T::LeftParen)?; + let expr = self.parse_expr()?; + self.force_token(T::RightParen)?; + Ok(expr) + } + + fn parse_params(&mut self) -> Result<(Vec<(Rc<str>, Position)>, bool)> { + let tok = self.lexer.next_token()?; + match tok.data { + T::Ident(ident) => { + let params = vec![(ident, tok.pos)]; + if self.lexer.peek_token()?.data == T::Varadic { + self.lexer.next_token()?; + return Ok((params, true)) + } else { + return Ok((params, false)) + } + } + T::LeftParen => (), + t => return Err(error!("unexpected token '{t}'").pos(tok.pos)) + } + + let mut params = Vec::new(); + let mut varadic = false; + + if self.lexer.peek_token()?.data == T::RightParen { + return Ok((params, varadic)); + } + + loop { + let ident = self.parse_ident()?; + params.push(ident); + let next = self.lexer.next_token()?; + match next.data { + T::Varadic => { + varadic = true; + self.force_token(T::RightParen)?; + break; + } + T::Comma => continue, + T::RightParen => break, + _ => return Err(error!("unexpected token '{next}'").pos(next.pos)) + } + } + + Ok((params, varadic)) + } + + fn parse_ident(&mut self) -> Result<AstName> { + let next = self.lexer.next_token()?; + if let T::Ident(ident) = next.data { + Ok((ident, next.pos)) + } else { + Err(error!("unexpected token '{next}'").pos(next.pos)) + } + } + + fn parse_wrapped_ident(&mut self) -> Result<AstName> { + if self.lexer.peek_token()?.data == T::LeftParen { + self.lexer.next_token()?; + let ident = self.parse_ident()?; + self.force_token(T::RightParen)?; + Ok(ident) + } else { + self.parse_ident() + } + } + + fn parse_ident_nl(&mut self) -> Result<AstName> { + let next = self.lexer.next_token_nl()?; + if let T::Ident(ident) = next.data { + Ok((ident, next.pos)) + } else { + Err(error!("unexpected token '{next}'").pos(next.pos)) + } + } + + fn parse_function(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Function)?; + let ident = self.parse_ident()?; + let (params, varadic) = match self.lexer.peek_token()?.data { + T::LeftBrace => (vec![], false), + _ => self.parse_params()?, + }; + let expr = self.parse_expr()?; + Ok((E::Function(ident, params, Box::new(expr), varadic), pos).into()) + } + + fn parse_lambda(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Backslash)?; + let (params, varadic) = match self.lexer.peek_token()?.data { + T::Arrow => (vec![], false), + _ => self.parse_params()?, + }; + self.force_token(T::Arrow)?; + let expr = self.parse_expr()?; + Ok((E::Lambda(params, Box::new(expr), varadic), pos).into()) + } + + fn parse_do_while(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Do)?; + let expr = Box::new(self.parse_expr()?); + self.force_token(T::While)?; + let cond = Box::new(self.parse_expr()?); + Ok((E::DoWhile(expr, cond), pos).into()) + } + + fn parse_while(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::While)?; + let cond = Box::new(self.parse_expr()?); + let expr = Box::new(self.parse_expr()?); + Ok((E::While(cond, expr), pos).into()) + } + + fn parse_loop(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Loop)?; + let expr = self.parse_expr()?; + Ok((E::Loop(Box::new(expr)), pos).into()) + } + + fn parse_for(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::For)?; + let name = self.parse_ident()?; + self.force_token(T::In)?; + let cond = Box::new(self.parse_expr()?); + let expr = Box::new(self.parse_expr()?); + Ok((E::For(name, cond, expr), pos).into()) + } + + fn parse_if(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::If)?; + let cond = Box::new(self.parse_expr()?); + let expr = Box::new(self.parse_expr()?); + + if self.lexer.peek_token()?.data != T::Else { + return Ok((E::If(cond, expr, None), pos).into()) + } + self.lexer.next_token()?; + + if self.lexer.peek_token()?.data == T::If { + Ok((E::If(cond, expr, Some(Box::new(self.parse_if()?))), pos).into()) + } else { + Ok((E::If(cond, expr, Some(Box::new(self.parse_expr()?))), pos).into()) + } + } + + fn parse_let(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Let)?; + let ident = self.parse_ident_nl()?; + if self.lexer.peek_token_nl()?.data == T::Assign { + self.force_token_nl(T::Assign)?; + Ok((E::Let(ident, Box::new(self.parse_expr()?)), pos).into()) + } else { + Ok((E::Let(ident, Box::new((E::Literal(V::Nil), pos).into())), pos).into()) + } + } + + fn parse_const(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Const)?; + let ident = self.parse_ident_nl()?; + self.force_token(T::Assign)?; + let expr = self.parse_expr()?; + Ok((E::Const(ident, Box::new(expr)), pos).into()) + } + + fn parse_return(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Return)?; + Ok((E::Return(Box::new(self.parse_expr()?)), pos).into()) + } + + fn parse_block(&mut self) -> Result<Expr> { + let mut block = Vec::new(); + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::LeftBrace)?; + loop { + let expr = match self.lexer.peek_token()?.data { + T::RightBrace => { + self.lexer.next_token()?; + break + }, + T::SemiColon => { + self.lexer.next_token()?; + continue; + } + _ => self.parse_expr()? + }; + block.push(expr); + let next = self.lexer.next_token_nl()?; + match next.data { + T::SemiColon => continue, + T::RightBrace => break, + _ => return Err(error!("expected a semicolon").pos(next.pos)) + } + } + Ok((E::Block(block), pos).into()) + } + + fn parse_try(&mut self) -> Result<Expr> { + let pos = self.lexer.peek_token()?.pos; + self.force_token(T::Try)?; + let expr = self.parse_expr()?; + self.force_token(T::Catch)?; + let ident = self.parse_wrapped_ident()?; + let catch = self.parse_expr()?; + Ok((E::Try(Box::new(expr), ident, Box::new(catch)), pos).into()) + } + + fn parse_value(&mut self) -> Result<Expr> { + let tok = self.lexer.next_token()?; + let data = match tok.data { + T::Nil => E::Literal(V::Nil), + T::Int(i) => E::Literal(V::Int(i)), + T::Float(f) => E::Literal(V::Float(f)), + T::Complex(c) => E::Literal(V::Complex(Complex64::new(0.0, c))), + T::Regex(r) => E::Literal(V::Regex(Rc::new(r.into()))), + T::String(s) => E::Literal(V::String(s.to_string().into())), + T::True => E::Literal(V::Bool(true)), + T::False => E::Literal(V::Bool(false)), + T::Ident(ident) => E::Ident(ident), + t => return Err(error!("unexpected token '{t}'").pos(tok.pos)) + }; + Ok((data, tok.pos).into()) + } + + fn parse_term(&mut self) -> Result<Expr> { + use T::*; + match self.lexer.peek_token()?.data { + Function => self.parse_function(), + Backslash => self.parse_lambda(), + Do => self.parse_do_while(), + While => self.parse_while(), + For => self.parse_for(), + Let => self.parse_let(), + Const => self.parse_const(), + LeftBrace => self.parse_block(), + Return => self.parse_return(), + If => self.parse_if(), + Loop => self.parse_loop(), + Try => self.parse_try(), + Break => { + let next = self.lexer.next_token()?; + Ok((E::Break, next.pos).into()) + }, + Continue => { + let next = self.lexer.next_token()?; + Ok((E::Continue, next.pos).into()) + }, + LeftBrack => self.parse_matrix(), + Colon => self.parse_table(), + LeftParen => self.parse_paren(), + _ => self.parse_value(), + } + } + + fn parse_expr_expr_access(&mut self) -> Result<Expr> { + let mut expr = self.parse_term()?; + let pos = expr.pos; + loop { + let tok = self.lexer.peek_token()?; + match tok.data { + T::Access => { + self.force_token(T::Access)?; + let temp = self.parse_ident()?; + expr = (E::FieldAccess(Box::new(expr), temp), pos).into(); + }, + _ => break + } + } + Ok(expr) + } + + fn parse_expr_call(&mut self) -> Result<Expr> { + let mut expr = self.parse_expr_expr_access()?; + let pos = expr.pos; + loop { + let tok = self.lexer.peek_token()?; + match tok.data { + T::LeftBrack => { + let index = self.parse_index()?; + expr = (E::Index(Box::new(expr), index), pos).into(); + }, + T::LeftParen => { + let params = self.parse_fn_call()?; + expr = (E::FnCall(Box::new(expr), params), pos).into(); + } + _ => break + } + } + Ok(expr) + } + + fn parse_expr_unary(&mut self) -> Result<Expr> { + let tok = self.lexer.peek_token_nl()?; + Ok(match tok.data { + T::Not => { + self.lexer.next_token()?; + (E::UnaryOp(Box::new(self.parse_expr_unary()?), UnaryOp::Not), tok.pos).into() + } + T::Subtract => { + self.lexer.next_token()?; + (E::UnaryOp(Box::new(self.parse_expr_unary()?), UnaryOp::Negate), tok.pos).into() + } + _ => self.parse_expr_call()? + }) + } + + fn parse_expr_pow(&mut self) -> Result<Expr> { + expr_parser_reverse!( + self, + T::Power, + parse_expr_unary, + parse_expr_pow + ) + } + + fn parse_expr_mult(&mut self) -> Result<Expr> { + expr_parser!(self, T::Multiply | T::Divide | T::Modulo, parse_expr_pow) + } + + fn parse_expr_add(&mut self) -> Result<Expr> { + expr_parser!(self, T::Add | T::Subtract, parse_expr_mult) + } + + fn parse_expr_shift(&mut self) -> Result<Expr> { + expr_parser!( + self, + T::BitwiseShiftLeft | T::BitwiseShiftRight, + parse_expr_add + ) + } + + fn parse_expr_bit_and(&mut self) -> Result<Expr> { + expr_parser!(self, T::BitwiseAnd, parse_expr_shift) + } + + fn parse_expr_bit_or(&mut self) -> Result<Expr> { + expr_parser!(self, T::BitwiseOr, parse_expr_bit_and) + } + + fn parse_expr_compare(&mut self) -> Result<Expr> { + expr_parser!( + self, + T::Equal | T::NotEqual | + T::LessThan | T::GreaterThan | + T::LessEqual | T::GreaterEqual, + parse_expr_bit_or + ) + } + + fn parse_expr_and(&mut self) -> Result<Expr> { + let mut expr = self.parse_expr_compare()?; + let pos = expr.pos; + loop { + let tok = self.lexer.peek_token()?; + match tok.data { + T::And => { + self.force_token(T::And)?; + let temp = self.parse_expr_compare()?; + expr = (E::And(Box::new(expr), Box::new(temp)), pos).into(); + }, + _ => break + } + } + Ok(expr) + } + + fn parse_expr_or(&mut self) -> Result<Expr> { + let mut expr = self.parse_expr_and()?; + let pos = expr.pos; + loop { + let tok = self.lexer.peek_token()?; + match tok.data { + T::Or => { + self.force_token(T::Or)?; + let temp = self.parse_expr_and()?; + expr = (E::Or(Box::new(expr), Box::new(temp)), pos).into(); + }, + _ => break + } + } + Ok(expr) + } + + fn parse_expr_range(&mut self) -> Result<Expr> { + let expr = self.parse_expr_or()?; + let pos = expr.pos; + match self.lexer.peek_token()?.data { + T::Range => { + self.lexer.next_token()?; + let temp = self.parse_expr_or()?; + Ok((E::BinaryOp(Box::new(expr), Box::new(temp), BinaryOp::Range), pos).into()) + }, + T::RangeEq => { + self.lexer.next_token()?; + let temp = self.parse_expr_or()?; + Ok((E::BinaryOp(Box::new(expr), Box::new(temp), BinaryOp::RangeEq), pos).into()) + }, + _ => Ok(expr) + } + } + + fn parse_expr_op_assign(&mut self) -> Result<Expr> { + use BinaryOp as B; + let expr = self.parse_expr_range()?; + let tok = self.lexer.peek_token_nl()?; + let pos = tok.pos; + let data: ExprData = match tok.data { + T::Assign => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new(self.parse_expr()?)) + }, + T::AssignAnd => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::And(Box::new(expr), Box::new(self.parse_expr()?)), pos).into())) + }, + T::AssignOr => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::Or(Box::new(expr), Box::new(self.parse_expr()?)),pos).into())) + }, + T::AssignAdd => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::Add),pos).into())) + }, + T::AssignSubtract => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::Subtract),pos).into())) + }, + T::AssignMultiply => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::Multiply),pos).into())) + }, + T::AssignDivide => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::Divide),pos).into())) + }, + T::AssignModulo => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::Modulo),pos).into())) + }, + T::AssignPower => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::Power),pos).into())) + }, + T::AssignBitwiseAnd => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::BitwiseAnd),pos).into())) + }, + T::AssignBitwiseOr => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::BitwiseOr),pos).into())) + }, + T::AssignBitwiseXor => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::BitwiseXor),pos).into())) + }, + T::AssignBitwiseShiftLeft => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::BitwiseShiftLeft),pos).into())) + }, + T::AssignBitwiseShiftRight => { + self.lexer.next_token_nl()?; + E::Assign(Box::new(expr.clone()),Box::new((E::BinaryOp(Box::new(expr), Box::new(self.parse_expr()?), B::BitwiseShiftRight),pos).into())) + }, + _ => expr.data + }; + Ok((data, pos).into()) + } + + fn parse_expr(&mut self) -> Result<Expr> { + let mut expr = self.parse_expr_op_assign()?; + let pos = expr.pos; + loop { + let tok = self.lexer.peek_token()?; + match tok.data { + T::Pipe => { + self.force_token(T::Pipe)?; + let temp = self.parse_expr_op_assign()?; + expr = (E::Pipeline(Box::new(expr), Box::new(temp)), pos).into(); + }, + _ => break + } + } + Ok(expr) + } + + fn parse_root(&mut self) -> Result<Expr> { + let mut block = Vec::new(); + loop { + match self.lexer.peek_token()?.data { + T::Eof => break, + T::SemiColon => { + self.lexer.next_token()?; + continue + } + _ => {} + }; + let expr = self.parse_expr()?; + block.push(expr); + let next = self.lexer.next_token_nl()?; + match next.data { + T::Eof => break, + T::SemiColon => continue, + _ => return Err(error!("expected a semicolon").pos(next.pos)) + }; + } + Ok((E::Block(block), Position::default()).into()) + } + + pub fn parse<T: Into<String>>(&mut self, into: T) -> Result<Expr> { + let lexer = Lexer::new(into); + self.lexer = lexer; + let ast = self.parse_root()?; + if self.optimize { + Ok(optimize(ast)?) + } else { + Ok(ast) + } + } +} diff --git a/matrix-lang/src/prelude.rs b/matrix-lang/src/prelude.rs new file mode 100644 index 0000000..c5af0c8 --- /dev/null +++ b/matrix-lang/src/prelude.rs @@ -0,0 +1,60 @@ +pub type Result<T> = std::result::Result<T, Exception>; + +pub use crate::value::Value as Value; +pub use crate::value::exception::Exception as Exception; +pub use crate::value::matrix::Matrix as Matrix; +pub use crate::value::gc::Gc as Gc; +pub use crate::value::hash::ValueMap as ValueMap; +pub use crate::value::function::Function as Function; +pub use crate::value::function::InnerFunction as InnerFunction; + +pub use num_complex::Complex64 as Complex64; +pub use num_rational::Rational64 as Rational64; +pub use regex::Regex as Regex; +pub use std::fs::File as File; + +pub use std::rc::Rc as Rc; +pub use std::cell::RefCell as RefCell; + +pub use crate::exception as exception; +pub use crate::native as native; +pub use crate::iter as iter; + +pub use crate::value::exception::HASH_EXCEPTION as HASH_EXCEPTION; +pub use crate::value::exception::VALUE_EXCEPTION as VALUE_EXCEPTION; +pub use crate::value::exception::PARSE_EXCEPTION as PARSE_EXCEPTION; +pub use crate::value::exception::COMPILE_EXCEPTION as COMPILE_EXCEPTION; +pub use crate::value::exception::RUNTIME_EXCEPTION as RUNTIME_EXCEPTION; +pub use crate::value::exception::BINARY_EXECPTION as BINARY_EXCEPTION; +pub use crate::value::exception::IO_EXECPTION as IO_EXCEPTION; + +pub use crate::value::clone::ValueClone as ValueClone; +pub use crate::value::hash::TryHash as TryHash; + +pub use crate::vm::Vm as Vm; +pub use crate::vm::StackFrame as StackFrame; +pub use crate::vm::Interupt as Interupt; + +pub use crate::lex::Lexer as Lexer; +pub use crate::lex::Position as Position; +pub use crate::lex::Token as Token; +pub use crate::lex::TokenData as TokenData; +pub use crate::parse::Parser as Parser; +pub use crate::parse::ParserBuilder as ParserBuilder; +pub use crate::compiler::Compiler as Compiler; +pub use crate::compiler::CompilerBuilder as CompilerBuilder; +pub use crate::compiler::NamesTable as NamesTable; +pub use crate::compiler::GlobalsTable as GlobalsTable; +pub use crate::compiler::Global as Global; + +pub use crate::ast::AstName as AstName; +pub use crate::ast::Expr as Expr; +pub use crate::ast::ExprData as ExprData; +pub use crate::ast::BinaryOp as BinaryOp; +pub use crate::ast::UnaryOp as UnaryOp; +pub use crate::ast::optimize as optimize; + +pub use crate::chunk::Chunk as Chunk; +pub use crate::chunk::Instruction as Instruction; + +pub use crate::binary::Program as Program; diff --git a/matrix-lang/src/value/clone.rs b/matrix-lang/src/value/clone.rs new file mode 100644 index 0000000..d5ac983 --- /dev/null +++ b/matrix-lang/src/value/clone.rs @@ -0,0 +1,54 @@ +use crate::prelude::*; + +pub trait ValueClone { + fn deep_clone(&self) -> Self; + fn shallow_clone(&self) -> Self; +} + +impl ValueClone for Value { + fn deep_clone(&self) -> Self { + use Value as V; + match self { + V::List(l) => V::List(l.deep_clone()), + V::Table(t) => V::Table(t.deep_clone()), + V::Matrix(m) => V::Matrix(m.deep_clone()), + _ => self.clone() + } + } + + fn shallow_clone(&self) -> Self { + use Value as V; + match self { + V::List(l) => V::List(l.shallow_clone()), + V::Table(t) => V::Table(t.shallow_clone()), + V::Matrix(m) => V::Matrix(m.shallow_clone()), + _ => self.clone() + } + } +} + +impl ValueClone for Vec<Value> { + fn deep_clone(&self) -> Self { + let mut vals = Vec::new(); + for val in self { + vals.push(val.deep_clone()) + } + vals + } + + fn shallow_clone(&self) -> Self { + self.clone() + } +} + +impl ValueClone for Matrix { + fn deep_clone(&self) -> Self { + let values = self.values.deep_clone(); + Self::new(self.domain, self.codomain, values) + } + + fn shallow_clone(&self) -> Self { + let values = self.values.shallow_clone(); + Self::new(self.domain, self.codomain, values) + } +} diff --git a/matrix-lang/src/value/comp.rs b/matrix-lang/src/value/comp.rs new file mode 100644 index 0000000..3557927 --- /dev/null +++ b/matrix-lang/src/value/comp.rs @@ -0,0 +1,373 @@ +use std::{ops::{Add, Sub, Mul, Div, Shl, Shr, BitOr, BitAnd, BitXor, Neg, Not}, cmp::Ordering}; +use crate::prelude::*; + +fn ratio_to_f64(r: Rational64) -> f64 { + *r.numer() as f64 / *r.denom() as f64 +} + +macro_rules! error { + ($($arg:tt)*) => { + exception!(VALUE_EXCEPTION, $($arg)*) + }; +} + +/// +/// MATH OPERATIONS +/// + +fn ipow(n: i64, d: i64, p: i64) -> Result<(i64, i64)> { + Ok(match (n, d, p) { + (0, _, 0) => Err(error!("cannot exponent 0 ** 0"))?, + (0, _, _) => (0, 1), + (_, _, 0) => (1, 1), + (1, 1, _) => (1, 1), + (n, d, p) if p < 0 => (d.pow((-p) as u32), n.pow((-p) as u32)), + (n, d, p) => (n.pow(p as u32), d.pow(p as u32)), + }) +} + +fn promote(a: Value, b: Value) -> (Value, Value) { + use Value as V; + match (&a, &b) { + (V::Int(x), V::Ratio(..)) => (V::Ratio((*x).into()), b), + (V::Int(x), V::Float(..)) => (V::Float(*x as f64), b), + (V::Int(x), V::Complex(..)) => (V::Complex((*x as f64).into()), b), + (V::Ratio(x), V::Float(..)) => (V::Float(ratio_to_f64(*x)), b), + (V::Ratio(x), V::Complex(..)) => (V::Complex(ratio_to_f64(*x).into()), b), + (V::Float(x), V::Complex(..)) => (V::Complex((*x).into()), b), + (V::Ratio(..), V::Int(y)) => (a, V::Ratio((*y).into())), + (V::Float(..), V::Int(y)) => (a, V::Float(*y as f64)), + (V::Complex(..), V::Int(y)) => (a, V::Complex((*y as f64).into())), + (V::Float(..), V::Ratio(y)) => (a, V::Float(ratio_to_f64(*y))), + (V::Complex(..), V::Ratio(y)) => (a, V::Complex(ratio_to_f64(*y).into())), + (V::Complex(..), V::Float(y)) => (a, V::Complex((*y).into())), + (V::List(l1), V::List(l2)) if l1.len() > 0 && l2.len() > 0 + => (V::Matrix(Matrix::from_list(l1.to_vec()).into()), V::Matrix(Matrix::from_list(l2.to_vec()).into())), + (_, V::List(l)) if l.len() > 0 + => (a, V::Matrix(Matrix::from_list(l.to_vec()).into())), + (V::List(l), _) if l.len() > 0 + => (V::Matrix(Matrix::from_list(l.to_vec()).into()), b), + _ => (a, b), + } +} + + +impl Add for Value { + type Output = Result<Self>; + fn add(self, rhs: Self) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x + y)), + (Float(x), Float(y)) => Ok(Float(x + y)), + (Ratio(x), Ratio(y)) => Ok(Ratio(x + y)), + (Complex(x), Complex(y)) => Ok(Complex(x + y)), + (Matrix(x), Matrix(y)) => Ok(Matrix((x + y)?.into())), + (Matrix(x), r) => Ok(Matrix(x.increment(r)?.into())), + (l, Matrix(y)) => Ok(Matrix(y.increment(l)?.into())), + (String(str), value) => Ok(String(Rc::from( + format!("{str}{value}") + ))), + (value, String(str)) => Ok(String(Rc::from( + format!("{value}{str}") + ))), + (List(mut l1), List(l2)) => { + l1.extend_from_slice(&l2); + Ok(List(l1)) + }, + (l, r) => Err(error!("cannot add {l:?} + {r:?}")) + } + } +} + +impl Sub for Value { + type Output = Result<Self>; + fn sub(self, rhs: Self) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x - y)), + (Float(x), Float(y)) => Ok(Float(x - y)), + (Ratio(x), Ratio(y)) => Ok(Ratio(x - y)), + (Complex(x), Complex(y)) => Ok(Complex(x - y)), + (Matrix(x), Matrix(y)) => Ok(Matrix((x - y)?.into())), + (Matrix(x), r) => Ok(Matrix(x.decrement(r)?.into())), + (l, r) => Err(error!("cannot subtract {l:?} - {r:?}")) + } + } +} + +impl Mul for Value { + type Output = Result<Self>; + fn mul(self, rhs: Value) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x * y)), + (Float(x), Float(y)) => Ok(Float(x * y)), + (Ratio(x), Ratio(y)) => Ok(Ratio(x * y)), + (Complex(x), Complex(y)) => Ok(Complex(x * y)), + (Matrix(x), Matrix(y)) => Ok(Matrix((x * y)?.into())), + (Matrix(x), r) => Ok(Matrix(x.scale(r)?.into())), + (l, Matrix(y)) => Ok(Matrix(y.scale(l)?.into())), + (l, r) => Err(error!("cannot multiply {l:?} * {r:?}")) + } + } +} + +impl Div for Value { + type Output = Result<Self>; + fn div(self, rhs: Value) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(_), Int(0)) => Err(error!("cannot divide by zero")), + (Int(x), Int(y)) => Ok(Ratio(Rational64::new(x, y))), + (Float(x), Float(y)) => Ok(Float(x / y)), + (Ratio(x), Ratio(y)) => Ok(Ratio(x / y)), + (Complex(x), Complex(y)) => Ok(Complex(x / y)), + (l, r) => Err(error!("cannot divide {l:?} / {r:?}")) + } + } +} + +impl BitOr for Value { + type Output = Result<Self>; + fn bitor(self, rhs: Value) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x | y)), + (l, r) => Err(error!("cannot bitwise or {l:?} | {r:?}")) + } + } +} + +impl BitAnd for Value { + type Output = Result<Self>; + fn bitand(self, rhs: Value) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x & y)), + (l, r) => Err(error!("cannot bitwise and {l:?} & {r:?}")) + } + } +} + +impl BitXor for Value { + type Output = Result<Self>; + fn bitxor(self, rhs: Value) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x ^ y)), + (l, r) => Err(error!("cannot bitwise xor {l:?} ^ {r:?}")) + } + } +} + +impl Shl for Value { + type Output = Result<Self>; + fn shl(self, rhs: Value) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x << y)), + (l, r) => Err(error!("cannot bitwise shift left {l:?} << {r:?}")) + } + } +} + +impl Shr for Value { + type Output = Result<Self>; + fn shr(self, rhs: Value) -> Self::Output { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x >> y)), + (l, r) => Err(error!("cannot bitwise shift right {l:?} >> {r:?}")) + } + } +} + +impl PartialEq for Value { + fn eq(&self, other: &Self) -> bool { + use Value::*; + match (self, other) { + (Nil, Nil) => true, + (Bool(a), Bool(b)) => a == b, + (Int(a), Int(b)) => *a == *b, + (Ratio(a), Ratio(b)) => *a == *b, + (Float(a), Float(b)) => *a == *b, + (Complex(a), Complex(b)) => *a == *b, + (Int(a), Ratio(b)) => Rational64::from(*a) == *b, + (Ratio(a), Int(b)) => *a == Rational64::from(*b), + (Int(a), Float(b)) => *a as f64 == *b, + (Float(a), Int(b)) => *a == *b as f64, + (Int(a), Complex(b)) => Complex64::from(*a as f64) == *b, + (Complex(a), Int(b)) => *a == Complex64::from(*b as f64), + (Ratio(a), Float(b)) => ratio_to_f64(*a) == *b, + (Float(a), Ratio(b)) => *a == ratio_to_f64(*b), + (Ratio(a), Complex(b)) => Complex64::from(ratio_to_f64(*a)) == *b, + (Complex(a), Ratio(b)) => *a == Complex64::from(ratio_to_f64(*b)), + (Float(a), Complex(b)) => Complex64::from(*a) == *b, + (Complex(a), Float(b)) => *a == Complex64::from(*b), + (String(a), String(b)) => *a == *b, + (List(a), List(b)) => *a == *b, + (Matrix(a), Matrix(b)) => a == b, + _ => false, + } + } +} + +impl PartialOrd for Value { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + use Value::*; + match (self, other) { + (Nil, Nil) => Some(Ordering::Equal), + (Bool(a), Bool(b)) => a.partial_cmp(b), + (Int(a), Int(b)) => a.partial_cmp(b), + (Ratio(a), Ratio(b)) => a.partial_cmp(b), + (Float(a), Float(b)) => a.partial_cmp(b), + (Int(a), Ratio(b)) => Rational64::from(*a).partial_cmp(b), + (Ratio(a), Int(b)) => a.partial_cmp(&Rational64::from(*b)), + (Int(a), Float(b)) => (*a as f64).partial_cmp(b), + (Float(a), Int(b)) => a.partial_cmp(&(*b as f64)), + (Ratio(a), Float(b)) => ratio_to_f64(*a).partial_cmp(b), + (Float(a), Ratio(b)) => a.partial_cmp(&ratio_to_f64(*b)), + (String(a), String(b)) => a.partial_cmp(b), + (List(a), List(b)) => a.partial_cmp(b), + (Matrix(a), Matrix(b)) => a.values.partial_cmp(&b.values), + _ => None, + } + } +} + +impl Neg for Value { + type Output = Value; + + fn neg(self) -> Self::Output { + use Value::*; + match self { + Bool(b) => Bool(!b), + Int(i) => Int(-i), + Float(f) => Float(-f), + Ratio(r) => Ratio(-r), + Complex(c) => Complex(-c), + _ => return Float(f64::NAN) + } + } +} + +impl Not for Value { + type Output = bool; + + fn not(self) -> Self::Output { + use Value as V; + match self { + V::Nil => true, + V::Bool(b) => !b, + V::Int(i) => i == 0, + V::Float(f) => f == 0.0, + V::Ratio(r) => *(r.numer()) == 0 || *(r.denom()) == 0, + V::Complex(c) => !c.is_normal(), + V::Regex(_) => false, + V::List(_) => false, + V::Matrix(_) => false, + V::Table(_) => false, + V::String(s) => s.as_ref() == "", + V::Function(_) => false, + V::Iter(_) => false, + V::Range(_) => false, + V::File(_) => false, + V::Exception(_) => false, + } + } +} + + +impl Value { + + pub fn modulo(self, rhs: Value) -> Result<Self> { + use Value::*; + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Int(x % y)), + (Float(x), Float(y)) => Ok(Float(x % y)), + (Ratio(x), Ratio(y)) => Ok(Ratio(x % y)), + (Complex(x), Complex(y)) => Ok(Complex(x % y)), + (l, r) => Err(error!("cannot modulo: {l:?} % {r:?}")) + } + } + + pub fn pow(self, rhs: Value) -> Result<Self> { + use Value::*; + if let (Ratio(x), Int(y)) = (&self, &rhs) { + return Ok(Ratio(ipow(*(*x).numer(), *(*x).denom(), *y)?.into())); + } + match promote(self, rhs) { + (Int(x), Int(y)) => Ok(Ratio(ipow(x, 1, y)?.into())), + (Float(x), Float(y)) => Ok(Float(x.powf(y))), + (Ratio(x), Ratio(y)) => Ok(Float(ratio_to_f64(x).powf(ratio_to_f64(y)))), + (Complex(x), Complex(y)) => Ok(Complex(x.powc(y))), + (l, r) => Err(error!("cannot exponent: {l:?} ** {r:?}")) + } + } + + pub fn floaty(self) -> Self { + use Value as V; + match self { + V::Int(i) => V::Float(i as f64), + V::Ratio(r) => V::Float(ratio_to_f64(r)), + a => a + } + } + + pub fn is_zero(&self) -> bool { + use Value as V; + match self { + V::Int(i) => *i == 0, + V::Float(f) => *f == 0.0 || *f == -0.0, + V::Ratio(r) => *r.numer() == 0, + _ => false, + } + } + + pub fn binary_op(op: BinaryOp, lhs: Value, rhs: Value) -> Result<Self> { + use BinaryOp::*; + match op { + Add => lhs + rhs, + Subtract => lhs - rhs, + Multiply => lhs * rhs, + Divide => lhs / rhs, + Modulo => lhs.modulo(rhs), + Power => lhs.pow(rhs), + BitwiseAnd => lhs & rhs, + BitwiseOr => lhs | rhs, + BitwiseXor => lhs ^ rhs, + BitwiseShiftLeft => lhs << rhs, + BitwiseShiftRight => lhs >> rhs, + Equals => Ok(Self::Bool(lhs == rhs)), + NotEquals => Ok(Self::Bool(lhs != rhs)), + GreaterEquals => Ok(Self::Bool(lhs >= rhs)), + LessEquals => Ok(Self::Bool(lhs <= rhs)), + GreaterThan => Ok(Self::Bool(lhs > rhs)), + LessThan => Ok(Self::Bool(lhs < rhs)), + Range | RangeEq => { + let Value::Int(lhs) = lhs else { + return Err(error!("range can only take [Int]'s")) + }; + let Value::Int(rhs) = rhs else { + return Err(error!("range can only take [Int]'s")) + }; + Ok(Self::Range(Rc::new((lhs, rhs, op == RangeEq)))) + }, + } + } + + pub fn unary_op(op: UnaryOp, val: Value) -> Value { + use UnaryOp::*; + match op { + Negate => -val, + Not => Self::Bool(!val), + } + } + + pub fn to_regex(value: &str) -> Result<Self> { + match Regex::new(value) { + Ok(r) => Ok(Self::Regex(r.into())), + Err(e) => Err(error!("{e}")), + } + } +} diff --git a/matrix-lang/src/value/exception.rs b/matrix-lang/src/value/exception.rs new file mode 100644 index 0000000..0df6f5c --- /dev/null +++ b/matrix-lang/src/value/exception.rs @@ -0,0 +1,78 @@ +use std::{fmt::{Debug, Display}, error::Error}; +use crate::prelude::*; + +#[macro_export] +macro_rules! exception { + ($type:expr) => { + $crate::prelude::Exception::new($type) + }; + ($type:expr, $($arg:tt)*) => { + $crate::prelude::Exception::msg($type, format!($($arg)*).as_str()) + }; +} + +pub const HASH_EXCEPTION: &'static str = "hash"; +pub const VALUE_EXCEPTION: &'static str = "value"; +pub const PARSE_EXCEPTION: &'static str = "parse"; +pub const COMPILE_EXCEPTION: &'static str = "compile"; +pub const RUNTIME_EXCEPTION: &'static str = "runtime"; +pub const BINARY_EXECPTION: &'static str = "binary"; +pub const IO_EXECPTION: &'static str = "io"; + +#[derive(Clone)] +pub struct Exception(Gc<ExceptionInner>); + +#[derive(Clone)] +struct ExceptionInner { + ty: Rc<str>, + msg: Rc<str>, + trace: Vec<(Rc<str>, Position)> +} + +impl Exception { + pub fn msg(ty: &str, msg: &str) -> Self { + Self(Gc::new(ExceptionInner { ty: ty.into(), msg: msg.into(), trace: Vec::new() })) + } + + pub fn pos(mut self, pos: Position) -> Self { + self.0.trace.push(( + Rc::from("<root>"), + pos + )); + self + } + + pub fn trace(mut self, block: Rc<str>, pos: Position) -> Self { + self.0.trace.push(( + block, + pos + )); + self + } +} + +impl Display for Exception { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let ty = self.0.ty.as_ref(); + let msg = self.0.msg.as_ref(); + write!(f, "{}\n Type <{}>", msg, ty)?; + for (block, pos) in self.0.trace.iter() { + write!(f, "\n In {block} at {pos}\n")?; + } + Ok(()) + } +} + +impl Debug for Exception { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "[Exception {}]", self.0.ty.as_ref()) + } +} + +impl Error for Exception {} + +impl<T> From<Exception> for Result<T> { + fn from(value: Exception) -> Self { + Err(value) + } +} diff --git a/matrix-lang/src/value/fmt.rs b/matrix-lang/src/value/fmt.rs new file mode 100644 index 0000000..f276bf1 --- /dev/null +++ b/matrix-lang/src/value/fmt.rs @@ -0,0 +1,186 @@ +use std::fmt::{Debug, Display}; +use crate::prelude::*; + +use Value as V; + +impl Debug for Value { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + V::Nil => write!(f, "[Nil]"), + V::Int(i) => write!(f, "[Int {i}]"), + V::Bool(b) => write!(f, "[Bool {b}]"), + V::Float(vf) => write!(f, "[Float {vf}]"), + V::Ratio(r) => write!(f, "[Ratio {r}]"), + V::Complex(c) => write!(f, "[Complex {c}]"), + V::Regex(r) => write!(f, "[Regex /{r}/]"), + V::String(s) => write!(f, "[String '{s}']"), + V::List(l) => write!(f, "[List {}]", l.len()), + V::Matrix(m) => write!(f, "[Matirx {}x{}]", m.domain, m.codomain), + V::Table(t) => write!(f, "[Table {}]", t.len()), + V::Function(vf) => write!(f, "[Function {}]", vf.name), + V::Range(r) => write!(f, "[Range {:?}..{:?}]", r.0, r.1), + V::Iter(_) => write!(f, "[Iterator]"), + V::Exception(_) => write!(f, "[Error]"), + V::File(_) => write!(f, "[File]"), + } + } +} + +impl Display for Value { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let red; + let green; + let yellow; + let blue; + let pink; + let cyan; + let clear; + + if f.alternate() { + red = "\x1b[31m"; + green = "\x1b[32m"; + yellow = "\x1b[33m"; + blue = "\x1b[34m"; + pink = "\x1b[35m"; + cyan = "\x1b[36m"; + clear = "\x1b[0m"; + } else { + red = ""; + green = ""; + yellow = ""; + blue = ""; + pink = ""; + cyan = ""; + clear = ""; + } + + match self { + V::Nil => {write!(f, "{blue}nil{clear}")?;}, + V::Bool(b) => {write!(f, "{yellow}{b}{clear}")?;}, + V::Int(i) => {write!(f, "{yellow}{i}{clear}")?;}, + V::Float(l) => {write!(f, "{yellow}{l}{clear}")?;}, + V::Ratio(r) => {write!(f, "{yellow}{r}{clear}")?;}, + V::Complex(c) => {write!(f, "{yellow}{c}{clear}")?;}, + V::Regex(r) => {write!(f, "/{red}{r}{clear}/")?;}, + V::String(s) => { + if f.alternate() { + write!(f, "{green}'{s}'{clear}")?; + } else { + write!(f, "{s}")?; + } + } + V::List(l) => { + if l.len() < 1 { + write!(f, "[]")?; + return Ok(()) + } + write!(f, "[ ")?; + for (i, el) in l.iter().enumerate() { + if i != 0 { + write!(f, " ")?; + } + if f.alternate() { + write!(f, "{el:#}")?; + } else { + write!(f, "{el}")?; + } + } + write!(f, " ]")?; + }, + V::Matrix(m) => { + if f.alternate() { + write!(f, "{m:#}")?; + } else { + write!(f, "{m}")?; + } + }, + V::Table(t) => { + if f.alternate() { + write!(f, "{t:#}")?; + } else { + write!(f, "{t}")?; + } + }, + V::Function(fun) => { + write!(f, "{cyan}{fun}{clear}")?; + } + V::Range(r) => { + if f.alternate() { + write!(f, "{:#}..{:#}", r.0, r.1)?; + } else { + write!(f, "{}..{}", r.0, r.1)?; + } + } + V::Iter(_) => {write!(f, "{pink}[Iterator]{clear}")?;}, + V::File(_) => {write!(f, "{pink}[File]{clear}")?;}, + V::Exception(e) => {write!(f, "{red}{e}{clear}")?;}, + }; + Ok(()) + } +} + +impl Debug for Matrix { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "[Matrix {}x{}]", self.domain, self.codomain) + } +} + +impl Display for Matrix { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let mut max_cols = vec![0; self.domain]; + let mut vals: Vec<String> = Vec::with_capacity(self.domain * self.codomain); + for row in 0..self.codomain { + for col in 0..self.domain { + let idx = col + row * self.domain; + let el = &self.values[idx]; + let s = match f.alternate() { + true => format!("{:#}", el), + false => format!("{}", el) + }; + max_cols[col] = max_cols[col].max(s.len()); + vals.push(s); + } + } + + write!(f, "\n")?; + for row in 0..self.codomain { + for col in 0..self.domain { + let idx = col + row * self.domain; + let s = vals[idx].as_str(); + let width = max_cols[col]; + write!(f, " {s:>width$}")?; + } + write!(f, "\n")?; + } + + Ok(()) + } +} + +impl Debug for ValueMap { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "[Table {}]", self.len()) + } +} + +impl Display for ValueMap { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + if self.len() < 1 { + write!(f, "{{}}")?; + return Ok(()) + } + write!(f, "{{ ")?; + for (i, (key, value)) in self.entries().enumerate() { + if i != 0 { + write!(f, ", ")?; + } + if f.alternate() { + write!(f, "{key:#} = {value:#}")? + } else { + write!(f, "{key} = {value}")? + } + } + write!(f, " }}")?; + Ok(()) + } +} diff --git a/matrix-lang/src/value/function.rs b/matrix-lang/src/value/function.rs new file mode 100644 index 0000000..38d8b0b --- /dev/null +++ b/matrix-lang/src/value/function.rs @@ -0,0 +1,43 @@ +use crate::prelude::*; +use std::fmt::{Debug, Display}; + +pub struct Function { + pub name: Rc<str>, + pub arity: usize, + pub variadic: bool, + pub fun: InnerFunction +} + +#[derive(Clone)] +pub enum InnerFunction { + Compiled(Rc<Chunk>), + Native(Rc<dyn Fn((&mut Vm, &mut StackFrame), Vec<Value>) -> Result<Value>>), +} + +impl Debug for Function { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + use InnerFunction as F; + match self.fun { + F::Compiled(_) => { + write!(f, "[Function {}]", self.name) + }, + F::Native(_) => { + write!(f, "[Builtin {}]", self.name) + } + } + } +} + +impl Display for Function { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + use InnerFunction as F; + match self.fun { + F::Compiled(_) => { + write!(f, "[Function {}]", self.name) + }, + F::Native(_) => { + write!(f, "[Builtin {}]", self.name) + } + } + } +} diff --git a/matrix-lang/src/value/gc.rs b/matrix-lang/src/value/gc.rs new file mode 100644 index 0000000..5ef8b80 --- /dev/null +++ b/matrix-lang/src/value/gc.rs @@ -0,0 +1,186 @@ +use std::{ops::{Index, IndexMut, Deref, DerefMut, Add, Sub, Mul}, marker::PhantomData, ptr::NonNull, fmt::{Debug, Display}}; +use crate::prelude::*; + +pub struct Gc<T> { + ptr: NonNull<GcInner<T>>, + phantom: PhantomData<GcInner<T>> +} + +struct GcInner<T> { + rc: usize, + data: T +} + +impl<T> Gc<T> { + pub fn new(data: T) -> Self { + let boxed = Box::new(GcInner { + rc: 1, + data, + }); + Self { + ptr: NonNull::new(Box::into_raw(boxed)).unwrap(), + phantom: PhantomData + } + } +} + +impl <T: Clone> Gc<T> { + pub fn into_inner(self) -> T { + unsafe { + self.ptr.as_ref().data.clone() + } + } + + fn data(&self) -> T { + unsafe { + self.ptr.as_ref().data.clone() + } + } +} + +impl <T: ValueClone> ValueClone for Gc<T> { + fn deep_clone(&self) -> Self { + unsafe { + let data = self.ptr.as_ref().data.deep_clone(); + Self::new(data) + } + } + + fn shallow_clone(&self) -> Self { + unsafe { + let data = self.ptr.as_ref().data.shallow_clone(); + Self::new(data) + } + } +} + +impl<T> From<T> for Gc<T> { + fn from(value: T) -> Self { + Gc::new(value) + } +} + +impl<T: IndexMut<Idx>, Idx> IndexMut<Idx> for Gc<T> { + fn index_mut(&mut self, index: Idx) -> &mut Self::Output { + self.deref_mut().index_mut(index) + } +} + +impl<T: Index<Idx>, Idx> Index<Idx> for Gc<T> { + type Output = T::Output; + + fn index(&self, index: Idx) -> &Self::Output { + self.deref().index(index) + } +} + +impl<T> DerefMut for Gc<T> { + fn deref_mut(&mut self) -> &mut Self::Target { + unsafe { + &mut self.ptr.as_mut().data + } + } +} + +impl<T> Deref for Gc<T> { + type Target = T; + + fn deref(&self) -> &Self::Target { + unsafe { + &self.ptr.as_ref().data + } + } +} + +impl <T: PartialEq> PartialEq for Gc<T> { + fn eq(&self, other: &Self) -> bool { + self.deref().eq(other.deref()) + } +} + +impl <T: Iterator> Iterator for Gc<T> { + type Item = T::Item; + + fn next(&mut self) -> Option<Self::Item> { + self.deref_mut().next() + } +} + +impl<T: Eq> Eq for Gc<T> {} + +impl<T> Clone for Gc<T> { + fn clone(&self) -> Self { + unsafe { + let inner = self.ptr.as_ptr().as_mut().unwrap(); + inner.rc += 1; + + Self { + ptr: self.ptr, + phantom: PhantomData + } + } + } +} + +impl<T> Drop for Gc<T> { + fn drop(&mut self) { + unsafe { + let inner = self.ptr.as_mut(); + if inner.rc > 1 { + inner.rc -= 1; + } else { + let _ = Box::from_raw(self.ptr.as_ptr()); + } + } + } +} + +impl<T: Debug> Debug for Gc<T> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + if f.alternate() { + write!(f, "{:#?}", self.deref()) + } else { + write!(f, "{:?}", self.deref()) + } + } +} + +impl<T: Display> Display for Gc<T> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + if f.alternate() { + write!(f, "{:#}", self.deref()) + } else { + write!(f, "{}", self.deref()) + } + } +} + +impl <T: Add + Clone> Add for Gc<T> { + type Output = T::Output; + + fn add(self, rhs: Self) -> Self::Output { + let a = self.data(); + let b = rhs.data(); + a + b + } +} + +impl <T: Sub + Clone> Sub for Gc<T> { + type Output = T::Output; + + fn sub(self, rhs: Self) -> Self::Output { + let a = self.data(); + let b = rhs.data(); + a - b + } +} + +impl <T: Mul + Clone> Mul for Gc<T> { + type Output = T::Output; + + fn mul(self, rhs: Self) -> Self::Output { + let a = self.data(); + let b = rhs.data(); + a * b + } +} diff --git a/matrix-lang/src/value/hash.rs b/matrix-lang/src/value/hash.rs new file mode 100644 index 0000000..35c1343 --- /dev/null +++ b/matrix-lang/src/value/hash.rs @@ -0,0 +1,240 @@ +use crate::prelude::*; +use std::hash::{Hash, DefaultHasher, Hasher}; + +#[derive(Clone)] +pub struct ValueMap { + values: Vec<ValueEntry>, + size: usize, + used: usize, +} + +#[derive(Clone)] +enum ValueEntry { + Empty, + Taken((Value, Value)), + Gravestone(Value), +} + +impl Default for ValueMap { + fn default() -> Self { + ValueMap { + values: vec![ValueEntry::Empty; 8], + size: 8, + used: 0, + } + } +} + +impl ValueMap { + + fn get_index(values: &Vec<ValueEntry>, size: usize, key: &Value, hash: usize) -> usize { + let mut nearest_grave = None; + let start = hash & size; + for offset in 0..size { + let idx = (start + offset) % size; + match &values[idx] { + ValueEntry::Empty => return idx, + ValueEntry::Taken((marker, _)) => { + if marker.eq(key) { return idx }; + continue; + }, + ValueEntry::Gravestone(grave) => { + if grave.eq(key) { return idx }; + if nearest_grave.is_none() { + nearest_grave = Some(idx); + } + continue; + }, + } + } + + match nearest_grave { + Some(idx) => idx, + None => panic!("cannot get value map index: full!!!"), + } + } + + fn expand(&mut self) -> Result<()> { + let pairs = self.values.iter() + .filter_map(|e| { + match e { + ValueEntry::Taken(s) => Some(s.clone()), + _ => None + } + }) + .collect::<Vec<(Value, Value)>>(); + + let new_used = pairs.len(); + let new_size = self.size * 2 + pairs.len(); + let mut new_values = vec![ValueEntry::Empty; new_size]; + + for (key, value) in pairs.into_iter() { + let hash = self.hash(&key)?; + let idx = ValueMap::get_index(&new_values, new_size, &key, hash); + new_values[idx] = ValueEntry::Taken((key, value)); + } + + self.used = new_used; + self.size = new_size; + self.values = new_values; + + Ok(()) + } + + fn hash(&self, key: &Value) -> Result<usize> { + let mut hasher = DefaultHasher::new(); + key.try_hash(&mut hasher)?; + Ok(hasher.finish() as usize) + } + + pub fn get<'a>(&'a self, key: &Value) -> Result<Option<&'a Value>> { + let hash = self.hash(key)?; + let idx = ValueMap::get_index(&self.values, self.size, key, hash); + match &self.values[idx] { + ValueEntry::Taken((_, value)) => Ok(Some(value)), + _ => Ok(None) + } + } + + pub fn insert(&mut self, key: Value, value: Value) -> Result<()> { + if self.used * 3 >= self.size * 2 { + self.expand()?; + } + let key = key.deep_clone(); + let hash = self.hash(&key)?; + let idx = ValueMap::get_index(&self.values, self.size, &key, hash); + self.values[idx] = ValueEntry::Taken((key, value)); + self.used += 1; + Ok(()) + } + + pub fn remove(&mut self, key: &Value) -> Result<Option<Value>> { + let hash = self.hash(key)?; + let idx = ValueMap::get_index(&self.values, self.size, key, hash); + let mut value = ValueEntry::Gravestone(key.clone()); + std::mem::swap(&mut value, &mut self.values[idx]); + match value { + ValueEntry::Taken((_, v)) => { + self.used -= 1; + Ok(Some(v)) + } + _ => Ok(None), + } + } + + pub fn entries<'a>(&'a self) -> ValueMapIterator<'a> { + ValueMapIterator::new(self) + } + + pub fn new() -> Self { + Self::default() + } + + pub fn len(&self) -> usize { + self.used + } +} + +pub struct ValueMapIterator<'a> { + map: &'a ValueMap, + index: usize +} + +impl<'a> ValueMapIterator<'a> { + fn new(map: &'a ValueMap) -> Self { + Self { map, index: 0 } + } +} + +impl<'a> Iterator for ValueMapIterator<'a> { + type Item = (&'a Value, &'a Value); + + fn next(&mut self) -> Option<Self::Item> { + let mut idx = self.index; + loop { + if idx >= self.map.size { + return None + } + use ValueEntry as E; + let E::Taken((k, v)) = &self.map.values[idx] else { + idx += 1; + continue; + }; + + self.index = idx + 1; + return Some((k, v)) + } + } +} + +pub trait TryHash { + fn try_hash<H: std::hash::Hasher>(&self, state: &mut H) -> Result<()>; +} + +impl TryHash for Value { + fn try_hash<H: std::hash::Hasher>(&self, state: &mut H) -> Result<()> { + use Value::*; + match self { + Nil => 0x23845.hash(state), + Bool(b) => b.hash(state), + Int(i) => i.hash(state), + Ratio(r) => r.hash(state), + Regex(r) => r.as_str().hash(state), + String(s) => s.hash(state), + List(l) => { + for val in l.iter() { + val.try_hash(state)?; + } + } + Matrix(m) => { + m.domain.hash(state); + m.codomain.hash(state); + for val in m.values.iter() { + val.try_hash(state)?; + } + }, + _ => return Err(exception!(HASH_EXCEPTION, "cannot hash {self:?}")) + }; + Ok(()) + } +} + +impl ValueClone for ValueEntry { + fn deep_clone(&self) -> Self { + use ValueEntry as E; + match self { + E::Empty => E::Empty, + E::Taken((k, v)) => E::Taken((k.deep_clone(), v.deep_clone())), + E::Gravestone(g) => E::Gravestone(g.deep_clone()), + } + } + + fn shallow_clone(&self) -> Self { + use ValueEntry as E; + match self { + E::Empty => E::Empty, + E::Taken((k, v)) => E::Taken((k.clone(), v.clone())), + E::Gravestone(g) => E::Gravestone(g.clone()), + } + } +} + +impl ValueClone for ValueMap { + fn deep_clone(&self) -> Self { + let values = self.values.iter().map(|e| e.deep_clone()).collect(); + Self { + values, + size: self.size, + used: self.used + } + } + + fn shallow_clone(&self) -> Self { + let values = self.values.iter().map(|e| e.clone()).collect(); + Self { + values, + size: self.size, + used: self.used + } + } +} diff --git a/matrix-lang/src/value/index.rs b/matrix-lang/src/value/index.rs new file mode 100644 index 0000000..a5725e8 --- /dev/null +++ b/matrix-lang/src/value/index.rs @@ -0,0 +1,230 @@ +use std::cmp::Ordering; + +use crate::prelude::*; + +macro_rules! error { + ($($arg:tt)*) => { + Err(exception!(VALUE_EXCEPTION, $($arg)*)) + }; +} + +impl Value { + pub fn val_cmp(&self, other: &Self) -> Result<Ordering> { + self.partial_cmp(other) + .map_or_else(|| error!("cannot compare: {self:?} and {other:?}"), Ok) + } + + fn index_single(&self, index: &Value) -> Result<Self> { + use Value as V; + match (self, index) { + (V::Table(t), index) => { + Ok(t.get(index)?.unwrap_or(&Value::Nil).clone()) + }, + (V::List(l), V::Int(i)) => { + if *i < 0 || *i as usize >= l.len() { + return error!("{i} out of bounds for {self:?}") + } + Ok(l[*i as usize].clone()) + }, + (V::Matrix(m), V::Int(i)) => { + if *i < 0 || *i as usize >= m.values.len() { + return error!("{i} out of bounds for {self:?}") + } + Ok(m.values[*i as usize].clone()) + }, + _ => return error!("{index:?} cant index {self:?}") + } + } + + fn index_multiple(&self, indexes: &Vec<Value>) -> Result<Self> { + use Value as V; + match self { + V::List(..) => { + let mut ret = Vec::new(); + for index in indexes { + let res = self.index_single(index)?; + ret.push(res); + } + Ok(V::List(ret.into())) + } + V::Table(..) => { + let mut ret = ValueMap::new(); + for index in indexes { + let res = self.index_single(index)?; + ret.insert(index.clone(), res)?; + } + Ok(V::Table(ret.into())) + } + V::Matrix(m) => { + let err = || error!("{self:?} can be index by [Int] or [Int;Int]"); + if indexes.len() != 2 { + return err() + } + let lhs = indexes[0].clone(); + let rhs = indexes[1].clone(); + match (lhs, rhs) { + (V::Nil, V::Nil) => { + Ok(V::Matrix(m.shallow_clone())) + }, + (V::Int(row), V::Nil) => { + let Some((_, row)) = m.rows().enumerate().filter(|(idx, _)| *idx as i64 == row).next() else { + return err(); + }; + let row: Vec<Value> = row.into_iter().map(|e| e.clone()).collect(); + Ok(V::Matrix(Matrix::new(row.len(), 1, row).into())) + }, + (V::Nil, V::Int(col)) => { + let Some((_, col)) = m.cols().enumerate().filter(|(idx, _)| *idx as i64 == col).next() else { + return err(); + }; + let col: Vec<Value> = col.into_iter().map(|e| e.clone()).collect(); + Ok(V::Matrix(Matrix::new(1, col.len(), col).into())) + }, + (V::Int(row), V::Int(col)) => { + if row < 0 || col < 0 { + return err(); + } + m.get(row as usize, col as usize) + } + _ => return err() + } + } + _ => return error!("cannot index {self:?}") + } + } + + pub fn index(&self, index: &Vec<Value>) -> Result<Self> { + if index.len() == 0 { + Ok(self.shallow_clone()) + } else if index.len() == 1 { + self.index_single(&index[0]) + } else { + self.index_multiple(index) + } + } + + fn store_index_single(&mut self, index: &Value, store: Value) -> Result<()> { + use Value as V; + let err = format!("{self:?}"); + match (self, index) { + (V::Table(t), index) => { + t.insert(index.clone(), store) + }, + (V::List(l), V::Int(i)) => { + if *i < 0 || *i as usize >= l.len() { + return error!("{i} out of bounds for {err}") + } + l[*i as usize] = store; + Ok(()) + }, + (V::Matrix(m), V::Int(i)) => { + if *i < 0 || *i as usize >= m.values.len() { + return error!("{i} out of bounds for {err}") + } + m.values[*i as usize] = store; + Ok(()) + }, + _ => return error!("{index:?} cant index {err}") + } + } + + fn store_index_multiple(&mut self, indexes: &Vec<Value>, store: Value) -> Result<()> { + use Value as V; + match self { + V::List(..) => { + for index in indexes { + self.store_index_single(index, store.clone())?; + } + Ok(()) + } + V::Table(..) => { + for index in indexes { + self.store_index_single(index, store.clone())?; + } + Ok(()) + } + _ => return error!("cannot index {self:?}") + } + } + + pub fn store_index(&mut self, index: &Vec<Value>, store: Value) -> Result<()> { + if index.len() == 0 { + Ok(()) + } else if index.len() == 1 { + self.store_index_single(&index[0], store) + } else { + self.store_index_multiple(index, store) + } + } + + pub fn store_field_access(&mut self, ident: &str, val: Value) -> Result<()> { + use Value as V; + match self { + V::Table(t) => { + let key = V::String(Rc::from(ident)); + Ok(t.insert(key, val)?) + }, + _ => return error!("cannot field access assign {self:?}") + } + } + + pub fn field_access(&self, ident: &str) -> Result<Self> { + use Value as V; + match self { + V::Table(t) => { + let key = V::String(Rc::from(ident)); + Ok(t.get(&key)?.unwrap_or(&V::Nil).clone()) + }, + _ => return error!("cannot field access {self:?}") + } + } + +} + +impl Value { + + pub fn into_iter_fn(self) -> Result<Rc<Function>> { + let Value::Iter(iter) = self.into_iter()? else { + return error!("bypassed iter check") + }; + Ok(iter) + } + + pub fn into_iter(self) -> Result<Self> { + use Value as V; + Ok(match self { + V::Iter(..) => self, + V::List(l) => { + let iter = RefCell::new(l.into_inner().into_iter()); + iter!(move |_,_| { + match iter.borrow_mut().next() { + Some(v) => Ok(v), + None => Ok(V::Nil), + } + }) + }, + V::Range(r) => { + let r = (*r).clone(); + let lhs = RefCell::new(r.0); + let rhs = r.1; + iter!(move |_,_| { + let val = *lhs.borrow(); + let next = *lhs.borrow() + 1; + if (!r.2 && *lhs.borrow() < rhs) || (r.2 && *lhs.borrow() <= rhs) { + *lhs.borrow_mut() = next; + return Ok(Value::Int(val)) + } + Ok(Value::Nil) + }) + }, + V::Function(f) => { + if f.arity > 0 || f.variadic { + return error!("iterator functions cannot be varadic or take arguments") + } + V::Iter(f) + }, + val => return error!("cannot turn {val:?} into an iterator") + }) + } +} + diff --git a/matrix-lang/src/value/matrix.rs b/matrix-lang/src/value/matrix.rs new file mode 100644 index 0000000..91e3ec2 --- /dev/null +++ b/matrix-lang/src/value/matrix.rs @@ -0,0 +1,337 @@ +use std::ops::{Add, Sub, Mul}; + +use crate::prelude::*; + +#[derive(Clone)] +pub struct Matrix { + pub domain: usize, + pub codomain: usize, + pub values: Vec<Value> +} + +macro_rules! error { + ($($arg:tt)*) => { + exception!(VALUE_EXCEPTION, $($arg)*) + }; +} + +impl Matrix { + pub fn new( + domain: usize, + codomain: usize, + values: Vec<Value> + ) -> Self { + Self { + domain, + codomain, + values + } + } + + pub fn from_list( + values: Vec<Value> + ) -> Self { + Self { + domain: values.len(), + codomain: 1, + values + } + } + + pub fn empty( + domain: usize, + codomain: usize + ) -> Self { + let values = (0..(domain * codomain)).into_iter() + .map(|_| Value::Int(0)) + .collect(); + Self { + domain, + codomain, + values + } + } + + pub fn get(&self, row: usize, col: usize) -> Result<Value> { + if row >= self.codomain || col >= self.domain { + return Err(error!("[{};{}] out of bounds for [Matrix {}x{}]", row, col, self.domain, self.codomain)) + } + let idx = col + row * self.domain; + Ok(self.values[idx].clone()) + } + + + + pub fn set(&mut self, row: usize, col: usize, val: Value) -> Result<()> { + if row >= self.codomain || col >= self.domain { + return Err(error!("[{};{}] out of bounds for [Matrix {}x{}]", row, col, self.domain, self.codomain)) + } + let idx = col + row * self.domain; + self.values[idx] = val; + Ok(()) + } + + pub fn rows<'a>(&'a self) -> MatrixRows<'a> { + MatrixRows { + matrix: self, + row: 0 + } + } + + pub fn cols<'a>(&'a self) -> MatrixCols<'a> { + MatrixCols { + matrix: self, + col: 0 + } + } + + // SPLCIE DOMAIN + pub fn splice_cols(&self, col_start: usize, col_end: usize) -> Result<Self> { + if col_start <= col_end || col_end > self.domain { + return Err(error!("[_;{}..{}] invalid for [Matrix {}x{}]", col_start, col_end, self.domain, self.codomain)) + } + + let mut cols = Vec::new(); + + for (i, col) in self.cols().enumerate() { + if i >= col_start && i < col_end { + cols.push(col); + } + } + + let domain = cols.len(); + let codomain = cols[0].len(); + let mut res = Self::empty(domain, codomain); + + for i in 0..domain { + for j in 0..codomain { + res.set(j, i, cols[i][j].clone())?; + } + } + + Ok(res) + } + + // SPLICE CODOMAIN + pub fn splice_rows(&self, row_start: usize, row_end: usize) -> Result<Self> { + if row_start <= row_end || row_end > self.codomain { + return Err(error!("[{}..{};_] invalid for [Matrix {}x{}]", row_start, row_end, self.domain, self.codomain)) + } + + let mut rows = Vec::new(); + + for (i, row) in self.rows().enumerate() { + if i >= row_start && i < row_end { + rows.push(row); + } + } + + let domain = rows[0].len(); + let codomain = rows.len(); + let mut res = Self::empty(domain, codomain); + + for i in 0..domain { + for j in 0..codomain { + res.set(j, i, rows[j][i].clone())?; + } + } + + Ok(res) + } + + pub fn increment(&self, increment: Value) -> Result<Self> { + let values = self.values.iter() + .map(|v| v.clone() + increment.clone()) + .collect::<Result<Vec<Value>>>()?; + Ok(Matrix::new(self.domain, self.codomain, values)) + } + + pub fn decrement(&self, decrement: Value) -> Result<Self> { + let values = self.values.iter() + .map(|v| v.clone() - decrement.clone()) + .collect::<Result<Vec<Value>>>()?; + Ok(Matrix::new(self.domain, self.codomain, values)) + } + + pub fn scale(&self, scale: Value) -> Result<Self> { + let values = self.values.iter() + .map(|v| v.clone() * scale.clone()) + .collect::<Result<Vec<Value>>>()?; + Ok(Matrix::new(self.domain, self.codomain, values)) + } + + pub fn join_right(&self, other: &Matrix) -> Result<Self> { + if self.codomain != other.codomain { + return Err(error!("matrix codomain's do not match")) + } + let mut r1 = self.rows(); + let mut r2 = other.rows(); + let mut rows = Vec::new(); + loop { + let Some(r1) = r1.next() else { break; }; + let Some(r2) = r2.next() else { break; }; + + let mut row = r1 + .into_iter() + .map(|v| v.clone()) + .collect::<Vec<Value>>(); + + row.extend(r2.into_iter().map(|v| v.clone())); + + rows.push(row); + } + + let values = rows + .into_iter() + .reduce(|mut a,b| {a.extend(b); a}) + .unwrap(); + + Ok(Matrix::new(self.domain + other.domain, self.codomain, values)) + } + + pub fn join_bottom(&self, other: &Matrix) -> Result<Self> { + if self.domain != other.domain { + return Err(error!("matrix domain's do not match")) + } + let mut values = self.values.clone(); + values.extend(other.values.clone()); + Ok(Matrix::new(self.domain, self.codomain + other.codomain, values)) + } +} + +impl PartialEq for Matrix { + fn eq(&self, other: &Self) -> bool { + if self.domain != other.domain || self.codomain != other.codomain { + return false + } + + for i in 0..self.values.len() { + if self.values[i] != other.values[i] { + return false; + } + } + + return true; + } +} + +impl Add for Matrix { + type Output = Result<Self>; + + fn add(self, rhs: Self) -> Self::Output { + if self.domain != rhs.domain || self.codomain != rhs.codomain { + return Err(error!("cannot add {self:?} + {rhs:?}")) + } + let mut res = Matrix::empty(self.domain, self.codomain); + for col in 0..self.domain { + for row in 0..self.codomain { + let add = self.get(row, col)? + rhs.get(row, col)?; + res.set(row, col, add?)?; + } + } + Ok(res) + } +} + +impl Sub for Matrix { + type Output = Result<Self>; + + fn sub(self, rhs: Self) -> Self::Output { + if self.domain != rhs.domain || self.codomain != rhs.codomain { + return Err(error!("cannot subtract {self:?} - {rhs:?}")) + } + let mut res = Matrix::empty(self.domain, self.codomain); + for col in 0..self.domain { + for row in 0..self.codomain { + let sub = self.get(row, col)? - rhs.get(row, col)?; + res.set(row, col, sub?)?; + } + } + Ok(res) + } +} + +fn dot(lhs: Vec<&Value>, rhs: Vec<&Value>) -> Result<Value> { + let len = lhs.len(); + + let mut res = Value::Int(0); + for i in 0..len { + let val = (lhs[i].clone() * rhs[i].clone())?; + res = (res + val)?; + } + + Ok(res) +} + +impl Mul for Matrix { + type Output = Result<Self>; + + fn mul(self, rhs: Self) -> Self::Output { + if self.domain != rhs.codomain { + return Err(error!("cannot multiply {self:?} * {rhs:?}")) + } + let mut res = Self::empty(rhs.domain, self.codomain); + for (i, row) in self.rows().enumerate() { + for (j, col) in rhs.cols().enumerate() { + let dot = dot(row.clone(), col.clone())?; + res.set(i, j, dot)?; + } + } + Ok(res) + } +} + +pub struct MatrixRows<'a> { + matrix: &'a Matrix, + row: usize +} + +impl<'a> Iterator for MatrixRows<'a> { + type Item = Vec<&'a Value>; + + fn next(&mut self) -> Option<Self::Item> { + if self.row >= self.matrix.codomain { + return None + } + + let row_start = self.row * self.matrix.domain; + let row_end = row_start + self.matrix.domain; + + let res = self.matrix.values + .iter() + .enumerate() + .filter(|(idx, _)| *idx >= row_start && *idx < row_end) + .map(|v| v.1) + .collect(); + + self.row += 1; + + Some(res) + } +} + +pub struct MatrixCols<'a> { + matrix: &'a Matrix, + col: usize +} + +impl<'a> Iterator for MatrixCols<'a> { + type Item = Vec<&'a Value>; + + fn next(&mut self) -> Option<Self::Item> { + if self.col >= self.matrix.domain { + return None + } + + let res = self.matrix.values + .iter() + .enumerate() + .filter(|(idx, _)| *idx % self.matrix.domain == self.col) + .map(|v| v.1) + .collect(); + + self.col += 1; + + Some(res) + } +} diff --git a/matrix-lang/src/value/mod.rs b/matrix-lang/src/value/mod.rs new file mode 100644 index 0000000..9094bb6 --- /dev/null +++ b/matrix-lang/src/value/mod.rs @@ -0,0 +1,42 @@ +pub mod comp; +pub mod gc; +pub mod matrix; +pub mod hash; +pub mod exception; +pub mod function; +pub mod fmt; +pub mod index; +pub mod clone; + +use crate::prelude::*; + +#[derive(Clone)] +pub enum Value { + Nil, + + Bool(bool), + Int(i64), + Float(f64), + Ratio(Rational64), + Complex(Complex64), + + Regex(Rc<Regex>), + String(Rc<str>), + + List(Gc<Vec<Value>>), + Matrix(Gc<Matrix>), + Table(Gc<ValueMap>), + + Function(Rc<Function>), + Range(Rc<(i64, i64, bool)>), + Iter(Rc<Function>), + File(Rc<RefCell<File>>), + + Exception(Exception), +} + +impl From<&str> for Value { + fn from(value: &str) -> Self { + Value::String(Rc::from(value)) + } +} diff --git a/matrix-lang/src/value/value.rs b/matrix-lang/src/value/value.rs new file mode 100644 index 0000000..10d8398 --- /dev/null +++ b/matrix-lang/src/value/value.rs @@ -0,0 +1,522 @@ +use std::{ + collections::HashMap, + rc::Rc, + hash::Hash, + fmt::{Display, Debug}, + ops::{Add, Neg, Not, Sub, Div, Mul, BitOr, BitAnd, BitXor, Shl, Shr}, + cmp::Ordering, + cell::RefCell, fs::File +}; + +use crate::iter; +use num_complex::Complex64; +use num_rational::Rational64; +use regex::Regex; + +use crate::{ast::{Expr, BinaryOp, UnaryOp}, chunk::Function, Result, gc::Gc}; + + +pub type InlineList = Vec<Expr>; +pub type InlineMatrix = (usize, usize, Vec<Expr>); +pub type InlineTable = Vec<(Expr, Expr)>; + +#[derive(Debug)] +pub struct Error(String); + +impl Display for self::Error { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}", self.0) + } +} + +impl std::error::Error for self::Error {} + +macro_rules! error { + ($($arg:tt)*) => { + Err(self::Error(format!($($arg)*)).into()) + }; +} + + +impl From<&str> for Value { + fn from(value: &str) -> Self { + Value::String(value.into()) + } +} + + +impl Debug for Value { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + use Value as V; + match self { + V::Nil => write!(f, "[Nil]"), + V::Bool(b) => write!(f, "[Bool {b}]"), + V::Int(i) => write!(f, "[Int {i}]"), + V::Float(vf) => write!(f, "[Float {vf}]"), + V::Ratio(r) => write!(f, "[Ratio {r}]"), + V::Complex(c) => write!(f, "[Complex {c}]"), + V::Regex(r) => write!(f, "[Regex /{r}/]"), + V::String(s) => write!(f, "[String '{s}']"), + V::List(l) => write!(f, "[List {}]", l.len()), + V::Matrix(m) => write!(f, "[Matirx {}x{}]", m.domain, m.codomain), + V::Table(t) => write!(f, "[Table {}]", t.0.len()), + V::Function(vf) => write!(f, "[Function {}]", vf.name), + V::Range(r) => write!(f, "[Range {:?}..{:?}]", r.0, r.1), + V::Iter(_) => write!(f, "[Iterator]"), + V::Error(_) => write!(f, "[Error]"), + V::File(_) => write!(f, "[File]"), + } + } +} + +impl Display for Value { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + use Value as V; + + let red; + let green; + let yellow; + let blue; + let pink; + let cyan; + let clear; + + if f.alternate() { + red = "\x1b[31m"; + green = "\x1b[32m"; + yellow = "\x1b[33m"; + blue = "\x1b[34m"; + pink = "\x1b[35m"; + cyan = "\x1b[36m"; + clear = "\x1b[0m"; + } else { + red = ""; + green = ""; + yellow = ""; + blue = ""; + pink = ""; + cyan = ""; + clear = ""; + } + + match self { + V::Nil => {write!(f, "{blue}nil{clear}")?;}, + V::Bool(b) => {write!(f, "{yellow}{b}{clear}")?;}, + V::Int(i) => {write!(f, "{yellow}{i}{clear}")?;}, + V::Float(l) => {write!(f, "{yellow}{l}{clear}")?;}, + V::Ratio(r) => {write!(f, "{yellow}{r}{clear}")?;}, + V::Complex(c) => {write!(f, "{yellow}{c}{clear}")?;}, + V::Regex(r) => {write!(f, "/{red}{r}{clear}/")?;}, + V::String(s) => { + if f.alternate() { + write!(f, "{green}'{s}'{clear}")?; + } else { + write!(f, "{s}")?; + } + } + V::List(l) => { + write!(f, "[")?; + for (i, el) in l.iter().enumerate() { + if i != 0 { + write!(f, " ")?; + } + if f.alternate() { + write!(f, "{el:#}")?; + } else { + write!(f, "{el}")?; + } + } + write!(f, "]")?; + }, + V::Matrix(m) => { + if f.alternate() { + write!(f, "{m:#}")?; + } else { + write!(f, "{m}")?; + } + }, + V::Table(t) => { + write!(f, "{{")?; + for (i, (key, val)) in t.0.iter().enumerate() { + if i != 0 { + write!(f, ", ")?; + } + if f.alternate() { + write!(f, "{key:#} = {val:#}")?; + } else { + write!(f, "{key} = {val}")?; + } + } + write!(f, "}}")?; + }, + V::Function(fun) => { + use crate::chunk::InnerFunction as F; + match fun.fun { + F::Compiled(_) => write!(f, "{cyan}[Function {}]{clear}", fun.name)?, + F::Native(_) => write!(f, "{cyan}[Builtin {}]{clear}", fun.name)?, + }; + }, + V::Range(r) => { + if f.alternate() { + write!(f, "{:#}..{:#}", r.0, r.1)?; + } else { + write!(f, "{}..{}", r.0, r.1)?; + } + } + V::Iter(_) => {write!(f, "{pink}[Iterator]{clear}")?;}, + V::File(_) => {write!(f, "{pink}[File]{clear}")?;}, + V::Error(e) => {write!(f, "{red}{e}{clear}")?;}, + }; + Ok(()) + } +} + +impl Value { + pub fn can_hash(&self) -> Result<()> { + use Value::*; + match self { + Nil => {}, + Bool(_) => {}, + Int(_) => {}, + Ratio(_) => {}, + Regex(_) => {}, + String(_) => {} + List(l) => { + for val in l.iter() { + val.can_hash()?; + } + } + Matrix(m) => { + for val in m.values.iter() { + val.can_hash()?; + } + }, + _ => return error!("cannot hash {self:?}") + } + Ok(()) + } + + pub fn is_zero(&self) -> bool { + use Value as V; + match self { + V::Int(i) => *i == 0, + V::Float(f) => *f == 0.0 || *f == -0.0, + V::Ratio(r) => *r.numer() == 0, + _ => false, + } + } +} + + +impl Value { + pub fn val_cmp(&self, other: &Self) -> Result<Ordering> { + self.partial_cmp(other) + .map_or_else(|| error!("cannot compare: {self:?} and {other:?}"), Ok) + } + + fn index_single(&self, index: &Value) -> Result<Self> { + use Value as V; + match (self, index) { + (V::Table(t), index) => { + Ok(t.get(index)?.unwrap_or(&Value::Nil).clone()) + }, + (V::List(l), V::Int(i)) => { + if *i < 0 || *i as usize >= l.len() { + return error!("{i} out of bounds for {self:?}") + } + Ok(l[*i as usize].clone()) + }, + (V::Matrix(m), V::Int(i)) => { + if *i < 0 || *i as usize >= m.values.len() { + return error!("{i} out of bounds for {self:?}") + } + Ok(m.values[*i as usize].clone()) + }, + _ => return error!("{index:?} cant index {self:?}") + } + } + + fn index_multiple(&self, indexes: &Vec<Value>) -> Result<Self> { + use Value as V; + match self { + V::List(..) => { + let mut ret = Vec::new(); + for index in indexes { + let res = self.index_single(index)?; + ret.push(res); + } + Ok(V::List(ret.into())) + } + V::Table(..) => { + let mut ret = ValueMap::new(); + for index in indexes { + let res = self.index_single(index)?; + ret.insert(index.clone(), res)?; + } + Ok(V::Table(ret.into())) + } + V::Matrix(m) => { + let err = || error!("{self:?} can be index by [Int] or [Int;Int]"); + if indexes.len() != 2 { + return err() + } + let lhs = indexes[0].clone(); + let rhs = indexes[1].clone(); + match (lhs, rhs) { + (V::Nil, V::Nil) => { + Ok(V::Matrix(m.clone_inside())) + }, + (V::Int(row), V::Nil) => { + let Some((_, row)) = m.rows().enumerate().filter(|(idx, _)| *idx as i64 == row).next() else { + return err(); + }; + let row: Vec<Value> = row.into_iter().map(|e| e.clone()).collect(); + Ok(V::Matrix(Matrix::new(row.len(), 1, row).into())) + }, + (V::Nil, V::Int(col)) => { + let Some((_, col)) = m.cols().enumerate().filter(|(idx, _)| *idx as i64 == col).next() else { + return err(); + }; + let col: Vec<Value> = col.into_iter().map(|e| e.clone()).collect(); + Ok(V::Matrix(Matrix::new(1, col.len(), col).into())) + }, + (V::Int(row), V::Int(col)) => { + if row < 0 || col < 0 { + return err(); + } + m.get(row as usize, col as usize) + } + _ => return err() + } + } + _ => return error!("cannot index {self:?}") + } + } + + pub fn index(&self, index: &Vec<Value>) -> Result<Self> { + if index.len() == 0 { + Ok(self.clone_inside()) + } else if index.len() == 1 { + self.index_single(&index[0]) + } else { + self.index_multiple(index) + } + } + + fn store_index_single(&mut self, index: &Value, store: Value) -> Result<()> { + use Value as V; + let err = format!("{self:?}"); + match (self, index) { + (V::Table(t), index) => { + t.insert(index.clone(), store) + }, + (V::List(l), V::Int(i)) => { + if *i < 0 || *i as usize >= l.len() { + return error!("{i} out of bounds for {err}") + } + l[*i as usize] = store; + Ok(()) + }, + (V::Matrix(m), V::Int(i)) => { + if *i < 0 || *i as usize >= m.values.len() { + return error!("{i} out of bounds for {err}") + } + m.values[*i as usize] = store; + Ok(()) + }, + _ => return error!("{index:?} cant index {err}") + } + } + + fn store_index_multiple(&mut self, indexes: &Vec<Value>, store: Value) -> Result<()> { + use Value as V; + match self { + V::List(..) => { + for index in indexes { + self.store_index_single(index, store.clone())?; + } + Ok(()) + } + V::Table(..) => { + for index in indexes { + self.store_index_single(index, store.clone())?; + } + Ok(()) + } + _ => return error!("cannot index {self:?}") + } + } + + pub fn store_index(&mut self, index: &Vec<Value>, store: Value) -> Result<()> { + if index.len() == 0 { + Ok(()) + } else if index.len() == 1 { + self.store_index_single(&index[0], store) + } else { + self.store_index_multiple(index, store) + } + } + + pub fn store_field_access(&mut self, ident: &str, val: Value) -> Result<()> { + use Value as V; + match self { + V::Table(t) => { + let key = V::String(Rc::from(ident)); + Ok(t.insert(key, val)?) + }, + _ => return error!("cannot field access assign {self:?}") + } + } + + pub fn field_access(&self, ident: &str) -> Result<Self> { + use Value as V; + match self { + V::Table(t) => { + let key = V::String(Rc::from(ident)); + Ok(t.get(&key)?.unwrap_or(&V::Nil).clone()) + }, + _ => return error!("cannot field access {self:?}") + } + } + + pub fn binary_op(op: BinaryOp, lhs: Value, rhs: Value) -> Result<Self> { + use BinaryOp::*; + match op { + Add => lhs + rhs, + Subtract => lhs - rhs, + Multiply => lhs * rhs, + Divide => lhs / rhs, + Modulo => lhs.modulo(rhs), + Power => lhs.pow(rhs), + BitwiseAnd => lhs & rhs, + BitwiseOr => lhs | rhs, + BitwiseXor => lhs ^ rhs, + BitwiseShiftLeft => lhs << rhs, + BitwiseShiftRight => lhs >> rhs, + Equals => Ok(Self::Bool(lhs == rhs)), + NotEquals => Ok(Self::Bool(lhs != rhs)), + GreaterEquals => Ok(Self::Bool(lhs >= rhs)), + LessEquals => Ok(Self::Bool(lhs <= rhs)), + GreaterThan => Ok(Self::Bool(lhs > rhs)), + LessThan => Ok(Self::Bool(lhs < rhs)), + Range | RangeEq => { + let Value::Int(lhs) = lhs else { + return error!("range can only take [Int]'s") + }; + let Value::Int(rhs) = rhs else { + return error!("range can only take [Int]'s") + }; + Ok(Self::Range(Rc::new((lhs, rhs, op == RangeEq)))) + }, + } + } + + pub fn unary_op(op: UnaryOp, val: Value) -> Value { + use UnaryOp::*; + match op { + Negate => -val, + Not => Self::Bool(!val), + } + } +} + +impl Neg for Value { + type Output = Value; + + fn neg(self) -> Self::Output { + use Value::*; + match self { + Bool(b) => Bool(!b), + Int(i) => Int(-i), + Float(f) => Float(-f), + Ratio(r) => Ratio(-r), + Complex(c) => Complex(-c), + _ => return Float(f64::NAN) + } + } +} + +impl Not for Value { + type Output = bool; + + fn not(self) -> Self::Output { + use Value as V; + match self { + V::Nil => true, + V::Bool(b) => !b, + V::Int(i) => i == 0, + V::Float(f) => f == 0.0, + V::Ratio(r) => *(r.numer()) == 0 || *(r.denom()) == 0, + V::Complex(c) => !c.is_normal(), + V::Regex(_) => false, + V::List(_) => false, + V::Matrix(_) => false, + V::Table(_) => false, + V::String(s) => s.as_ref() == "", + V::Function(_) => false, + V::Iter(_) => false, + V::Range(_) => false, + V::File(_) => false, + V::Error(_) => false, + } + } +} + +impl Value { + + pub fn into_iter_fn(self) -> Result<Rc<Function>> { + let Value::Iter(iter) = self.into_iter()? else { + return error!("bypassed iter check") + }; + Ok(iter) + } + + pub fn into_iter(self) -> Result<Self> { + use Value as V; + Ok(match self { + V::Iter(..) => self, + V::List(l) => { + let iter = RefCell::new(l.into_inner().into_iter()); + iter!(move |_,_| { + match iter.borrow_mut().next() { + Some(v) => Ok(v), + None => Ok(V::Nil), + } + }) + }, + V::Range(r) => { + let r = (*r).clone(); + let lhs = RefCell::new(r.0); + let rhs = r.1; + iter!(move |_,_| { + let val = *lhs.borrow(); + let next = *lhs.borrow() + 1; + if (!r.2 && *lhs.borrow() < rhs) || (r.2 && *lhs.borrow() <= rhs) { + *lhs.borrow_mut() = next; + return Ok(Value::Int(val)) + } + Ok(Value::Nil) + }) + }, + V::Function(f) => { + if f.arity > 0 || f.variadic { + return error!("iterator functions cannot be varadic or take arguments") + } + V::Iter(f) + }, + val => return error!("cannot turn {val:?} into an iterator") + }) + } +} + +fn dot(lhs: Vec<&Value>, rhs: Vec<&Value>) -> Result<Value> { + let len = lhs.len(); + + let mut res = Value::Int(0); + for i in 0..len { + let val = (lhs[i].clone() * rhs[i].clone())?; + res = (res + val)?; + } + + Ok(res) +} diff --git a/matrix-lang/src/vm.rs b/matrix-lang/src/vm.rs new file mode 100644 index 0000000..bac6341 --- /dev/null +++ b/matrix-lang/src/vm.rs @@ -0,0 +1,461 @@ +use std::{fmt::Display, ops::{IndexMut, Index}, sync::{atomic::{AtomicUsize, Ordering}, Arc}, collections::HashMap}; +use crate::prelude::*; + +pub struct Stack<T> { + inner: Vec<T> +} + +impl<T> Stack<T> { + pub fn new() -> Self { + Self { inner: vec![] } + } + + pub fn pop(&mut self) -> T { + self.inner.pop().expect("stack empty") + } + + pub fn push(&mut self, val: T) { + self.inner.push(val) + } + + pub fn split_off(&mut self, len: usize) -> Self { + let inner = self.inner.split_off(len); + Self { inner } + } + + pub fn truncate(&mut self, len: usize) { + self.inner.truncate(len); + } + + pub fn len(&self) -> usize { + self.inner.len() + } +} + +impl<T: Display> Display for Stack<T> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f,"[ ")?; + for (i, el) in self.inner.iter().enumerate() { + if i != 0 { + write!(f, ", ")?; + } + write!(f, "{el}")?; + } + write!(f, " ]")?; + Ok(()) + } +} + +impl<T> IndexMut<usize> for Stack<T> { + fn index_mut(&mut self, index: usize) -> &mut Self::Output { + &mut self.inner[index] + } +} + +impl<T> Index<usize> for Stack<T> { + type Output = T; + + fn index(&self, index: usize) -> &Self::Output { + &self.inner[index] + } +} + +#[derive(Clone)] +pub struct StackFrame { + #[allow(dead_code)] + name: Rc<str>, + body: Rc<Chunk>, + ip: usize, + bp: usize, + lp: usize, + depth: usize, +} + +struct VmError { + err: Exception, + frames: Vec<StackFrame> +} + +impl From<Exception> for VmError { + fn from(err: Exception) -> Self { + VmError { + err, + frames: Vec::new() + } + } +} + +type VmResult<T> = std::result::Result<T, VmError>; + +impl StackFrame { + fn new(vm: &Vm, name: Rc<str>, body: Rc<Chunk>, arity: usize, depth: usize) -> Self { + Self { + name, + body, + bp: vm.stack.len() - arity, + lp: vm.locals.len(), + ip: 0, + depth + } + } +} + +impl Default for StackFrame { + fn default() -> Self { + StackFrame { + name: Rc::from("<root>"), + body: Rc::new(Chunk::default()), + bp: 0, + lp: 0, + ip: 0, + depth: 0 + } + } +} + +pub enum Interupt { + KeyboardInterupt = 1 +} + +struct TryScope { + stack_len: usize, + locals_len: usize, + frame_depth: usize, + err_idx: usize, +} + +pub struct Vm { + stack: Stack<Value>, + locals: Stack<Value>, + trystack: Vec<TryScope>, + globals: Rc<RefCell<HashMap<u16, Value>>>, + names: NamesTable, + global_names: GlobalsTable, + interupt: Arc<AtomicUsize>, +} + +macro_rules! error { + ($($arg:tt)*) => { + exception!(RUNTIME_EXCEPTION, $($arg)*) + }; +} + +impl Vm { + + fn push(&mut self, val: Value) { + self.stack.push(val) + } + + fn pop(&mut self) -> Value { + self.stack.pop() + } + + fn top(&mut self) -> Value { + self.stack[self.stack.len() - 1].clone() + } + + pub fn names(&self) -> NamesTable { + self.names.clone() + } + + pub fn globals(&self) -> GlobalsTable { + self.global_names.clone() + } + + pub fn interupt(&self) -> Arc<AtomicUsize> { + self.interupt.clone() + } + + pub fn new() -> Self { + Self { + stack: Stack::new(), + locals: Stack::new(), + trystack: Vec::new(), + globals: Rc::new(RefCell::new(HashMap::new())), + names: Rc::new(RefCell::new(Vec::new())), + global_names: Rc::new(RefCell::new(Vec::new())), + interupt: Arc::new(AtomicUsize::new(0)), + } + } + + pub fn load_global(&mut self, value: Value, name: &str) { + let idx = self.global_names.borrow().len(); + self.global_names.borrow_mut().push(Global { idx, name: Rc::from(name), is_const: true }); + self.globals.borrow_mut().insert(idx as u16, value); + } + + pub fn load_global_fn(&mut self, value: Rc<Function>, name: &str) { + self.load_global(Value::Function(value), name) + } + + fn init_frame(&mut self, fun: Rc<Function>) -> Result<StackFrame> { + let InnerFunction::Compiled(ref compiled_chunk) = fun.fun else { + return Err(error!("cannot create stack frame on builtin function")) + }; + Ok(StackFrame::new( + self, + fun.name.clone(), + compiled_chunk.clone(), + fun.arity, + 0 + )) + } + + fn check_interupt(&self) -> bool { + self.interupt.load(Ordering::Relaxed) != 0 + } + + fn exec_ins(&mut self, frame: &mut StackFrame, ins: Instruction) -> VmResult<Option<Value>> { + use Instruction as I; + match ins { + I::NoOp => {}, + I::CreateLocal => self.locals.push(self.stack.pop()), + I::LoadLocal(idx) => {self.stack.push(self.locals[frame.lp + idx as usize].clone());}, + I::StoreLocal(idx) => self.locals[frame.bp + idx as usize] = self.pop(), + I::DiscardLocals(count) => {self.locals.truncate(self.locals.len() - count as usize)}, + I::LoadGlobal(idx) => { + let val = self.globals + .borrow_mut() + .get(&idx) + .unwrap() + .clone(); + self.stack.push(val); + }, + I::StoreGlobal(idx) => { + let val = self.pop(); + self.globals.borrow_mut().insert(idx, val); + }, + I::Const(idx) => self.push(frame.body.constants[idx as usize].clone()), + I::Int(i) => self.push(Value::Int(i as i64)), + I::True => self.push(Value::Bool(true)), + I::False => self.push(Value::Bool(false)), + I::Nil => self.push(Value::Nil), + I::Dup => self.push(self.stack[self.stack.len() - 1].clone()), + I::Discard(count) => {self.stack.truncate(self.stack.len() - count as usize)}, + I::UnaryOp(op) => { + let val = self.pop(); + self.push(Value::unary_op(op, val)); + }, + I::BinaryOp(op) => { + let rhs = self.pop(); + let lhs = self.pop(); + self.push(Value::binary_op(op, lhs, rhs)?); + }, + I::NewList(items) => { + let list = self.stack.split_off(self.stack.len() - items as usize); + self.push(Value::List(list.inner.into())); + }, + I::NewTable(items) => { + let mut table = ValueMap::new(); + for _ in 0..items { + let value = self.pop(); + let key = self.pop(); + table.insert(key, value)?; + } + self.push(Value::Table(table.into())) + }, + I::NewMatrix(items, domain) => { + let values = self.stack.split_off(self.stack.len() - items as usize).inner; + let domain = domain as usize; + let codomain = values.len() / domain; + self.push(Value::Matrix(Gc::new(Matrix::new(domain, codomain, values)))); + } + I::Jump(idx) => { + if self.check_interupt() { + return Ok(Some(Value::Nil)) + } + frame.ip = idx as usize; + } + I::JumpTrue(idx) => { + if self.check_interupt() { + return Ok(Some(Value::Nil)) + } + if !!self.pop() { + frame.ip = idx as usize; + } + }, + I::JumpFalse(idx) => { + if self.check_interupt() { + return Ok(Some(Value::Nil)) + } + if !self.pop() { + frame.ip = idx as usize; + } + }, + I::JumpNil(idx) => { + if self.check_interupt() { + return Ok(Some(Value::Nil)) + } + if self.pop() == Value::Nil { + frame.ip = idx as usize; + } + }, + I::Call(arity) => { + let arity = arity as usize; + + let fun = self.pop(); + let Value::Function(fun) = fun else { + Err(error!("cannot call {fun} (not a function)"))? + }; + + if !fun.variadic && arity > fun.arity { + let needs = fun.arity; + Err(error!("function {fun} takes {needs} args, given {arity}"))? + } + + let mut params = self.stack.split_off(self.stack.len() - arity).inner; + + if params.len() < fun.arity { + let new_arity = fun.arity - arity; + let val = native!("<partial>", new_arity, false, move |(vm, vm_frame), args| { + let mut params = params.clone(); + params.extend(args); + vm.exec_fn(vm_frame, fun.clone(), params).map_err(|e| e.err) + }); + self.stack.push(val); + return Ok(None); + } + + if fun.variadic { + if arity == fun.arity { + params.push(Value::List(vec![].into())); + } else { + let count = arity - fun.arity; + let varadic_params = params.split_off(params.len() - count); + params.push(Value::List(varadic_params.into())); + } + } + + let res = self.exec_fn(frame, fun, params)?; + self.push(res); + }, + I::Return => { + if self.check_interupt() { + return Ok(Some(Value::Nil)) + } + let ret = self.pop(); + self.stack.truncate(frame.bp); + self.locals.truncate(frame.lp); + return Ok(Some(ret)) + }, + I::Field(name_idx) => { + let expr = self.pop(); + let name = self.names.borrow()[name_idx as usize].clone(); + self.push(expr.field_access(&name)?); + }, + I::StoreField(name_idx) => { + let mut expr = self.pop(); + let value = self.pop(); + let name = self.names.borrow()[name_idx as usize].clone(); + expr.store_field_access(&name, value)?; + }, + I::Index(count) => { + let index = self.stack.split_off(self.stack.len() - count as usize); + let collection = self.pop(); + let value = collection.index(&index.inner)?; + self.stack.push(value); + }, + I::StoreIndex(count) => { + let index = self.stack.split_off(self.stack.len() - count as usize); + let mut collection = self.pop(); + let value = self.pop(); + collection.store_index(&index.inner, value)?; + }, + I::IterCreate => { + let val = self.pop().into_iter(); + self.push(val?); + }, + I::IterNext => { + let Value::Iter(iter) = self.top() else { panic!("bypassed iter check"); }; + let val = self.exec_fn(frame, iter, vec![])?; + self.push(val); + }, + I::Try(idx) => { + let scope = TryScope { + err_idx: idx as usize, + frame_depth: frame.depth, + stack_len: self.stack.len(), + locals_len: self.locals.len(), + }; + self.trystack.push(scope); + }, + I::TryEnd => { + self.trystack.pop().unwrap(); + }, + }; + + Ok(None) + } + + fn stack_trace(&mut self, frames: Vec<StackFrame>, e: Exception) -> Exception { + let mut e = e; + for frame in frames { + let ip = frame.ip - 1; + let pos = frame.body.pos[ip]; + e = e.trace(frame.name, pos); + } + e + } + + fn exec_fn(&mut self, frame: &mut StackFrame, fun: Rc<Function>, params: Vec<Value>) -> VmResult<Value> { + if self.check_interupt() { + return Ok(Value::Nil) + } + let name = fun.name.clone(); + let params_len = params.len(); + match &fun.fun { + InnerFunction::Compiled(body) => { + for param in params { + self.stack.push(param); + } + let mut new_frame = StackFrame::new(self, name, body.clone(), params_len, frame.depth + 1); + let res = self.exec(&mut new_frame); + res + }, + InnerFunction::Native(native_fun) => { + Ok(native_fun((self, frame), params)?) + } + } + } + + fn exec(&mut self, frame: &mut StackFrame) -> VmResult<Value> { + loop { + let ins = frame.body.code[frame.ip].clone(); + frame.ip += 1; + match self.exec_ins(frame, ins) { + Ok(Some(val)) => return Ok(val), + Ok(None) => {}, + Err(err) => { + if let Some(catch) = self.trystack.pop() { + if frame.depth != catch.frame_depth { + self.trystack.push(catch); + return Err(err); + } + self.stack.truncate(catch.stack_len); + self.locals.truncate(catch.locals_len); + frame.ip = catch.err_idx; + self.stack.push(Value::Exception(err.err)); + } else { + let mut err = err; + err.frames.push(frame.clone()); + return Err(err) + } + }, + } + } + } + + pub fn run_fn(&mut self, frame: &mut StackFrame, fun: Rc<Function>, params: Vec<Value>) -> Result<Value> { + self.exec_fn(frame, fun, params).map_err(|e| e.err) + } + + pub fn run(&mut self, fun: Rc<Function>) -> Result<Value> { + self.interupt.store(0, Ordering::SeqCst); + self.stack = Stack::new(); + self.locals = Stack::new(); + let mut frame = self.init_frame(fun)?; + self.exec(&mut frame).map_err(|e| { + self.stack_trace(e.frames, e.err) + }) + } +} |