diff options
Diffstat (limited to 'users/tazjin/rlox/src/bytecode/compiler.rs')
| -rw-r--r-- | users/tazjin/rlox/src/bytecode/compiler.rs | 702 |
1 files changed, 702 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 0000000000..89584f19d7 --- /dev/null +++ b/users/tazjin/rlox/src/bytecode/compiler.rs @@ -0,0 +1,702 @@ +use super::chunk::Chunk; +use super::errors::{Error, ErrorKind, LoxResult}; +use super::interner::{InternedStr, Interner}; +use super::opcode::{CodeIdx, CodeOffset, ConstantIdx, OpCode, StackIdx}; +use super::value::Value; +use crate::scanner::{self, Token, TokenKind}; + +#[cfg(feature = "disassemble")] +use super::chunk; + +#[derive(Debug)] +enum Depth { + Unitialised, + At(usize), +} + +impl Depth { + fn above(&self, theirs: usize) -> bool { + match self { + Depth::Unitialised => false, + Depth::At(ours) => *ours > theirs, + } + } + + fn below(&self, theirs: usize) -> bool { + match self { + Depth::Unitialised => false, + Depth::At(ours) => *ours < theirs, + } + } +} + +#[derive(Debug)] +struct Local { + name: Token, + depth: Depth, +} + +#[derive(Debug, Default)] +struct Locals { + locals: Vec<Local>, + scope_depth: usize, +} + +struct Compiler<T: Iterator<Item = Token>> { + tokens: T, + chunk: Chunk, + panic: bool, + errors: Vec<Error>, + strings: Interner, + locals: Locals, + + 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), + + TokenKind::True => ParseRule::new(Some(Compiler::literal), None, Precedence::None), + + TokenKind::False => ParseRule::new(Some(Compiler::literal), None, Precedence::None), + + TokenKind::Nil => ParseRule::new(Some(Compiler::literal), None, Precedence::None), + + TokenKind::Bang => ParseRule::new(Some(Compiler::unary), None, Precedence::None), + + TokenKind::BangEqual => ParseRule::new(None, Some(Compiler::binary), Precedence::Equality), + + TokenKind::EqualEqual => ParseRule::new(None, Some(Compiler::binary), Precedence::Equality), + + TokenKind::Greater => ParseRule::new(None, Some(Compiler::binary), Precedence::Comparison), + + TokenKind::GreaterEqual => { + ParseRule::new(None, Some(Compiler::binary), Precedence::Comparison) + } + + TokenKind::Less => ParseRule::new(None, Some(Compiler::binary), Precedence::Comparison), + + TokenKind::LessEqual => { + ParseRule::new(None, Some(Compiler::binary), Precedence::Comparison) + } + + TokenKind::Identifier(_) => { + ParseRule::new(Some(Compiler::variable), None, Precedence::None) + } + + TokenKind::String(_) => ParseRule::new(Some(Compiler::string), None, Precedence::None), + + _ => ParseRule::new(None, None, Precedence::None), + } +} + +macro_rules! consume { + ( $self:ident, $expected:pat, $err:expr ) => { + match $self.current().kind { + $expected => $self.advance(), + _ => $self.error_at($self.current().line, $err), + } + }; +} + +impl<T: Iterator<Item = Token>> Compiler<T> { + fn compile(&mut self) -> LoxResult<()> { + self.advance(); + + while !self.match_token(&TokenKind::Eof) { + self.declaration()?; + } + + 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 var_declaration(&mut self) -> LoxResult<()> { + let idx = self.parse_variable()?; + + if self.match_token(&TokenKind::Equal) { + self.expression()?; + } else { + self.emit_op(OpCode::OpNil); + } + + self.expect_semicolon("expect ';' after variable declaration")?; + self.define_variable(idx) + } + + fn define_variable(&mut self, var: Option<ConstantIdx>) -> LoxResult<()> { + if self.locals.scope_depth == 0 { + self.emit_op(OpCode::OpDefineGlobal(var.expect("should be global"))); + } else { + self.locals + .locals + .last_mut() + .expect("fatal: variable not yet added at definition") + .depth = Depth::At(self.locals.scope_depth); + } + + Ok(()) + } + + fn declaration(&mut self) -> LoxResult<()> { + if self.match_token(&TokenKind::Var) { + self.var_declaration()?; + } else { + self.statement()?; + } + + if self.panic { + self.synchronise(); + } + + Ok(()) + } + + fn statement(&mut self) -> LoxResult<()> { + if self.match_token(&TokenKind::Print) { + self.print_statement() + } else if self.match_token(&TokenKind::If) { + self.if_statement() + } else if self.match_token(&TokenKind::LeftBrace) { + self.begin_scope(); + self.block()?; + self.end_scope(); + Ok(()) + } else { + self.expression_statement() + } + } + + fn print_statement(&mut self) -> LoxResult<()> { + self.expression()?; + self.expect_semicolon("expect ';' after print statement")?; + self.emit_op(OpCode::OpPrint); + Ok(()) + } + + fn begin_scope(&mut self) { + self.locals.scope_depth += 1; + } + + fn end_scope(&mut self) { + debug_assert!(self.locals.scope_depth > 0, "tried to end global scope"); + self.locals.scope_depth -= 1; + + while self.locals.locals.len() > 0 + && self.locals.locals[self.locals.locals.len() - 1] + .depth + .above(self.locals.scope_depth) + { + self.emit_op(OpCode::OpPop); + self.locals.locals.remove(self.locals.locals.len() - 1); + } + } + + fn block(&mut self) -> LoxResult<()> { + while !self.check(&TokenKind::RightBrace) && !self.check(&TokenKind::Eof) { + self.declaration()?; + } + + consume!( + self, + TokenKind::RightBrace, + ErrorKind::ExpectedToken("Expected '}' after block.") + ); + Ok(()) + } + + fn expression_statement(&mut self) -> LoxResult<()> { + self.expression()?; + self.expect_semicolon("expect ';' after expression")?; + // TODO(tazjin): Why did I add this originally? + // self.emit_op(OpCode::OpPop); + Ok(()) + } + + fn if_statement(&mut self) -> LoxResult<()> { + consume!( + self, + TokenKind::LeftParen, + ErrorKind::ExpectedToken("Expected '(' after 'if'") + ); + + self.expression()?; + + consume!( + self, + TokenKind::RightParen, + ErrorKind::ExpectedToken("Expected ')' after condition") + ); + + let then_jump = self.emit_op(OpCode::OpJumpPlaceholder(false)); + self.emit_op(OpCode::OpPop); + self.statement()?; + let else_jump = self.emit_op(OpCode::OpJumpPlaceholder(true)); + self.patch_jump(then_jump); + self.emit_op(OpCode::OpPop); + + if self.match_token(&TokenKind::Else) { + self.statement()?; + } + + self.patch_jump(else_jump); + + Ok(()) + } + + fn number(&mut self) -> LoxResult<()> { + if let TokenKind::Number(num) = self.previous().kind { + self.emit_constant(Value::Number(num), true); + return Ok(()); + } + + unreachable!("internal parser error: entered number() incorrectly") + } + + fn grouping(&mut self) -> LoxResult<()> { + self.expression()?; + consume!( + self, + 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::Bang => self.emit_op(OpCode::OpNot), + 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.next())?; + + // 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), + + TokenKind::BangEqual => { + self.emit_op(OpCode::OpEqual); + self.emit_op(OpCode::OpNot) + } + + TokenKind::EqualEqual => self.emit_op(OpCode::OpEqual), + TokenKind::Greater => self.emit_op(OpCode::OpGreater), + + TokenKind::GreaterEqual => { + self.emit_op(OpCode::OpLess); + self.emit_op(OpCode::OpNot) + } + + TokenKind::Less => self.emit_op(OpCode::OpLess), + TokenKind::LessEqual => { + self.emit_op(OpCode::OpGreater); + self.emit_op(OpCode::OpNot) + } + + _ => unreachable!("only called for binary operator tokens"), + }; + + Ok(()) + } + + fn literal(&mut self) -> LoxResult<()> { + match self.previous().kind { + TokenKind::Nil => self.emit_op(OpCode::OpNil), + TokenKind::True => self.emit_op(OpCode::OpTrue), + TokenKind::False => self.emit_op(OpCode::OpFalse), + _ => unreachable!("only called for literal value tokens"), + }; + + Ok(()) + } + + fn string(&mut self) -> LoxResult<()> { + let val = match &self.previous().kind { + TokenKind::String(s) => s.clone(), + _ => unreachable!("only called for strings"), + }; + + let id = self.strings.intern(val); + self.emit_constant(Value::String(id.into()), true); + + Ok(()) + } + + fn named_variable(&mut self, name: Token) -> LoxResult<()> { + let local_idx = self.resolve_local(&name); + + let ident = if local_idx.is_some() { + None + } else { + Some(self.identifier_constant(&name)?) + }; + + if self.match_token(&TokenKind::Equal) { + self.expression()?; + match local_idx { + Some(idx) => self.emit_op(OpCode::OpSetLocal(idx)), + None => self.emit_op(OpCode::OpSetGlobal(ident.unwrap())), + }; + } else { + match local_idx { + Some(idx) => self.emit_op(OpCode::OpGetLocal(idx)), + None => self.emit_op(OpCode::OpGetGlobal(ident.unwrap())), + }; + } + + Ok(()) + } + + fn variable(&mut self) -> LoxResult<()> { + let name = self.previous().clone(); + self.named_variable(name) + } + + 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 identifier_str(&mut self, token: &Token) -> LoxResult<InternedStr> { + let ident = match &token.kind { + TokenKind::Identifier(ident) => ident.to_string(), + _ => { + return Err(Error { + line: self.current().line, + kind: ErrorKind::ExpectedToken("Expected identifier"), + }) + } + }; + + Ok(self.strings.intern(ident)) + } + + fn identifier_constant(&mut self, name: &Token) -> LoxResult<ConstantIdx> { + let ident = self.identifier_str(name)?; + Ok(self.emit_constant(Value::String(ident.into()), false)) + } + + fn resolve_local(&self, name: &Token) -> Option<StackIdx> { + for (idx, local) in self.locals.locals.iter().enumerate().rev() { + if name.lexeme == local.name.lexeme { + if let Depth::Unitialised = local.depth { + // TODO(tazjin): *return* err + panic!("can't read variable in its own initialiser"); + } + return Some(StackIdx(idx)); + } + } + + None + } + + fn add_local(&mut self, name: Token) { + let local = Local { + name, + depth: Depth::Unitialised, + }; + + self.locals.locals.push(local); + } + + fn declare_variable(&mut self) -> LoxResult<()> { + if self.locals.scope_depth == 0 { + return Ok(()); + } + + let name = self.previous().clone(); + + for local in self.locals.locals.iter().rev() { + if local.depth.below(self.locals.scope_depth) { + break; + } + + if name.lexeme == local.name.lexeme { + return Err(Error { + kind: ErrorKind::VariableShadowed(name.lexeme.into()), + line: name.line, + }); + } + } + + self.add_local(name); + Ok(()) + } + + fn parse_variable(&mut self) -> LoxResult<Option<ConstantIdx>> { + consume!( + self, + TokenKind::Identifier(_), + ErrorKind::ExpectedToken("expected identifier") + ); + + self.declare_variable()?; + if self.locals.scope_depth > 0 { + return Ok(None); + } + + let name = self.previous().clone(); + let id = self.identifier_str(&name)?; + Ok(Some(self.emit_constant(Value::String(id.into()), false))) + } + + 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) -> CodeIdx { + let line = self.previous().line; + self.current_chunk().add_op(op, line) + } + + fn emit_constant(&mut self, val: Value, with_op: bool) -> ConstantIdx { + let idx = ConstantIdx(self.chunk.add_constant(val)); + + if with_op { + self.emit_op(OpCode::OpConstant(idx)); + } + + idx + } + + fn patch_jump(&mut self, idx: CodeIdx) { + let offset = CodeOffset(self.chunk.code.len() - idx.0 - 1); + + if let OpCode::OpJumpPlaceholder(true) = self.chunk.code[idx.0] { + self.chunk.code[idx.0] = OpCode::OpJump(offset); + return; + } + + if let OpCode::OpJumpPlaceholder(false) = self.chunk.code[idx.0] { + self.chunk.code[idx.0] = OpCode::OpJumpIfFalse(offset); + return; + } + + panic!( + "attempted to patch unsupported op: {:?}", + self.chunk.code[idx.0] + ); + } + + 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 }) + } + + fn match_token(&mut self, token: &TokenKind) -> bool { + if !self.check(token) { + return false; + } + + self.advance(); + true + } + + fn check(&self, token: &TokenKind) -> bool { + return self.current().kind == *token; + } + + fn synchronise(&mut self) { + self.panic = false; + + while self.current().kind != TokenKind::Eof { + if self.previous().kind == TokenKind::Semicolon { + return; + } + + match self.current().kind { + TokenKind::Class + | TokenKind::Fun + | TokenKind::Var + | TokenKind::For + | TokenKind::If + | TokenKind::While + | TokenKind::Print + | TokenKind::Return => return, + + _ => { + self.advance(); + } + } + } + } + + fn expect_semicolon(&mut self, msg: &'static str) -> LoxResult<()> { + consume!(self, TokenKind::Semicolon, ErrorKind::ExpectedToken(msg)); + Ok(()) + } +} + +pub fn compile(code: &str) -> Result<(Interner, 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![], + strings: Interner::with_capacity(1024), + locals: Default::default(), + current: None, + previous: None, + }; + + compiler.compile()?; + + if compiler.errors.is_empty() { + Ok((compiler.strings, compiler.chunk)) + } else { + Err(compiler.errors) + } +} |