tinyscript 0.6.1

// Copyright © 2025 Stephan Kunz
//! [`Parser`] is implemented as a [Pratt-Parser](https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html)
//! You should also read the articel by [Robert Nystrom](https://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/)
//!
//! Implementation is inspired by
//! - Robert Nystrom [crafting interpreters - A Bytecode Virtual Machine](https://craftinginterpreters.com/a-bytecode-virtual-machine.html)
//! - Jon Gjengsets [video](https://www.youtube.com/watch?v=mNOLaw-_Buc) & [example](https://github.com/jonhoo/lox/blob/master/src/parse.rs)
//! - Jürgen Wurzers implementation of [Bantam](https://github.com/jwurzer/bantam-rust/blob/master/src/bantam/bantam_parser.rs)
//!
//! Definition of the grammer (following this [notation](https://craftinginterpreters.com/representing-code.html#rules-for-grammars)):
//! ```no-test
//! script      → statement* EoF ;
//! statement   → expression ";" ;
//! expression  → assignment ;
//! assignment  → IDENTIFIER ":=" assignment | IDENTIFIER "=" assignment | logic_or ;
//! ternary     → logic_or "?" expression ":" expression ;
//! logic_or    → logic_and ( "||" logic_and )* ;
//! logic_and   → binary_or ( "&&" binary_or )* ;
//! binary_or   → binary_xor ( "|" binary_xor )* ;
//! binary_xor  → binary_and ( "^" binary_and )* ;
//! binary_and  → equality ( "&" equality )* ;
//! equality    → comparison ( ( "!=" | "==" ) comparison )* ;
//! comparison  → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
//! term        → factor ( ( "-" | "+" ) factor )* ;
//! factor      → unary ( ( "/" | "*" ) unary )* ;
//! unary       → ( "!" | "-" | "~") unary | primary ;
//! primary     → "true" | "false" | FLOATNUMBER | HEXNUMBER| INTNUMBER  | STRING | IDENTIFIER | "(" expression ")" ;
//!
//! FLOATNUMBER → DIGIT+ ( "." DIGIT+ ) ;
//! HEXNUMBER   → (0x | 0X) + (DIGIT+ | "a" ... "f"+ | "A" ... "F"+ );
//! INTNUMBER   → ( DIGIT+ ) ;
//! STRING      → "\'" <any char except "\'">* "\'" ;
//! IDENTIFIER  → ALPHA ( ALPHA | DIGIT )* ;
//! ALPHA       → "a" ... "z" | "A" ... "Z" | "_" ;
//! DIGIT       → "0" ... "9" ;
//! ```

use alloc::{
	collections::btree_map::BTreeMap,
	string::{String, ToString},
};

use crate::{
	compilation::Lexer,
	execution::{Chunk, op_code::OpCode},
};

use super::{
	error::CompilationError,
	parselets::{
		AnyInfixParselet, AnyPrefixParselet, AssignmentParselet, BinaryKind, BinaryParselet, GroupingParselet,
		InfixParselet, LiteralParselet, LogicKind, LogicParselet, PrefixParselet, UnaryParselet, ValueParselet,
	},
	precedence::Precedence,
	token::{Token, TokenKind},
};

/// Parser implementation.
pub struct Parser {
	/// Map of prefix parselets.
	prefix_parselets: BTreeMap<TokenKind, AnyPrefixParselet>,
	/// Map of infix parselets.
	infix_parselets: BTreeMap<TokenKind, AnyInfixParselet>,
	/// Current handled Token.
	current: Token,
	/// Preview on next Token.
	next: Token,
}

impl core::fmt::Debug for Parser {
	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
		f.debug_struct("Parser")
			// .field("lexer", &self.lexer)
			// .field("prefix_parselets", &self.prefix_parselets)
			// .field("infix_parselets", &self.infix_parselets)
			.field("current", &self.current)
			.field("next", &self.next)
			.finish_non_exhaustive()
	}
}

impl Default for Parser {
	fn default() -> Self {
		Self::new()
	}
}

