vyre 0.4.0

//! Recursive descent — a bounded table-driven parser primitive.
//!
//! Parsing is sequential: a stack, a state machine, and a transition table.
//! Most GPU frameworks force you to fall back to CPU for this.  Vyre treats it
//! as a first-class primitive.  `recursive_descent` maintains an explicit
//! parser stack in workgroup SRAM, fires callbacks into an output buffer, and
//! validates bounds so the kernel cannot overflow workgroup memory.  The CPU
//! reference performs the exact same table walk with the same stack and
//! callback limits, giving conform a byte-identical target to verify against.

use crate::ops::AlgebraicLaw;
use crate::ir::transform::compiler::{U32X2_OUTPUTS, U32X5_INPUTS};
use crate::lower::wgsl::compiler::wgsl_backend;
use crate::ops::{IntrinsicDescriptor, OpSpec};
use thiserror::Error;

/// Portable WGSL source for the recursive-descent primitive.
#[must_use]
pub const fn source() -> &'static str {
    include_str!("../../../lower/wgsl/compiler/recursive_descent.wgsl")
}

impl RecursiveDescentOp {
    /// Declarative operation specification.
    pub const SPEC: OpSpec = OpSpec::intrinsic(
        "compiler_primitives.recursive_descent",
        U32X5_INPUTS,
        U32X2_OUTPUTS,
        LAWS,
        wgsl_backend,
        IntrinsicDescriptor::new("compiler_primitives_recursive_descent", "workgroup_stack", crate::ops::cpu_op::structured_intrinsic_cpu),
    );
}

/// Algebraic laws declared by the recursive-descent primitive.
pub const LAWS: &[AlgebraicLaw] = &[AlgebraicLaw::Bounded {
    lo: 0,
    hi: u32::MAX,
}];

/// Parse tokens using a bounded explicit stack and transition table.
///
/// # Errors
///
/// Returns `Fix: ...` when no transition matches, stack capacity is exceeded,
/// or the callback output buffer would overflow.
pub fn parse(
    tokens: &[u32],
    transitions: &[Transition],
    start_state: u32,
    accept_state: u32,
    max_stack: usize,
    max_callbacks: usize,
) -> Result<ParseResult, RecursiveDescentError> {
    let mut state = start_state;
    let mut stack = Vec::with_capacity(max_stack);
    let mut callbacks = Vec::new();
    let mut consumed = 0usize;
    while consumed < tokens.len() {
        let token = tokens[consumed];
        let transition = transitions
            .iter()
            .find(|candidate| candidate.state == state && candidate.token_kind == token)
            .copied()
            .ok_or(RecursiveDescentError::NoTransition { state, token })?;
        if transition.push_state != u32::MAX {
            if stack.len() == max_stack {
                return Err(RecursiveDescentError::StackOverflow { max_stack });
            }
            stack.push(transition.push_state);
        }
        if transition.callback != 0 {
            if callbacks.len() == max_callbacks {
                return Err(RecursiveDescentError::CallbackOverflow { max_callbacks });
            }
            callbacks.push(transition.callback);
        }
        state = if transition.next_state == u32::MAX {
            stack.pop().ok_or(RecursiveDescentError::StackUnderflow)?
        } else {
            transition.next_state
        };
        consumed += 1;
    }
    if state != accept_state {
        return Err(RecursiveDescentError::NotAccepted {
            state,
            accept_state,
        });
    }
    Ok(ParseResult {
        callbacks,
        consumed: u32::try_from(consumed).map_err(|_| RecursiveDescentError::TokenOverflow)?,
        final_state: state,
    })
}

/// Parser result emitted by the CPU reference.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ParseResult {
    /// Fired callback ids in input order.
    pub callbacks: Vec<u32>,
    /// Number of consumed tokens.
    pub consumed: u32,
    /// Final parser state.
    pub final_state: u32,
}

/// Recursive-descent parser validation errors.
#[derive(Debug, Clone, PartialEq, Eq, Error)]
pub enum RecursiveDescentError {
    /// No transition matches the current state and token.
    #[error("RecursiveDescentNoTransition: no transition for state {state} token {token}. Fix: add a grammar table edge or reject this token stream before dispatch.")]
    NoTransition {
        /// Parser state.
        state: u32,
        /// Token kind.
        token: u32,
    },
    /// Explicit parser stack exceeded its bound.
    #[error("RecursiveDescentStackOverflow: stack exceeded {max_stack} entries. Fix: increase workgroup.stack depth or split the grammar production.")]
    StackOverflow {
        /// Stack capacity.
        max_stack: usize,
    },
    /// Transition attempted to return without a caller state.
    #[error("RecursiveDescentStackUnderflow: return transition found an empty stack. Fix: validate push/return grammar balance.")]
    StackUnderflow,
    /// Callback sequence exceeded its output bound.
    #[error("RecursiveDescentCallbackOverflow: callback output exceeded {max_callbacks}. Fix: increase callback output capacity.")]
    CallbackOverflow {
        /// Callback capacity.
        max_callbacks: usize,
    },
    /// Parser ended in a non-accepting state.
    #[error("RecursiveDescentNotAccepted: final state {state} does not equal accept state {accept_state}. Fix: add a completion transition or reject incomplete input.")]
    NotAccepted {
        /// Final state.
        state: u32,
        /// Required accept state.
        accept_state: u32,
    },
    /// Consumed token count cannot fit in `u32`.
    #[error("RecursiveDescentTokenOverflow: consumed token count cannot fit u32. Fix: split the token stream.")]
    TokenOverflow,
}

/// Category C recursive-descent intrinsic.
#[derive(Debug, Default, Clone, Copy)]
pub struct RecursiveDescentOp;

/// Grammar transition for the table-walk parser.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Transition {
    /// Current parser state.
    pub state: u32,
    /// Token kind required by this transition.
    pub token_kind: u32,
    /// Next parser state.
    pub next_state: u32,
    /// Callback id emitted when the transition fires.
    pub callback: u32,
    /// Optional state to push before moving to `next_state`; `u32::MAX` means no push.
    pub push_state: u32,
}

/// Workgroup size used by the reference WGSL lowering.
pub const WORKGROUP_SIZE: [u32; 3] = [64, 1, 1];