blues_lsp/syntax/parser/

state.rs

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;
            }

            // Emit all tokens leading up to event
            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"))
    }

    /// Get token kind `ofs` tokens from cursor
    /// This does *not* skip non-significant tokens!
    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!(),
        }
    }
}