ielr 0.1.1

/*
 * Copyright 2022 Arnaud Golfouse
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

use super::Lookahead;
use crate::{
    indices::{StateIdxRaw, SymbolIdx},
    input::{Grammar, Node, ProdIdx, Symbol},
    structures::{Map, Set},
};
use std::ops;

/// An index in the [`states`](super::Table::states).
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct StateIdx(pub(crate) StateIdxRaw);

impl StateIdx {
    /// Get the index as an integer.
    pub const fn get(self) -> StateIdxRaw {
        self.0
    }
}

/// A state in the [`Table`](super::Table).
#[derive(Debug, Clone)]
pub struct State {
    /// Items of the state. That is, what productions might in process of being parsed
    /// in this state.
    pub(crate) items: Vec<Item>,
    /// Where the core items end.
    ///
    /// That is, `self.items[..self.core_items_len]` will be all core items.
    pub(crate) core_items_len: usize,
    /// What to do on each encountered lookahead.
    ///
    /// If a lookahead is not in this table, the associated action is 'error'.
    pub(crate) action_table: InternalActionTable,
    /// The 'GOTO' table: in which state to go when a node has been reduced.
    pub(crate) goto_table: Map<Node, StateIdx>,
    /// Symbol used to transition into this state.
    pub accessing_symbol: Option<Symbol>,
}

/// Item in a [`State`].
///
/// This represent one of the things the parser _may_ be currently parsing.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Item {
    /// The production of this item.
    ///
    /// This has the form `lhs → rhs`, where `rhs` may be retrieved using
    /// [`Grammar::get_rhs`](crate::input::Grammar::get_rhs).
    pub production: ProdIdx,
    /// At which point of [`production`](Self::production) we are.
    pub index: SymbolIdx,
    /// Which lookaheads are expected after this item is finished parsing.
    pub(crate) lookaheads: Set<Lookahead>,
}

impl Item {
    /// Returns `true` if `lookahead` may be found right after `self`.
    pub fn has_lookahead(&self, lookahead: Lookahead) -> bool {
        self.lookaheads.contains(&lookahead)
    }

    /// Returns all lookaheads that may be found right after `self`.
    pub fn get_all_lookaheads(&self) -> impl Iterator<Item = Lookahead> + '_ {
        self.lookaheads.iter().copied()
    }

    /// Uses `grammar` to get the production corresponding to `self`, at read the
    /// symbol at [`Self::index`].
    ///
    /// If `index` is at the last position, this will return `None`.
    pub fn current_symbol(&self, grammar: &Grammar) -> Option<Symbol> {
        let rhs = grammar.get_rhs(self.production).unwrap_or_default();
        rhs.get(self.index as usize).copied()
    }
}

type InternalActionTable = Map<Lookahead, Action>;

/// Structure to probe to get the next [`Action`], using [`Self::get_action`].
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ActionTable<'a> {
    internal: &'a InternalActionTable,
}

/// A table in a [`State`] that maps a [`Node`] to the state one should go into right
/// after reducing said node.
pub struct GotoTable<'a> {
    internal: &'a Map<Node, StateIdx>,
}

/// What action the parser should take upon seeing a lookahead (or more).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Action {
    /// The parser needs to shift into the contained state.
    Shift(StateIdx),
    /// The parser needs to create a new node, using the contained [`ProdIdx`].
    Reduce(ProdIdx),
    /// The parser can finish the parsing for the given starting node.
    Accept(Node),
}

impl ActionTable<'_> {
    /// Get the next action to take upon seeing `lookahead`.
    ///
    /// If this returns `None`, this is a parser error.
    pub fn get_action(self, lookahead: Lookahead) -> Option<Action> {
        Some(*self.internal.get(&lookahead)?)
    }

    /// Get all expected lookahead in the [`ActionTable`], and the associated [`Action`].
    pub fn iter(&mut self) -> impl Iterator<Item = (Lookahead, Action)> + '_ {
        self.internal
            .iter()
            .map(|(lookahead, action)| (*lookahead, *action))
    }
}

impl GotoTable<'_> {
    /// Get the goto action associated with `node`.
    ///
    /// This should be used right after a [`reduce`](Action::Reduce) action, with the
    /// left-hand side of the reduced production.
    pub fn get_goto(self, node: Node) -> Option<StateIdx> {
        self.internal.get(&node).copied()
    }

    /// Get all possible goto transitions in this table.
    pub fn iter(&mut self) -> impl Iterator<Item = (Node, StateIdx)> + '_ {
        self.internal
            .iter()
            .map(|(node, to_state)| (*node, *to_state))
    }
}

impl State {
    /// Get the possible action (depending on the lookahead) for this state.
    pub fn action_table(&self) -> ActionTable {
        ActionTable {
            internal: &self.action_table,
        }
    }

    /// Get the [`GotoTable`] associated with this state.
    pub fn goto_table(&self) -> GotoTable {
        GotoTable {
            internal: &self.goto_table,
        }
    }

    /// Get the transition from this state on `symbol`, if it exists.
    pub fn transition(&self, symbol: Symbol) -> Option<StateIdx> {
        match symbol {
            Symbol::Token(t) => match self.action_table.get(&Lookahead::Token(t)) {
                Some(Action::Shift(to_state)) => Some(*to_state),
                _ => None,
            },
            Symbol::Node(n) => self.goto_table.get(&n).copied(),
        }
    }

    /// Get all possible transition from this state to any other, using either
    /// [`shift`](Action::Shift) or [`goto`](GotoTable) transitions.
    pub fn get_all_transitions(&self) -> impl Iterator<Item = (Symbol, StateIdx)> + '_ {
        self.action_table
            .iter()
            .filter_map(|(lookahead, action)| {
                let token = match lookahead {
                    Lookahead::Eof => return None,
                    Lookahead::Token(token) => *token,
                };
                match action {
                    Action::Shift(to) => Some((Symbol::Token(token), *to)),
                    _ => None,
                }
            })
            .chain(
                self.goto_table
                    .iter()
                    .map(|(node, to)| (Symbol::Node(*node), *to)),
            )
    }

    /// Get all the [`Item`]s of this state.
    pub fn all_items(&self) -> &[Item] {
        &self.items
    }

    /// Get all the _core_ [`Item`]s of this state
    ///
    /// A core item is an item where the dot is not at the left-most position. In other
    /// words, [`Item::index`] is not `0`.
    pub fn core_items(&self) -> &[Item] {
        &self.items[..self.core_items_len]
    }
}

impl ops::Index<StateIdx> for [State] {
    type Output = State;

    fn index(&self, index: StateIdx) -> &Self::Output {
        &self[index.0 as usize]
    }
}

impl ops::Index<StateIdx> for Vec<State> {
    type Output = State;

    fn index(&self, index: StateIdx) -> &Self::Output {
        &self[index.0 as usize]
    }
}

impl ops::IndexMut<StateIdx> for Vec<State> {
    fn index_mut(&mut self, index: StateIdx) -> &mut Self::Output {
        &mut self[index.0 as usize]
    }
}