use std::cell::Cell;
use crate::syntax::{
buildctx::BuildCtx,
cst::{kind::TreeKind, tree::{Node, NodeHandle}},
diagnostic::Severity,
lexer::token::{Token, TokenKind},
location::Span,
};
use super::{
token::{Tt, TtSet},
};
#[derive(Debug, Clone, Copy)]
enum EventKind {
Open { kind: TreeKind, next: u32 },
Close,
}
const CHAIN_END: u32 = u32::MAX;
#[derive(Debug, Clone, Copy)]
struct Event {
token: u32,
kind: EventKind,
}
const EVENT_IGNORE: u32 = u32::MAX;
#[derive(Debug, Clone, Copy)]
pub struct OpenHandle(u32);
#[derive(Debug, Clone, Copy)]
pub struct CloseHandle(u32);
const MAX_PARSER_LOOKUPS: u32 = 256;
pub struct Parser<'ctx> {
ctx: &'ctx mut BuildCtx,
tokens: Vec<Token>,
token_idx: u32,
events: Vec<Event>,
fuel: Cell<u32>,
}
impl<'ctx> Parser<'ctx> {
pub fn new(ctx: &'ctx mut BuildCtx, tokens: Vec<Token>) -> Self {
Self {
ctx,
tokens,
token_idx: 0,
events: Vec::new(),
fuel: Cell::new(MAX_PARSER_LOOKUPS),
}
}
pub fn make_tree(&mut self) -> Vec<Node> {
let mut stack = Vec::new();
let mut output = Vec::with_capacity(self.tokens.len() + self.events.len());
let mut tokens = self.tokens.drain(..);
let mut token_idx = 0;
for event in self.events.iter() {
if event.token == EVENT_IGNORE {
continue;
}
for _ in token_idx..event.token {
output.push(Node::Token(
tokens
.next()
.expect("Event token index exceeds number of tokens"),
));
}
token_idx = event.token;
match event.kind {
EventKind::Open { mut kind, mut next } => loop {
stack.push(output.len());
output.push(Node::Open {
kind,
close: NodeHandle(u32::MAX),
});
if next != CHAIN_END {
assert_eq!(self.events[next as usize].token, EVENT_IGNORE);
(kind, next) = if let EventKind::Open { kind, next } =
self.events[next as usize].kind
{
(kind, next)
} else {
panic!("Open event chained to a non-Open event")
}
} else {
break;
}
},
EventKind::Close => {
let open_idx = stack.pop().expect("Too many close events");
let close_idx = output.len();
let Node::Open { kind, close } = &mut output[open_idx] else {
panic!("stack points to non-Open node");
};
*close = NodeHandle(close_idx as u32);
let kind = *kind;
output.push(Node::Close {
kind,
open: NodeHandle(open_idx as u32),
});
}
}
}
assert!(stack.is_empty());
output
}
fn burn(&self) {
if self.fuel.get() == 0 {
panic!("Parser is stuck at {:?}", self.pos())
}
self.fuel.set(self.fuel.get() - 1);
}
fn push_event(&mut self, kind: EventKind) {
self.events.push(Event {
token: self.token_idx,
kind,
});
}
#[must_use]
pub fn open(&mut self) -> OpenHandle {
let handle = OpenHandle(self.events.len() as u32);
self.push_event(EventKind::Open {
kind: TreeKind::Error,
next: CHAIN_END,
});
handle
}
pub fn close(&mut self, handle: OpenHandle, new_kind: TreeKind) -> CloseHandle {
let EventKind::Open { kind, .. }: &mut EventKind = &mut self.events[handle.0 as usize].kind
else {
panic!("close called on Close event")
};
*kind = new_kind;
self.push_event(EventKind::Close);
CloseHandle(handle.0)
}
pub fn open_before(&mut self, handle: CloseHandle) -> OpenHandle {
let new_evt_idx = self.events.len();
let prev_evt_idx = handle.0 as usize;
let Event { token, kind } = self.events[prev_evt_idx];
self.events.push(Event {
token: EVENT_IGNORE,
kind,
});
self.events[prev_evt_idx] = Event {
token,
kind: EventKind::Open {
kind: TreeKind::Error,
next: new_evt_idx as u32,
},
};
OpenHandle(handle.0)
}
pub fn wrap(&mut self, handle: CloseHandle, kind: TreeKind) -> CloseHandle {
let h = self.open_before(handle);
self.close(h, kind)
}
fn peek_raw(&self) -> Option<&Token> {
self.tokens.get(self.token_idx as usize)
}
pub fn peek_kind<'inp: 'out, 'out>(&'inp mut self) -> Option<&'out TokenKind> {
self.burn();
while let Some(tok) = self.peek_raw() {
if tok.kind.significant() {
break;
}
self.advance();
}
self.peek_raw().map(|t| &t.kind)
}
pub fn peek(&mut self) -> Tt {
self.peek_kind()
.map_or(Tt::Eof, |t| Tt::from_kind(t).expect("Token is significant"))
}
pub fn nth_raw(&mut self, ofs: usize) -> Option<Tt> {
self.tokens
.get(self.token_idx as usize + ofs)
.map_or(Some(Tt::Eof), |t| Tt::from_kind(&t.kind))
}
pub fn nth(&mut self, mut ofs: usize) -> Tt {
let mut raw_ofs = 0;
loop {
match self.nth_raw(raw_ofs) {
Some(tt) if ofs == 0 => return tt,
Some(_) => ofs -= 1,
None => (),
}
raw_ofs += 1;
}
}
pub fn nth_is(&mut self, ofs: usize, ty: impl Into<Tt>) -> bool {
self.nth(ofs) == ty.into()
}
pub fn advance(&mut self) {
assert!(!self.eof());
self.fuel.set(MAX_PARSER_LOOKUPS);
self.token_idx += 1;
}
pub fn eof(&self) -> bool {
self.token_idx == self.tokens.len() as u32
}
pub fn at(&mut self, ty: impl Into<Tt>) -> bool {
self.peek() == ty.into()
}
pub fn at_set(&mut self, tys: &TtSet) -> bool {
tys.contains(self.peek())
}
pub fn at_id(&mut self, str: &str) -> bool {
matches!(self.peek_kind(), Some(TokenKind::Ident(id)) if id == str)
}
pub fn eof_or(&mut self, ty: impl Into<Tt>) -> bool {
self.at(ty) || self.eof()
}
pub fn eat(&mut self, ty: impl Into<Tt>) -> bool {
if self.at(ty) {
self.advance();
true
} else {
false
}
}
pub fn advance_error(&mut self, message: impl Into<String>) -> CloseHandle {
let h = self.open();
self.error(message);
if !self.eof() {
self.advance();
}
self.close(h, TreeKind::Error)
}
pub fn error_empty(&mut self, message: impl Into<String>) -> CloseHandle {
let h = self.open();
self.error(message);
self.close(h, TreeKind::Error)
}
fn pos(&self) -> Span {
self.tokens
.get(self.token_idx as usize)
.map_or(Span::empty_at(self.ctx.origins.root().end_pos()), |t| {
t.span.empty_at_start()
})
}
pub fn error(&mut self, message: impl Into<String>) {
self.ctx
.diagnostics
.push(self.pos(), Severity::Error, "blues-lsp", message.into());
}
pub fn expect(&mut self, ty: impl Into<Tt>) {
let ty = ty.into();
if self.eat(ty) {
return;
}
self.error(format!("Expected {}", ty));
}
pub fn assert(&mut self, ty: impl Into<Tt>) {
let ty = ty.into();
assert_eq!(self.peek(), ty);
self.advance();
}
pub fn kind_of(&self, handle: CloseHandle) -> TreeKind {
match self.events[handle.0 as usize].kind {
EventKind::Open { kind, .. } => kind,
EventKind::Close => unreachable!(),
}
}
}