metrale_grammar/earley/
accept.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Acceptable-next-byte computation for the Earley parser.
4//
5// The C++ matcher derives the set of bytes a parser can consume by
6// inspecting the outgoing char-range edges / sequence elements of every
7// latest scanable state. This module exposes that as a reusable query
8// so the W6 `GrammarMatcher` can build its token bitmask on top.
9
10use super::parser::EarleyParser;
11use super::state::ParserState;
12use crate::grammar::GrammarExprType;
13
14impl EarleyParser {
15    /// Append the byte ranges `state` can accept to `ranges` as
16    /// inclusive `(min, max)` pairs. FSM-backed states contribute their
17    /// char-range edges; non-FSM states contribute the current
18    /// element's byte/character-class ranges.
19    fn acceptable_ranges_of(&self, state: &ParserState, ranges: &mut Vec<(u8, u8)>) {
20        if state.rule_id != -1 {
21            let fsm = match self.grammar.per_rule_fsms[state.rule_id as usize].as_ref() {
22                Some(f) => f,
23                None => return,
24            };
25            for edge in fsm.fsm().edges(state.element_id as usize) {
26                if edge.is_char_range() {
27                    ranges.push((edge.min as u8, edge.max as u8));
28                }
29            }
30            return;
31        }
32        let seq = self.grammar.expr(state.sequence_id);
33        if state.element_id as usize >= seq.len() {
34            return;
35        }
36        let element = self.grammar.expr(seq[state.element_id as usize]);
37        match element.kind {
38            GrammarExprType::ByteString if (state.sub_element_id as usize) < element.len() => {
39                let b = element[state.sub_element_id as usize] as u8;
40                ranges.push((b, b));
41            }
42            GrammarExprType::CharacterClass | GrammarExprType::CharacterClassStar => {
43                // Only the ASCII portion of the ranges is a direct byte
44                // range; multi-byte handling is deferred to `advance`.
45                let mut i = 1;
46                while i + 1 < element.len() {
47                    let lo = element[i].clamp(0, 255) as u8;
48                    let hi = element[i + 1].clamp(0, 255) as u8;
49                    if element[i] <= 255 {
50                        ranges.push((lo, hi));
51                    }
52                    i += 2;
53                }
54            }
55            _ => {}
56        }
57    }
58
59    /// All byte ranges acceptable as the next input, across every
60    /// latest scanable state. Ranges may overlap and are unsorted.
61    pub fn acceptable_byte_ranges(&self) -> Vec<(u8, u8)> {
62        let mut ranges = Vec::new();
63        for state in self.latest_scanable_states() {
64            self.acceptable_ranges_of(state, &mut ranges);
65        }
66        ranges
67    }
68
69    /// A 256-entry bitmap: `out[b]` is true if byte `b` can be the next
70    /// input. This is the exact acceptable-next-byte set.
71    pub fn acceptable_byte_mask(&self) -> [bool; 256] {
72        let mut mask = [false; 256];
73        for (lo, hi) in self.acceptable_byte_ranges() {
74            for b in lo..=hi {
75                mask[b as usize] = true;
76            }
77        }
78        mask
79    }
80
81    /// True if byte `ch` can be accepted as the next input without
82    /// mutating the parser. Note: for negative character classes this
83    /// is a conservative pre-check; `advance` is authoritative.
84    pub fn can_accept(&self, ch: u8) -> bool {
85        self.acceptable_byte_mask()[ch as usize]
86    }
87}
metrale_grammar/earley/accept.rs

metrale_grammar/earley/
accept.rs