impl Parser {
	/// Create a Parser with all the necessary ingredients
	#[must_use]
	#[allow(clippy::too_many_lines)]
	pub fn new() -> Self {
		let mut parser = Self {
			prefix_parselets: BTreeMap::default(),
			infix_parselets: BTreeMap::default(),
			current: Token::none(),
			next: Token::none(),
		};

		// Register the parselets for the grammar
		parser.infix_parselets.insert(
			TokenKind::Ampersand,
			AnyInfixParselet::Logic(LogicParselet::new(LogicKind::BitAnd)),
		);
		parser
			.infix_parselets
			.insert(TokenKind::And, AnyInfixParselet::Logic(LogicParselet::new(LogicKind::And)));
		parser
			.prefix_parselets
			.insert(TokenKind::Bang, AnyPrefixParselet::Unary(UnaryParselet));
		parser.infix_parselets.insert(
			TokenKind::BangEqual,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::BangEqual)),
		);
		parser.infix_parselets.insert(
			TokenKind::Caret,
			AnyInfixParselet::Logic(LogicParselet::new(LogicKind::BitXor)),
		);
		parser
			.prefix_parselets
			.insert(TokenKind::Enum, AnyPrefixParselet::Value(ValueParselet));
		parser.infix_parselets.insert(
			TokenKind::EqualEqual,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::EqualEqual)),
		);
		parser
			.prefix_parselets
			.insert(TokenKind::False, AnyPrefixParselet::Literal(LiteralParselet));
		parser.infix_parselets.insert(
			TokenKind::Greater,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::Greater)),
		);
		parser.infix_parselets.insert(
			TokenKind::GreaterEqual,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::GreaterEqual)),
		);
		parser
			.prefix_parselets
			.insert(TokenKind::HexNumber, AnyPrefixParselet::Value(ValueParselet));
		parser
			.prefix_parselets
			.insert(TokenKind::IntNumber, AnyPrefixParselet::Value(ValueParselet));
		parser
			.prefix_parselets
			.insert(TokenKind::Ident, AnyPrefixParselet::Assignment(AssignmentParselet));
		parser
			.prefix_parselets
			.insert(TokenKind::LeftParen, AnyPrefixParselet::Grouping(GroupingParselet));
		parser.infix_parselets.insert(
			TokenKind::Less,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::Less)),
		);
		parser.infix_parselets.insert(
			TokenKind::LessEqual,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::LessEqual)),
		);
		parser
			.prefix_parselets
			.insert(TokenKind::Minus, AnyPrefixParselet::Unary(UnaryParselet));
		parser.infix_parselets.insert(
			TokenKind::Minus,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::Minus)),
		);
		parser
			.prefix_parselets
			.insert(TokenKind::Nil, AnyPrefixParselet::Literal(LiteralParselet));
		parser
			.prefix_parselets
			.insert(TokenKind::FloatNumber, AnyPrefixParselet::Value(ValueParselet));
		parser
			.infix_parselets
			.insert(TokenKind::Or, AnyInfixParselet::Logic(LogicParselet::new(LogicKind::Or)));
		parser
			.infix_parselets
			.insert(TokenKind::Pipe, AnyInfixParselet::Logic(LogicParselet::new(LogicKind::BitOr)));
		parser
			.prefix_parselets
			.insert(TokenKind::Plus, AnyPrefixParselet::Unary(UnaryParselet));
		parser.infix_parselets.insert(
			TokenKind::Plus,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::Plus)),
		);
		parser.infix_parselets.insert(
			TokenKind::QMark,
			AnyInfixParselet::Logic(LogicParselet::new(LogicKind::Ternary)),
		);
		parser.infix_parselets.insert(
			TokenKind::Slash,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::Slash)),
		);
		parser.infix_parselets.insert(
			TokenKind::Star,
			AnyInfixParselet::Binary(BinaryParselet::new(BinaryKind::Star)),
		);
		parser
			.prefix_parselets
			.insert(TokenKind::String, AnyPrefixParselet::Value(ValueParselet));
		parser
			.prefix_parselets
			.insert(TokenKind::Tilde, AnyPrefixParselet::Unary(UnaryParselet));
		parser
			.prefix_parselets
			.insert(TokenKind::True, AnyPrefixParselet::Literal(LiteralParselet));

		// return the prepared parser
		parser
	}

	/// Create a bytecode [`Chunk`] from source
	/// # Errors
	/// - passes [`Lexer`] errors through
	/// - if it could not create a proper [`Chunk`]
	pub fn parse(&mut self, enums: &BTreeMap<String, i8>, source_code: &str) -> Result<Chunk, CompilationError> {
		let mut chunk = Chunk::default();
		let mut lexer = Lexer::new(enums, source_code);

		self.advance(&mut lexer)?;
		while !self.check_next(TokenKind::None) {
			// in case of error try to synchronize to next statement
			if let Err(_error) = self.statement(&mut lexer, &mut chunk) {
				while !(self.check_next(TokenKind::Semicolon)
					|| self.check_next(TokenKind::Print)
					|| self.check_next(TokenKind::None))
				{
					self.advance(&mut lexer)?;
				}
			}
		}

		// end compiler
		self.emit_byte(OpCode::Return as u8, &mut chunk);
		chunk.finalize();
		Ok(chunk)
	}

	pub(super) fn current(&self) -> Token {
		self.current.clone()
	}

	pub(super) fn next(&self) -> Token {
		self.next.clone()
	}

	/// Advance to the next token
	/// # Errors
	/// passthrough of [`Lexer`] errors
	pub(super) fn advance(&mut self, lexer: &mut Lexer) -> Result<(), CompilationError> {
		self.current = self.next.clone();
		let tmp = lexer.next();
		if let Some(token) = tmp {
			// passthrough of lexer errors
			self.next = token?;
		} else {
			self.next = Token::none();
		}
		//std::println!("{}", self.current.kind);
		Ok(())
	}

	/// Consume the next token if it has the expected kind
	/// # Errors
	/// if next token does not have the expected kind
	pub(super) fn consume(&mut self, lexer: &mut Lexer, expected: TokenKind) -> Result<(), CompilationError> {
		if self.next.kind == expected {
			self.advance(lexer)
		} else {
			Err(CompilationError::TokenExpected {
				expected: expected.to_string().into(),
				found: self.next.kind.to_string().into(),
				pos: self.next.line,
			})
		}
	}

	/// Check next token whether it has given kind
	pub(super) fn check_next(&self, kind: TokenKind) -> bool {
		self.next.kind == kind
	}

	pub(super) fn emit_byte(&self, byte: u8, chunk: &mut Chunk) {
		chunk.write(byte, self.current.line);
	}

	pub(super) fn emit_bytes(&self, byte1: u8, byte2: u8, chunk: &mut Chunk) {
		chunk.write(byte1, self.current.line);
		chunk.write(byte2, self.current.line);
	}

	pub(super) fn emit_jump(&self, instruction: u8, chunk: &mut Chunk) -> usize {
		chunk.write(instruction, self.current.line);
		let target_pos = chunk.code().len();
		// the dummy address bytes
		chunk.write(0xFF, self.current.line);
		chunk.write(0xFF, self.current.line);
		target_pos
	}

	#[allow(clippy::cast_possible_truncation)]
	pub(super) fn patch_jump(patch_pos: usize, chunk: &mut Chunk) {
		let target = chunk.code().len();
		let byte1 = (target >> 8) as u8;
		let byte2 = target as u8;
		chunk.patch(byte1, patch_pos);
		chunk.patch(byte2, patch_pos + 1);
	}

	pub(super) fn statement(&mut self, lexer: &mut Lexer, chunk: &mut Chunk) -> Result<(), CompilationError> {
		if self.next.kind == TokenKind::Print {
			self.advance(lexer)?;
			self.expression(lexer, chunk)?;
			// a statement my also be finished by EOF
			if !self.check_next(TokenKind::None) {
				self.consume(lexer, TokenKind::Semicolon)?;
			}
			#[cfg(feature = "std")]
			self.emit_byte(OpCode::Print as u8, chunk);
			#[cfg(not(feature = "std"))]
			self.emit_byte(OpCode::Pop as u8, chunk);
		} else {
			self.expression(lexer, chunk)?;
			if !self.check_next(TokenKind::None) {
				self.consume(lexer, TokenKind::Semicolon)?;
			}
			//self.emit_byte(OP_POP, chunk);
		}
		Ok(())
	}

	pub(super) fn expression(&mut self, lexer: &mut Lexer, chunk: &mut Chunk) -> Result<(), CompilationError> {
		self.with_precedence(lexer, Precedence::Assignment, chunk)
	}

	#[allow(clippy::expect_used)]
	pub(super) fn with_precedence(
		&mut self,
		lexer: &mut Lexer,
		precedence: Precedence,
		chunk: &mut Chunk,
	) -> Result<(), CompilationError> {
		self.advance(lexer)?;

		let token = self.current();
		let Some(prefix_parselet) = self.prefix_parselets.get(&token.kind).cloned() else {
			return Err(CompilationError::ExpressionExpected {
				token: token.kind.to_string().into(),
				pos: token.line,
			});
		};
		prefix_parselet.parse(lexer, self, chunk, token)?;

		while precedence <= self.get_precedence() {
			self.advance(lexer)?;
			let token = self.current();
			if let Some(infix) = self.infix_parselets.get(&token.kind).cloned() {
				infix.parse(lexer, self, chunk, token)?;
			} else {
				break;
			}
		}

		Ok(())
	}

	fn get_precedence(&self) -> Precedence {
		let token = self.next();
		if let Some(parselet) = self.infix_parselets.get(&token.kind) {
			return parselet.get_precedence();
		}
		Precedence::None
	}
}

#[cfg(test)]
mod tests {
	use super::*;

	// check, that the auto traits are available
	const fn is_normal<T: Sized + Send + Sync>() {}

	#[test]
	const fn normal_types() {
		is_normal::<&Parser>();
		is_normal::<Parser>();
	}
}