about summary refs log tree commit diff
path: root/users/tazjin/rlox/src/bytecode/compiler.rs
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2021-02-27T23·13+0200
committertazjin <mail@tazj.in>2021-02-28T11·14+0000
commit995d024f03d99726de5b22bdf5aaa04a88e00b4a (patch)
tree036adadc3ca8787e7b85c74a88e4eb7d8ea8b882 /users/tazjin/rlox/src/bytecode/compiler.rs
parent0c9a7de5be0ac54f068a5f4db7eb400b3bd63282 (diff)
feat(tazjin/rlox): Wire up bytecode interpreter & print results r/2247
This makes the bytecode interpreter actually usable.

Change-Id: I24afc7ce461c6673dc42581378f6e14da7aece5c
Reviewed-on: https://cl.tvl.fyi/c/depot/+/2566
Reviewed-by: tazjin <mail@tazj.in>
Tested-by: BuildkiteCI
Diffstat (limited to 'users/tazjin/rlox/src/bytecode/compiler.rs')
-rw-r--r--users/tazjin/rlox/src/bytecode/compiler.rs287
1 files changed, 287 insertions, 0 deletions
diff --git a/users/tazjin/rlox/src/bytecode/compiler.rs b/users/tazjin/rlox/src/bytecode/compiler.rs
new file mode 100644
index 000000000000..ca56bfe7cf50
--- /dev/null
+++ b/users/tazjin/rlox/src/bytecode/compiler.rs
@@ -0,0 +1,287 @@
+use super::chunk::{self, Chunk};
+use super::errors::{Error, ErrorKind, LoxResult};
+use super::opcode::OpCode;
+use super::value::Value;
+use crate::scanner::{self, Token, TokenKind};
+
+struct Compiler<T: Iterator<Item = Token>> {
+    tokens: T,
+    chunk: Chunk,
+    panic: bool,
+    errors: Vec<Error>,
+
+    // TODO(tazjin): Restructure so that these don't need to be Option?
+    current: Option<Token>,
+    previous: Option<Token>,
+}
+
+#[derive(Debug, PartialEq, PartialOrd)]
+enum Precedence {
+    None,
+    Assignment, // =
+    Or,         // or
+    And,        // and
+    Equality,   // == !=
+    Comparison, // < > <= >=
+    Term,       // + -
+    Factor,     // * /
+    Unary,      // ! -
+    Call,       // . ()
+    Primary,
+}
+
+type ParseFn<T> = fn(&mut Compiler<T>) -> LoxResult<()>;
+
+struct ParseRule<T: Iterator<Item = Token>> {
+    prefix: Option<ParseFn<T>>,
+    infix: Option<ParseFn<T>>,
+    precedence: Precedence,
+}
+
+impl<T: Iterator<Item = Token>> ParseRule<T> {
+    fn new(
+        prefix: Option<ParseFn<T>>,
+        infix: Option<ParseFn<T>>,
+        precedence: Precedence,
+    ) -> Self {
+        ParseRule {
+            prefix,
+            infix,
+            precedence,
+        }
+    }
+}
+
+impl Precedence {
+    // Return the next highest precedence, if there is one.
+    fn next(&self) -> Self {
+        match self {
+            Precedence::None => Precedence::Assignment,
+            Precedence::Assignment => Precedence::Or,
+            Precedence::Or => Precedence::And,
+            Precedence::And => Precedence::Equality,
+            Precedence::Equality => Precedence::Comparison,
+            Precedence::Comparison => Precedence::Term,
+            Precedence::Term => Precedence::Factor,
+            Precedence::Factor => Precedence::Unary,
+            Precedence::Unary => Precedence::Call,
+            Precedence::Call => Precedence::Primary,
+            Precedence::Primary => panic!(
+                "invalid parser state: no higher precedence than Primary"
+            ),
+        }
+    }
+}
+
+fn rule_for<T: Iterator<Item = Token>>(token: &TokenKind) -> ParseRule<T> {
+    match token {
+        TokenKind::LeftParen => {
+            ParseRule::new(Some(Compiler::grouping), None, Precedence::None)
+        }
+
+        TokenKind::Minus => ParseRule::new(
+            Some(Compiler::unary),
+            Some(Compiler::binary),
+            Precedence::Term,
+        ),
+
+        TokenKind::Plus => {
+            ParseRule::new(None, Some(Compiler::binary), Precedence::Term)
+        }
+
+        TokenKind::Slash => {
+            ParseRule::new(None, Some(Compiler::binary), Precedence::Factor)
+        }
+
+        TokenKind::Star => {
+            ParseRule::new(None, Some(Compiler::binary), Precedence::Factor)
+        }
+
+        TokenKind::Number(_) => {
+            ParseRule::new(Some(Compiler::number), None, Precedence::None)
+        }
+
+        _ => ParseRule::new(None, None, Precedence::None),
+    }
+}
+
+impl<T: Iterator<Item = Token>> Compiler<T> {
+    fn compile(&mut self) -> LoxResult<()> {
+        self.advance();
+        self.expression()?;
+        self.consume(
+            &TokenKind::Eof,
+            ErrorKind::ExpectedToken("Expected end of expression"),
+        );
+
+        self.end_compiler()
+    }
+
+    fn advance(&mut self) {
+        self.previous = self.current.take();
+        self.current = self.tokens.next();
+    }
+
+    fn expression(&mut self) -> LoxResult<()> {
+        self.parse_precedence(Precedence::Assignment)
+    }
+
+    fn number(&mut self) -> LoxResult<()> {
+        if let TokenKind::Number(num) = self.previous().kind {
+            self.emit_constant(num);
+            return Ok(());
+        }
+
+        unreachable!("internal parser error: entered number() incorrectly")
+    }
+
+    fn grouping(&mut self) -> LoxResult<()> {
+        self.expression()?;
+        self.consume(
+            &TokenKind::RightParen,
+            ErrorKind::ExpectedToken("Expected ')' after expression"),
+        );
+        Ok(())
+    }
+
+    fn unary(&mut self) -> LoxResult<()> {
+        // TODO(tazjin): Avoid clone
+        let kind = self.previous().kind.clone();
+
+        // Compile the operand
+        self.parse_precedence(Precedence::Unary)?;
+
+        // Emit operator instruction
+        match kind {
+            TokenKind::Minus => self.emit_op(OpCode::OpNegate),
+            _ => unreachable!("only called for unary operator tokens"),
+        }
+
+        Ok(())
+    }
+
+    fn binary(&mut self) -> LoxResult<()> {
+        // Remember the operator
+        let operator = self.previous().kind.clone();
+
+        // Compile the right operand
+        let rule: ParseRule<T> = rule_for(&operator);
+        self.parse_precedence(rule.precedence)?;
+
+        // Emit operator instruction
+        match operator {
+            TokenKind::Minus => self.emit_op(OpCode::OpSubtract),
+            TokenKind::Plus => self.emit_op(OpCode::OpAdd),
+            TokenKind::Star => self.emit_op(OpCode::OpMultiply),
+            TokenKind::Slash => self.emit_op(OpCode::OpDivide),
+            _ => unreachable!("only called for binary operator tokens"),
+        }
+
+        Ok(())
+    }
+
+    fn parse_precedence(&mut self, precedence: Precedence) -> LoxResult<()> {
+        self.advance();
+        let rule: ParseRule<T> = rule_for(&self.previous().kind);
+        let prefix_fn = match rule.prefix {
+            None => unimplemented!("expected expression or something, unclear"),
+            Some(func) => func,
+        };
+
+        prefix_fn(self)?;
+
+        while precedence <= rule_for::<T>(&self.current().kind).precedence {
+            self.advance();
+            match rule_for::<T>(&self.previous().kind).infix {
+                Some(func) => {
+                    func(self)?;
+                }
+                None => {
+                    unreachable!("invalid compiler state: error in parse rules")
+                }
+            }
+        }
+
+        Ok(())
+    }
+
+    fn consume(&mut self, expected: &TokenKind, err: ErrorKind) {
+        if (self.current().kind == *expected) {
+            self.advance();
+            return;
+        }
+
+        self.error_at(self.current().line, err);
+    }
+
+    fn current_chunk(&mut self) -> &mut Chunk {
+        &mut self.chunk
+    }
+
+    fn end_compiler(&mut self) -> LoxResult<()> {
+        self.emit_op(OpCode::OpReturn);
+
+        #[cfg(feature = "disassemble")]
+        {
+            chunk::disassemble_chunk(&self.chunk);
+            println!("== compilation finished ==");
+        }
+
+        Ok(())
+    }
+
+    fn emit_op(&mut self, op: OpCode) {
+        let line = self.previous().line;
+        self.current_chunk().add_op(op, line);
+    }
+
+    fn emit_constant(&mut self, val: Value) {
+        let idx = self.chunk.add_constant(val);
+        self.emit_op(OpCode::OpConstant(idx));
+    }
+
+    fn previous(&self) -> &Token {
+        self.previous
+            .as_ref()
+            .expect("invalid internal compiler state: missing previous token")
+    }
+
+    fn current(&self) -> &Token {
+        self.current
+            .as_ref()
+            .expect("invalid internal compiler state: missing current token")
+    }
+
+    fn error_at(&mut self, line: usize, kind: ErrorKind) {
+        if self.panic {
+            return;
+        }
+
+        self.panic = true;
+        self.errors.push(Error { kind, line })
+    }
+}
+
+pub fn compile(code: &str) -> Result<Chunk, Vec<Error>> {
+    let chars = code.chars().collect::<Vec<char>>();
+    let tokens = scanner::scan(&chars).map_err(|errors| {
+        errors.into_iter().map(Into::into).collect::<Vec<Error>>()
+    })?;
+
+    let mut compiler = Compiler {
+        tokens: tokens.into_iter().peekable(),
+        chunk: Default::default(),
+        panic: false,
+        errors: vec![],
+        current: None,
+        previous: None,
+    };
+
+    compiler.compile()?;
+
+    if compiler.errors.is_empty() {
+        Ok(compiler.chunk)
+    } else {
+        Err(compiler.errors)
+    }
+}