From 311d3ae9a3b0a014e14e885ddbdf35a6c1cfd3ce Mon Sep 17 00:00:00 2001
From: Rose Hogenson <rosehogenson@posteo.net>
Date: Thu, 30 May 2024 23:50:59 -0700
Subject: Add bytecode.

A recursive AST is kind of annoying to evaluate without recursion.
Bytecode is cooler anyway.
---
 src/parser.rs | 258 +++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 167 insertions(+), 91 deletions(-)

(limited to 'src/parser.rs')

diff --git a/src/parser.rs b/src/parser.rs
index 6eeb9d8..4cd75be 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -1,18 +1,20 @@
 use crate::eval::Num;
-use crate::expr::{BinOp, Expr, UnOp};
 use crate::lexer::Lexer;
+use crate::op::{BinOp, Op, UnOp};
 use std::str::FromStr;
 
-enum Op {
+enum Pending {
     Paren,
     Un(UnOp),
-    Bin(BinOp, Expr),
+    Bin(BinOp),
 }
 
 struct Parser<'a> {
     r: Lexer<'a>,
     first_token: Option<&'a str>,
-    stack: Vec<Op>,
+    // stack stores the pending operations that can't be flushed yet.
+    stack: Vec<Pending>,
+    result: Vec<Op>,
 }
 
 impl<'a> Parser<'a> {
@@ -43,89 +45,93 @@ impl<'a> Parser<'a> {
         true
     }
 
-    fn parse_num(&mut self) -> Option<Num> {
+    fn parse_num(&mut self) -> Option<()> {
         let t = self.next()?;
         if t.contains('.') || t.contains('e') || t.contains('E') {
             let Ok(f) = f64::from_str(t) else {
                 return None;
             };
-            return Some(Num::Float(f));
+            self.result.push(Op::Num(Num::Float(f)));
+            return Some(());
         }
         let Ok(i) = i128::from_str(t) else {
             return None;
         };
-        Some(Num::Int(i))
+        self.result.push(Op::Num(Num::Int(i)));
+        Some(())
     }
 
-    fn parse_const(&mut self) -> Option<Num> {
+    fn parse_const(&mut self) -> Option<()> {
         if self.symbol("e") {
-            return Some(Num::Float(std::f64::consts::E));
+            self.result.push(Op::Num(Num::Float(std::f64::consts::E)));
+            return Some(());
         }
         if self.symbol("pi") {
-            return Some(Num::Float(std::f64::consts::PI));
+            self.result.push(Op::Num(Num::Float(std::f64::consts::PI)));
+            return Some(());
         }
         self.parse_num()
     }
 
     fn parse_fun(&mut self) -> bool {
         if self.symbol("-") {
-            self.stack.push(Op::Un(UnOp::Neg));
+            self.stack.push(Pending::Un(UnOp::Neg));
             return true;
         }
         if self.symbol("sin") {
-            self.stack.push(Op::Un(UnOp::Sin));
+            self.stack.push(Pending::Un(UnOp::Sin));
             return true;
         }
         if self.symbol("cos") {
-            self.stack.push(Op::Un(UnOp::Cos));
+            self.stack.push(Pending::Un(UnOp::Cos));
             return true;
         }
         if self.symbol("tan") {
-            self.stack.push(Op::Un(UnOp::Tan));
+            self.stack.push(Pending::Un(UnOp::Tan));
             return true;
         }
         if self.symbol("asin") || self.symbol("arcsin") {
-            self.stack.push(Op::Un(UnOp::Asin));
+            self.stack.push(Pending::Un(UnOp::Asin));
             return true;
         }
         if self.symbol("acos") || self.symbol("arccos") {
-            self.stack.push(Op::Un(UnOp::Acos));
+            self.stack.push(Pending::Un(UnOp::Acos));
             return true;
         }
         if self.symbol("atan") || self.symbol("arctan") {
-            self.stack.push(Op::Un(UnOp::Atan));
+            self.stack.push(Pending::Un(UnOp::Atan));
             return true;
         }
         if self.symbol("sqrt") {
-            self.stack.push(Op::Un(UnOp::Sqrt));
+            self.stack.push(Pending::Un(UnOp::Sqrt));
             return true;
         }
         if self.symbol("log") || self.symbol("ln") {
-            self.stack.push(Op::Un(UnOp::Log));
+            self.stack.push(Pending::Un(UnOp::Log));
             return true;
         }
         if self.symbol("log10") {
-            self.stack.push(Op::Un(UnOp::Log10));
+            self.stack.push(Pending::Un(UnOp::Log10));
             return true;
         }
         if self.symbol("log2") {
-            self.stack.push(Op::Un(UnOp::Log2));
+            self.stack.push(Pending::Un(UnOp::Log2));
             return true;
         }
         if self.symbol("floor") {
-            self.stack.push(Op::Un(UnOp::Floor));
+            self.stack.push(Pending::Un(UnOp::Floor));
             return true;
         }
         if self.symbol("ceil") || self.symbol("ceiling") {
-            self.stack.push(Op::Un(UnOp::Ceil));
+            self.stack.push(Pending::Un(UnOp::Ceil));
             return true;
         }
         if self.symbol("round") {
-            self.stack.push(Op::Un(UnOp::Round));
+            self.stack.push(Pending::Un(UnOp::Round));
             return true;
         }
         if self.symbol("abs") {
-            self.stack.push(Op::Un(UnOp::Abs));
+            self.stack.push(Pending::Un(UnOp::Abs));
             return true;
         }
         false
@@ -145,134 +151,135 @@ fn prec(op: BinOp) -> i8 {
 }
 
 impl<'a> Parser<'a> {
-    fn eval(&mut self, e: Expr, target_prec: i8) -> Expr {
-        let mut e = e;
+    fn flush(&mut self, target_prec: i8) {
         loop {
             match self.stack.last() {
-                None | Some(Op::Paren) => break,
-                Some(Op::Bin(op, _)) if prec(*op) < target_prec => break,
+                None | Some(Pending::Paren) => break,
+                Some(Pending::Bin(op)) if prec(*op) < target_prec => break,
                 _ => (),
             }
             match self.stack.pop().unwrap() {
-                Op::Un(op) => e = op.expr(e),
-                Op::Bin(op, e1) => e = op.expr(e1, e),
-                Op::Paren => unreachable!(),
+                Pending::Un(op) => self.result.push(Op::Un(op)),
+                Pending::Bin(op) => self.result.push(Op::Bin(op)),
+                Pending::Paren => unreachable!(),
             }
         }
-        e
     }
 
-    fn parse_op(&mut self, e: Expr) {
+    fn parse_op(&mut self) {
         if self.symbol("^") {
-            let e = self.eval(e, 3);
-            self.stack.push(Op::Bin(BinOp::Pow, e));
+            self.flush(3);
+            self.stack.push(Pending::Bin(BinOp::Pow));
             return;
         }
         if self.symbol("*") {
-            let e = self.eval(e, 1);
-            self.stack.push(Op::Bin(BinOp::Mul, e));
+            self.flush(1);
+            self.stack.push(Pending::Bin(BinOp::Mul));
             return;
         }
         if self.symbol("/") {
-            let e = self.eval(e, 1);
-            self.stack.push(Op::Bin(BinOp::Div, e));
+            self.flush(1);
+            self.stack.push(Pending::Bin(BinOp::Div));
             return;
         }
         if self.symbol("//") {
-            let e = self.eval(e, 1);
-            self.stack.push(Op::Bin(BinOp::IntDiv, e));
+            self.flush(1);
+            self.stack.push(Pending::Bin(BinOp::IntDiv));
             return;
         }
         if self.symbol("%") {
-            let e = self.eval(e, 1);
-            self.stack.push(Op::Bin(BinOp::Mod, e));
+            self.flush(1);
+            self.stack.push(Pending::Bin(BinOp::Mod));
             return;
         }
         if self.symbol("+") {
-            let e = self.eval(e, 0);
-            self.stack.push(Op::Bin(BinOp::Add, e));
+            self.flush(0);
+            self.stack.push(Pending::Bin(BinOp::Add));
             return;
         }
         if self.symbol("-") {
-            let e = self.eval(e, 0);
-            self.stack.push(Op::Bin(BinOp::Sub, e));
+            self.flush(0);
+            self.stack.push(Pending::Bin(BinOp::Sub));
             return;
         }
-        let e = self.eval(e, 1);
-        self.stack.push(Op::Bin(BinOp::Mul, e));
+        self.flush(1);
+        self.stack.push(Pending::Bin(BinOp::Mul));
     }
 
-    fn parse(&mut self) -> Option<Expr> {
-        let mut e = loop {
+    fn parse(&mut self) -> Option<()> {
+        loop {
             if self.symbol("(") {
-                self.stack.push(Op::Paren);
+                self.stack.push(Pending::Paren);
                 continue;
             }
             if self.parse_fun() {
                 continue;
             }
-            let mut e = Expr::Num(self.parse_const()?);
+            self.parse_const()?;
             while self.symbol(")") {
                 loop {
                     match self.stack.pop()? {
-                        Op::Un(op) => e = op.expr(e),
-                        Op::Bin(op, e1) => e = op.expr(e1, e),
-                        Op::Paren => break,
+                        Pending::Un(op) => self.result.push(Op::Un(op)),
+                        Pending::Bin(op) => self.result.push(Op::Bin(op)),
+                        Pending::Paren => break,
                     }
                 }
             }
             if self.peek().is_none() {
-                break e;
+                break;
             }
-            self.parse_op(e);
-        };
+            self.parse_op();
+        }
         loop {
             match self.stack.pop() {
-                Some(Op::Paren) => return None,
-                Some(Op::Un(op)) => e = op.expr(e),
-                Some(Op::Bin(op, e1)) => e = op.expr(e1, e),
-                None => return Some(e),
+                Some(Pending::Paren) => return None,
+                Some(Pending::Un(op)) => self.result.push(Op::Un(op)),
+                Some(Pending::Bin(op)) => self.result.push(Op::Bin(op)),
+                None => return Some(()),
             }
         }
     }
 }
 
-pub fn parse(expr: &str) -> Option<Expr> {
+// parse turns an expression into bytecode.
+pub fn parse(expr: &str) -> Option<Vec<Op>> {
     let mut p = Parser {
         r: Lexer { buf: expr },
         first_token: None,
         stack: Vec::new(),
+        result: Vec::new(),
     };
-    p.parse()
+    p.parse()?;
+    Some(p.result)
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
 
-    fn int(i: i128) -> Expr {
-        Expr::Num(Num::Int(i))
+    fn int(i: i128) -> Op {
+        Op::Num(Num::Int(i))
     }
 
-    fn float(f: f64) -> Expr {
-        Expr::Num(Num::Float(f))
+    fn float(f: f64) -> Op {
+        Op::Num(Num::Float(f))
     }
 
     #[test]
     fn parse_int() {
-        assert_eq!(parse("500"), Some(int(500)));
+        assert_eq!(parse("500"), Some(vec![int(500)]));
     }
 
     #[test]
     fn parse_float() {
-        assert_eq!(parse("1e2"), Some(float(100.)));
+        assert_eq!(parse("1e2"), Some(vec![float(100.)]));
     }
 
     #[test]
     fn parse_fun() {
         assert_eq!(
             parse("sin pi"),
-            Some(UnOp::Sin.expr(float(std::f64::consts::PI)))
+            Some(vec![float(std::f64::consts::PI), Op::Un(UnOp::Sin)])
         );
     }
 
@@ -280,7 +287,7 @@ mod tests {
     fn parse_nested_fun() {
         assert_eq!(
             parse("log log 100"),
-            Some(UnOp::Log.expr(UnOp::Log.expr(int(100))))
+            Some(vec![int(100), Op::Un(UnOp::Log), Op::Un(UnOp::Log)])
         );
     }
 
@@ -288,7 +295,13 @@ mod tests {
     fn parse_power() {
         assert_eq!(
             parse("2^1^2"),
-            Some(BinOp::Pow.expr(int(2), BinOp::Pow.expr(int(1), int(2))))
+            Some(vec![
+                int(2),
+                int(1),
+                int(2),
+                Op::Bin(BinOp::Pow),
+                Op::Bin(BinOp::Pow)
+            ])
         );
     }
 
@@ -296,7 +309,7 @@ mod tests {
     fn parse_fun_power() {
         assert_eq!(
             parse("log 2^2"),
-            Some(BinOp::Pow.expr(UnOp::Log.expr(int(2)), int(2)))
+            Some(vec![int(2), Op::Un(UnOp::Log), int(2), Op::Bin(BinOp::Pow)])
         );
     }
 
@@ -304,7 +317,7 @@ mod tests {
     fn parse_power_fun() {
         assert_eq!(
             parse("2^log 2"),
-            Some(BinOp::Pow.expr(int(2), UnOp::Log.expr(int(2))))
+            Some(vec![int(2), int(2), Op::Un(UnOp::Log), Op::Bin(BinOp::Pow)])
         );
     }
 
@@ -312,7 +325,13 @@ mod tests {
     fn parse_pow_mul() {
         assert_eq!(
             parse("2^2*2"),
-            Some(BinOp::Mul.expr(BinOp::Pow.expr(int(2), int(2)), int(2)))
+            Some(vec![
+                int(2),
+                int(2),
+                Op::Bin(BinOp::Pow),
+                int(2),
+                Op::Bin(BinOp::Mul)
+            ])
         );
     }
 
@@ -320,7 +339,13 @@ mod tests {
     fn parse_mul_pow() {
         assert_eq!(
             parse("2*2^2"),
-            Some(BinOp::Mul.expr(int(2), BinOp::Pow.expr(int(2), int(2))))
+            Some(vec![
+                int(2),
+                int(2),
+                int(2),
+                Op::Bin(BinOp::Pow),
+                Op::Bin(BinOp::Mul)
+            ])
         );
     }
 
@@ -328,7 +353,13 @@ mod tests {
     fn parse_mul_div() {
         assert_eq!(
             parse("2*2/2"),
-            Some(BinOp::Div.expr(BinOp::Mul.expr(int(2), int(2)), int(2)))
+            Some(vec![
+                int(2),
+                int(2),
+                Op::Bin(BinOp::Mul),
+                int(2),
+                Op::Bin(BinOp::Div)
+            ])
         );
     }
 
@@ -336,7 +367,13 @@ mod tests {
     fn parse_add_mul() {
         assert_eq!(
             parse("2+2*2"),
-            Some(BinOp::Add.expr(int(2), BinOp::Mul.expr(int(2), int(2))))
+            Some(vec![
+                int(2),
+                int(2),
+                int(2),
+                Op::Bin(BinOp::Mul),
+                Op::Bin(BinOp::Add)
+            ])
         );
     }
 
@@ -344,7 +381,13 @@ mod tests {
     fn parse_mul_add() {
         assert_eq!(
             parse("2*2+2"),
-            Some(BinOp::Add.expr(BinOp::Mul.expr(int(2), int(2)), int(2)))
+            Some(vec![
+                int(2),
+                int(2),
+                Op::Bin(BinOp::Mul),
+                int(2),
+                Op::Bin(BinOp::Add)
+            ])
         );
     }
 
@@ -352,7 +395,7 @@ mod tests {
     fn parse_fun_add() {
         assert_eq!(
             parse("log 2+2"),
-            Some(BinOp::Add.expr(UnOp::Log.expr(int(2)), int(2))),
+            Some(vec![int(2), Op::Un(UnOp::Log), int(2), Op::Bin(BinOp::Add)])
         );
     }
 
@@ -360,7 +403,13 @@ mod tests {
     fn parse_parens() {
         assert_eq!(
             parse("(1+2)*3"),
-            Some(BinOp::Mul.expr(BinOp::Add.expr(int(1), int(2)), int(3)))
+            Some(vec![
+                int(1),
+                int(2),
+                Op::Bin(BinOp::Add),
+                int(3),
+                Op::Bin(BinOp::Mul)
+            ])
         );
     }
 
@@ -368,7 +417,11 @@ mod tests {
     fn parse_implicit_multiplication() {
         assert_eq!(
             parse("2pi"),
-            Some(BinOp::Mul.expr(int(2), float(std::f64::consts::PI))),
+            Some(vec![
+                int(2),
+                float(std::f64::consts::PI),
+                Op::Bin(BinOp::Mul)
+            ])
         );
     }
 
@@ -376,7 +429,14 @@ mod tests {
     fn parse_implicit_multiplication_neg() {
         assert_eq!(
             parse("-2 2 -2"),
-            Some(BinOp::Sub.expr(BinOp::Mul.expr(UnOp::Neg.expr(int(2)), int(2)), int(2)))
+            Some(vec![
+                int(2),
+                Op::Un(UnOp::Neg),
+                int(2),
+                Op::Bin(BinOp::Mul),
+                int(2),
+                Op::Bin(BinOp::Sub)
+            ])
         );
     }
 
@@ -384,7 +444,12 @@ mod tests {
     fn parse_fun_implicit_multiplication() {
         assert_eq!(
             parse("sin 2pi"),
-            Some(BinOp::Mul.expr(UnOp::Sin.expr(int(2)), float(std::f64::consts::PI))),
+            Some(vec![
+                int(2),
+                Op::Un(UnOp::Sin),
+                float(std::f64::consts::PI),
+                Op::Bin(BinOp::Mul)
+            ])
         );
     }
 
@@ -392,7 +457,13 @@ mod tests {
     fn parse_unary_negate() {
         assert_eq!(
             parse("1---2"),
-            Some(BinOp::Sub.expr(int(1), UnOp::Neg.expr(UnOp::Neg.expr(int(2)))))
+            Some(vec![
+                int(1),
+                int(2),
+                Op::Un(UnOp::Neg),
+                Op::Un(UnOp::Neg),
+                Op::Bin(BinOp::Sub)
+            ])
         );
     }
 
@@ -400,17 +471,22 @@ mod tests {
     fn parse_negate_fun() {
         assert_eq!(
             parse("log-log 2"),
-            Some(UnOp::Log.expr(UnOp::Neg.expr(UnOp::Log.expr(int(2)))))
+            Some(vec![
+                int(2),
+                Op::Un(UnOp::Log),
+                Op::Un(UnOp::Neg),
+                Op::Un(UnOp::Log)
+            ])
         );
     }
 
     #[test]
     fn parse_unmatched_parens() {
-        assert_eq!(parse("0))))"), None,);
+        assert_eq!(parse("0))))"), None);
     }
 
     #[test]
     fn parse_unmatched_op() {
-        assert_eq!(parse("2^2+"), None,);
+        assert_eq!(parse("2^2+"), None);
     }
 }
-- 
cgit v1.3.1