Skip to main content

qualia_core_db/inference/
speculative_decode.rs

1//! A2 — Speculative Constrained Decoding (DOMINO).
2//!
3//! Subword-aligned prefix-trie token masking integrated into the in-process
4//! `QTensorEngine` decode loop. The approach:
5//!
6//! 1. **TokenTrie** — a prefix trie over token byte strings, built once from
7//!    the tokenizer vocabulary (cold path).
8//! 2. **GrammarState** — a state machine tracking which character classes and
9//!    keywords are valid at the current parse position, based on the VibeScript
10//!    0.1 GBNF grammar.
11//! 3. **DominoMasker** — combines the trie and grammar state to produce a logit
12//!    mask, setting disallowed tokens to `-inf` before sampling.
13//!
14//! The mask is applied per-token on the hot path using caller-supplied buffers
15//! (zero-heap). The trie is walked incrementally: at each decode step, the
16//! grammar state determines valid byte ranges, and the trie is traversed to
17//! find all token IDs whose byte sequences are valid continuations.
18//!
19//! ## Integration
20//!
21//! The masker is called between logit readback and the sampler:
22//! ```text
23//! logits = engine.readback_logits();
24//! masker.apply_mask(&mut logits, &accepted_tokens);
25//! token = sampler.sample(&mut logits, &ctx);
26//! ```
27//!
28//! When no grammar is active (unconstrained mode), `apply_mask` is a no-op.
29
30use std::collections::HashMap;
31
32// ── Token Trie ──────────────────────────────────────────────────────────────
33
34/// Maximum trie depth (longest token in bytes we support).
35pub const MAX_TRIE_DEPTH: usize = 32;
36
37/// A node in the token prefix trie.
38#[derive(Debug, Default, Clone)]
39struct TrieNode {
40    /// Children keyed by byte value.
41    children: HashMap<u8, TrieNode>,
42    /// Token IDs that terminate at this node (a token's bytes end here).
43    token_ids: Vec<u32>,
44}
45
46/// A prefix trie over token byte strings. Built once from the vocabulary.
47#[derive(Clone)]
48pub struct TokenTrie {
49    root: TrieNode,
50    vocab_size: usize,
51}
52
53impl TokenTrie {
54    /// Build a trie from a vocabulary: `(token_id, token_bytes)` pairs.
55    /// Cold path — allocation is expected here.
56    pub fn build(vocab: &[(u32, &[u8])]) -> Self {
57        let mut root = TrieNode::default();
58        let vocab_size = vocab.len();
59        for &(id, bytes) in vocab {
60            let mut node = &mut root;
61            for &b in bytes.iter().take(MAX_TRIE_DEPTH) {
62                node = node.children.entry(b).or_default();
63            }
64            node.token_ids.push(id);
65        }
66        Self { root, vocab_size }
67    }
68
69    /// Build from a tokenizer that provides `token_id → string` lookups.
70    pub fn build_from_strings(vocab: &[(u32, String)]) -> Self {
71        let refs: Vec<(u32, &[u8])> = vocab.iter().map(|(id, s)| (*id, s.as_bytes())).collect();
72        Self::build(&refs)
73    }
74
75    /// Walk the trie from the root, collecting all token IDs reachable via
76    /// bytes that pass the `byte_allowed` predicate. This is the core mask
77    /// computation: a token is valid iff every byte in its string passes
78    /// the predicate at the corresponding depth.
79    ///
80    /// Hot path — uses caller-supplied output buffer (zero-heap).
81    pub fn collect_valid(
82        &self,
83        byte_allowed: &dyn Fn(u8, usize) -> bool,
84        out: &mut [u32],
85    ) -> usize {
86        let mut count = 0;
87        self.walk(
88            &self.root,
89            byte_allowed,
90            &mut [0u8; MAX_TRIE_DEPTH],
91            0,
92            out,
93            &mut count,
94        );
95        count
96    }
97
98    fn walk(
99        &self,
100        node: &TrieNode,
101        byte_allowed: &dyn Fn(u8, usize) -> bool,
102        path: &mut [u8; MAX_TRIE_DEPTH],
103        depth: usize,
104        out: &mut [u32],
105        count: &mut usize,
106    ) {
107        // Emit token IDs at this node.
108        for &id in &node.token_ids {
109            if *count >= out.len() {
110                return;
111            }
112            out[*count] = id;
113            *count += 1;
114        }
115        if depth >= MAX_TRIE_DEPTH {
116            return;
117        }
118        for (&b, child) in &node.children {
119            if byte_allowed(b, depth) {
120                path[depth] = b;
121                self.walk(child, byte_allowed, path, depth + 1, out, count);
122            }
123        }
124    }
125
126    /// Number of tokens in the vocabulary.
127    pub fn vocab_size(&self) -> usize {
128        self.vocab_size
129    }
130}
131
132// ── Grammar State ───────────────────────────────────────────────────────────
133
134/// VibeScript 0.1 grammar parse states. These correspond to the non-terminals
135/// in `vibe-0.1.gbnf` that determine which characters are valid next.
136#[derive(Debug, Clone, Copy, PartialEq, Eq)]
137pub enum GrammarState {
138    /// Start of input — expects a cell (`=`) or module keyword.
139    Start,
140    /// After `=` — expects an expression.
141    CellExpr,
142    /// Expecting a keyword: `module`, `import`, `prefix`, `requires`, `fn`,
143    /// `on`, `let`, `return`, or an identifier (statement/expression).
144    KeywordOrIdent,
145    /// Inside whitespace — any amount of whitespace is consumed.
146    Whitespace,
147    /// Inside an identifier — `[A-Za-z0-9_]` continue, anything else ends it.
148    Ident,
149    /// Inside a number — `[0-9.]` continue.
150    Number,
151    /// Inside a string literal — `[^"\\]` or escape sequences continue.
152    String,
153    /// Inside an IRI — `[^<>\s]` continue.
154    Iri,
155    /// Inside a block — `{` entered, statements expected.
156    Block,
157    /// Inside a triple — `<<(` entered, three expressions expected.
158    Triple,
159    /// Inside a reified triple — `<<` entered.
160    Reified,
161    /// Inside a list — `[` entered.
162    List,
163    /// Inside a parenthesized expression.
164    Paren,
165    /// Unconstrained — no grammar active (free generation).
166    Unconstrained,
167}
168
169impl Default for GrammarState {
170    fn default() -> Self {
171        Self::Start
172    }
173}
174
175/// The grammar state machine. Tracks the current parse position and a stack
176/// of nested contexts (blocks, parens, triples, etc.) for proper nesting.
177#[derive(Clone)]
178pub struct GrammarStateMachine {
179    /// Current state.
180    state: GrammarState,
181    /// Stack of nested contexts (for closing braces/brackets/parens).
182    stack: Vec<GrammarState>,
183    /// The decoded text so far (for keyword matching).
184    text: String,
185    /// The state to return to after whitespace is consumed. This preserves
186    /// the semantic context (e.g. CellExpr, Block) across whitespace.
187    whitespace_parent: GrammarState,
188}
189
190impl GrammarStateMachine {
191    /// Creates `GrammarStateMachine` with the given state.
192    pub fn new() -> Self {
193        Self {
194            state: GrammarState::Start,
195            stack: Vec::new(),
196            text: String::new(),
197            whitespace_parent: GrammarState::Start,
198        }
199    }
200
201    /// Reset to initial state.
202    pub fn reset(&mut self) {
203        self.state = GrammarState::Start;
204        self.stack.clear();
205        self.text.clear();
206        self.whitespace_parent = GrammarState::Start;
207    }
208
209    /// Feed a decoded byte into the state machine, updating the state.
210    pub fn feed_byte(&mut self, b: u8) {
211        self.text.push(b as char);
212        self.state = self.transition(b);
213    }
214
215    /// Feed a decoded token's bytes.
216    pub fn feed_token(&mut self, bytes: &[u8]) {
217        for &b in bytes {
218            self.feed_byte(b);
219        }
220    }
221
222    /// Determine the next state given the current state and a byte.
223    fn transition(&mut self, b: u8) -> GrammarState {
224        use GrammarState::*;
225        let c = b as char;
226
227        // Whitespace is handled uniformly: save the semantic context and
228        // skip. When a non-whitespace byte arrives after whitespace, the
229        // `Whitespace` state dispatches based on `whitespace_parent`.
230        if c.is_whitespace() && self.state != Whitespace {
231            self.whitespace_parent = self.state;
232            return Whitespace;
233        }
234
235        match self.state {
236            Unconstrained => Unconstrained,
237            Start => {
238                if c == '=' {
239                    CellExpr
240                } else if c.is_alphabetic() || c == '_' {
241                    self.text.clear();
242                    self.text.push(c);
243                    Ident
244                } else {
245                    Unconstrained
246                }
247            }
248            Whitespace => {
249                if c.is_whitespace() {
250                    Whitespace
251                } else {
252                    // Dispatch based on the semantic context before whitespace.
253                    self.dispatch_after_whitespace(c)
254                }
255            }
256            CellExpr => {
257                if c.is_ascii_digit() || c == '-' {
258                    Number
259                } else if c == '"' {
260                    String
261                } else if c == '<' {
262                    Iri
263                } else if c == '[' {
264                    self.stack.push(List);
265                    List
266                } else if c == '(' {
267                    self.stack.push(Paren);
268                    Paren
269                } else if c.is_alphabetic() || c == '_' || c == '?' {
270                    self.text.clear();
271                    self.text.push(c);
272                    Ident
273                } else {
274                    Unconstrained
275                }
276            }
277            Ident => {
278                if c.is_alphanumeric() || c == '_' || c == '.' || c == '-' || c == ':' {
279                    Ident
280                } else if c == '{' {
281                    self.stack.push(Block);
282                    Block
283                } else if c == '(' {
284                    self.stack.push(Paren);
285                    Paren
286                } else if c == ';' {
287                    KeywordOrIdent
288                } else {
289                    Unconstrained
290                }
291            }
292            Number => {
293                if c.is_ascii_digit() || c == '.' {
294                    Number
295                } else if c == ';' {
296                    KeywordOrIdent
297                } else {
298                    Unconstrained
299                }
300            }
301            String => {
302                if c == '"' {
303                    // String ended — return to the context that contained it.
304                    if let Some(parent) = self.stack.last().copied() {
305                        parent
306                    } else {
307                        KeywordOrIdent
308                    }
309                } else {
310                    String
311                }
312            }
313            Iri => {
314                if c == '>' {
315                    if let Some(parent) = self.stack.last().copied() {
316                        parent
317                    } else {
318                        KeywordOrIdent
319                    }
320                } else {
321                    Iri
322                }
323            }
324            Block => {
325                if c == '}' {
326                    self.stack.pop();
327                    KeywordOrIdent
328                } else if c.is_alphabetic() || c == '_' {
329                    self.text.clear();
330                    self.text.push(c);
331                    Ident
332                } else {
333                    Unconstrained
334                }
335            }
336            Triple | Reified => self.transition_generic(c),
337            List => {
338                if c == ']' {
339                    self.stack.pop();
340                    if let Some(parent) = self.stack.last().copied() {
341                        parent
342                    } else {
343                        KeywordOrIdent
344                    }
345                } else {
346                    self.transition_generic(c)
347                }
348            }
349            Paren => {
350                if c == ')' {
351                    self.stack.pop();
352                    if let Some(parent) = self.stack.last().copied() {
353                        parent
354                    } else {
355                        KeywordOrIdent
356                    }
357                } else {
358                    self.transition_generic(c)
359                }
360            }
361            KeywordOrIdent => {
362                if c.is_alphabetic() || c == '_' {
363                    self.text.clear();
364                    self.text.push(c);
365                    Ident
366                } else if c == '}' {
367                    self.stack.pop();
368                    KeywordOrIdent
369                } else {
370                    Unconstrained
371                }
372            }
373        }
374    }
375
376    /// Dispatch after whitespace, based on the semantic context that preceded it.
377    fn dispatch_after_whitespace(&mut self, c: char) -> GrammarState {
378        use GrammarState::*;
379        match self.whitespace_parent {
380            Start | KeywordOrIdent => {
381                if c == '=' {
382                    CellExpr
383                } else if c == '{' {
384                    self.stack.push(Block);
385                    Block
386                } else if c.is_alphabetic() || c == '_' {
387                    self.text.clear();
388                    self.text.push(c);
389                    Ident
390                } else {
391                    Unconstrained
392                }
393            }
394            CellExpr => {
395                if c.is_ascii_digit() || c == '-' {
396                    Number
397                } else if c == '"' {
398                    String
399                } else if c == '<' {
400                    Iri
401                } else if c == '[' {
402                    self.stack.push(List);
403                    List
404                } else if c == '(' {
405                    self.stack.push(Paren);
406                    Paren
407                } else if c.is_alphabetic() || c == '_' || c == '?' {
408                    self.text.clear();
409                    self.text.push(c);
410                    Ident
411                } else {
412                    Unconstrained
413                }
414            }
415            Block => {
416                if c == '}' {
417                    self.stack.pop();
418                    KeywordOrIdent
419                } else if c.is_alphabetic() || c == '_' {
420                    self.text.clear();
421                    self.text.push(c);
422                    Ident
423                } else {
424                    Unconstrained
425                }
426            }
427            Ident => {
428                // After an identifier + whitespace, `(` (call/params), `{` (block),
429                // `;` (statement end) are valid.
430                if c == '(' {
431                    self.stack.push(Paren);
432                    Paren
433                } else if c == '{' {
434                    self.stack.push(Block);
435                    Block
436                } else if c == ';' {
437                    KeywordOrIdent
438                } else if c.is_alphabetic() || c == '_' {
439                    self.text.clear();
440                    self.text.push(c);
441                    Ident
442                } else {
443                    Unconstrained
444                }
445            }
446            _ => self.transition_generic(c),
447        }
448    }
449
450    fn transition_generic(&mut self, c: char) -> GrammarState {
451        if c.is_ascii_digit() || c == '-' {
452            GrammarState::Number
453        } else if c == '"' {
454            GrammarState::String
455        } else if c == '<' {
456            GrammarState::Iri
457        } else if c.is_alphabetic() || c == '_' || c == '?' {
458            self.text.clear();
459            self.text.push(c);
460            GrammarState::Ident
461        } else {
462            GrammarState::Unconstrained
463        }
464    }
465
466    /// Get the current grammar state.
467    pub fn state(&self) -> GrammarState {
468        self.state
469    }
470
471    /// Is the grammar currently active (not unconstrained)?
472    pub fn is_active(&self) -> bool {
473        self.state != GrammarState::Unconstrained
474    }
475
476    /// Determine if a byte is allowed at the current grammar position.
477    /// This is the predicate used by the trie walker.
478    pub fn byte_allowed(&self, b: u8, _depth: usize) -> bool {
479        use GrammarState::*;
480        let c = b as char;
481        match self.state {
482            Unconstrained => true,
483            Whitespace => {
484                // In whitespace, allowed bytes depend on the parent context.
485                if c.is_whitespace() {
486                    return true;
487                }
488                self.byte_allowed_parent(b)
489            }
490            Start => c.is_whitespace() || c == '=' || c.is_alphabetic() || c == '_',
491            CellExpr => {
492                c.is_whitespace()
493                    || c.is_ascii_digit()
494                    || c == '-'
495                    || c == '"'
496                    || c == '<'
497                    || c == '['
498                    || c == '('
499                    || c.is_alphabetic()
500                    || c == '_'
501                    || c == '?'
502            }
503            Ident => {
504                c.is_alphanumeric()
505                    || c == '_'
506                    || c == '.'
507                    || c == '-'
508                    || c == ':'
509                    || c.is_whitespace()
510                    || c == '{'
511                    || c == '('
512                    || c == ';'
513            }
514            Number => c.is_ascii_digit() || c == '.' || c.is_whitespace() || c == ';',
515            String => true, // Any byte can appear inside a string (escape sequences).
516            Iri => b != b'>' && !c.is_whitespace() || b == b'>',
517            Block => c.is_whitespace() || c == '}' || c.is_alphabetic() || c == '_',
518            List | Paren | Triple | Reified => {
519                c.is_whitespace()
520                    || c.is_ascii_digit()
521                    || c == '-'
522                    || c == '"'
523                    || c == '<'
524                    || c == '['
525                    || c == '('
526                    || c == ']'
527                    || c == ')'
528                    || c.is_alphabetic()
529                    || c == '_'
530                    || c == '?'
531            }
532            KeywordOrIdent => {
533                c.is_whitespace() || c.is_alphabetic() || c == '_' || c == '}' || c == '{'
534            }
535        }
536    }
537
538    /// Check if a byte is allowed based on the whitespace parent context.
539    fn byte_allowed_parent(&self, b: u8) -> bool {
540        use GrammarState::*;
541        let c = b as char;
542        match self.whitespace_parent {
543            Start | KeywordOrIdent => c == '=' || c == '{' || c.is_alphabetic() || c == '_',
544            CellExpr => {
545                c.is_ascii_digit()
546                    || c == '-'
547                    || c == '"'
548                    || c == '<'
549                    || c == '['
550                    || c == '('
551                    || c.is_alphabetic()
552                    || c == '_'
553                    || c == '?'
554            }
555            Block => c == '}' || c.is_alphabetic() || c == '_',
556            Ident => c == '(' || c == '{' || c == ';' || c.is_alphabetic() || c == '_',
557            _ => {
558                c.is_ascii_digit()
559                    || c == '-'
560                    || c == '"'
561                    || c == '<'
562                    || c == '['
563                    || c == '('
564                    || c == ']'
565                    || c == ')'
566                    || c.is_alphabetic()
567                    || c == '_'
568                    || c == '?'
569            }
570        }
571    }
572}
573
574impl Default for GrammarStateMachine {
575    fn default() -> Self {
576        Self::new()
577    }
578}
579
580// ── DOMINO Masker ───────────────────────────────────────────────────────────
581
582/// The DOMINO constrained decoding masker. Combines a token trie with a
583/// grammar state machine to produce logit masks.
584#[derive(Clone)]
585pub struct DominoMasker {
586    trie: TokenTrie,
587    grammar: GrammarStateMachine,
588    /// Scratch buffer for valid token IDs (reused across calls — zero-heap on hot path).
589    valid_buf: Vec<u32>,
590    /// Whether constrained decoding is active.
591    active: bool,
592}
593
594impl DominoMasker {
595    /// Create a new masker from a vocabulary. The trie is built once (cold path).
596    pub fn new(vocab: &[(u32, String)]) -> Self {
597        Self {
598            trie: TokenTrie::build_from_strings(vocab),
599            grammar: GrammarStateMachine::new(),
600            valid_buf: Vec::with_capacity(4096),
601            active: false,
602        }
603    }
604
605    /// Enable constrained decoding.
606    pub fn enable(&mut self) {
607        self.active = true;
608        self.grammar.reset();
609    }
610
611    /// Disable constrained decoding (free generation).
612    pub fn disable(&mut self) {
613        self.active = false;
614    }
615
616    /// Is constrained decoding active?
617    pub fn is_active(&self) -> bool {
618        self.active && self.grammar.is_active()
619    }
620
621    /// Apply the constraint mask to logits. Sets disallowed tokens to `-inf`.
622    /// When inactive, this is a no-op.
623    ///
624    /// Hot path — reuses internal scratch buffer, no allocation.
625    pub fn apply_mask(&mut self, logits: &mut [f32]) {
626        if !self.is_active() {
627            return;
628        }
629        // Collect valid token IDs from the trie.
630        self.valid_buf.clear();
631        self.valid_buf.resize(logits.len(), 0);
632        let grammar = &self.grammar;
633        let count = self.trie.collect_valid(
634            &|b, depth| grammar.byte_allowed(b, depth),
635            &mut self.valid_buf,
636        );
637        // Mask: set all logits to -inf, then restore valid ones.
638        // This is O(vocab) — acceptable at the one-fence-per-token cost.
639        for logit in logits.iter_mut() {
640            *logit = f32::NEG_INFINITY;
641        }
642        for i in 0..count {
643            let id = self.valid_buf[i] as usize;
644            if id < logits.len() {
645                logits[id] = 0.0; // Restore to a finite value (original logit is lost).
646            }
647        }
648    }
649
650    /// Apply the constraint mask while preserving original logit values.
651    /// Uses a snapshot approach: first save valid logits, then mask all,
652    /// then restore valid ones.
653    pub fn apply_mask_preserving(&mut self, logits: &mut [f32]) {
654        if !self.is_active() {
655            return;
656        }
657        self.valid_buf.clear();
658        self.valid_buf.resize(logits.len(), 0);
659        let grammar = &self.grammar;
660        let count = self.trie.collect_valid(
661            &|b, depth| grammar.byte_allowed(b, depth),
662            &mut self.valid_buf,
663        );
664        // Save valid logits, mask all, restore.
665        let mut saved = [0f32; 256];
666        for i in 0..count.min(saved.len()) {
667            let id = self.valid_buf[i] as usize;
668            if id < logits.len() {
669                saved[i] = logits[id];
670            }
671        }
672        for logit in logits.iter_mut() {
673            *logit = f32::NEG_INFINITY;
674        }
675        for i in 0..count.min(saved.len()) {
676            let id = self.valid_buf[i] as usize;
677            if id < logits.len() {
678                logits[id] = saved[i];
679            }
680        }
681    }
682
683    /// Feed a decoded token into the grammar state machine.
684    pub fn feed_token(&mut self, bytes: &[u8]) {
685        if self.active {
686            self.grammar.feed_token(bytes);
687        }
688    }
689
690    /// Feed a decoded token ID by looking up its bytes in the vocabulary.
691    pub fn feed_token_id(&mut self, token_id: u32, vocab: &[(u32, String)]) {
692        if !self.active {
693            return;
694        }
695        for &(id, ref s) in vocab {
696            if id == token_id {
697                self.grammar.feed_token(s.as_bytes());
698                return;
699            }
700        }
701    }
702
703    /// Get the current grammar state.
704    pub fn grammar_state(&self) -> GrammarState {
705        self.grammar.state()
706    }
707
708    /// Reset the grammar state machine (e.g., for a new generation).
709    pub fn reset(&mut self) {
710        self.grammar.reset();
711    }
712}
713
714// ── Tests ───────────────────────────────────────────────────────────────────
715
716#[cfg(test)]
717mod tests {
718    use super::*;
719
720    fn test_vocab() -> Vec<(u32, String)> {
721        vec![
722            (0, "=".to_string()),
723            (1, " ".to_string()),
724            (2, "\n".to_string()),
725            (3, "module".to_string()),
726            (4, "import".to_string()),
727            (5, "fn".to_string()),
728            (6, "let".to_string()),
729            (7, "return".to_string()),
730            (8, "x".to_string()),
731            (9, "42".to_string()),
732            (10, ";".to_string()),
733            (11, "\"hello\"".to_string()),
734            (12, "{".to_string()),
735            (13, "}".to_string()),
736            (14, "(".to_string()),
737            (15, ")".to_string()),
738            (16, "i32".to_string()),
739            (17, "=".to_string()),
740            (18, "1".to_string()),
741            (19, "2".to_string()),
742            (20, "test".to_string()),
743            (21, "abc".to_string()),
744        ]
745    }
746
747    #[test]
748    fn trie_build_and_lookup() {
749        let vocab = test_vocab();
750        let trie = TokenTrie::build_from_strings(&vocab);
751        assert_eq!(trie.vocab_size(), 22);
752        let mut out = [0u32; 64];
753        let count = trie.collect_valid(&|_b, _d| true, &mut out);
754        assert!(count > 0);
755    }
756
757    #[test]
758    fn trie_filters_by_byte_predicate() {
759        let vocab = test_vocab();
760        let trie = TokenTrie::build_from_strings(&vocab);
761        let mut out = [0u32; 64];
762        // Only allow '=' as first byte.
763        let count = trie.collect_valid(&|b, depth| depth == 0 && b == b'=', &mut out);
764        assert!(count > 0);
765        // All returned tokens should start with '='.
766        for i in 0..count {
767            assert!(out[i] == 0 || out[i] == 17); // "=" or "="
768        }
769    }
770
771    #[test]
772    fn grammar_state_start() {
773        let mut gsm = GrammarStateMachine::new();
774        assert_eq!(gsm.state(), GrammarState::Start);
775        gsm.feed_byte(b' ');
776        assert_eq!(gsm.state(), GrammarState::Whitespace);
777        gsm.feed_byte(b'=');
778        assert_eq!(gsm.state(), GrammarState::CellExpr);
779    }
780
781    #[test]
782    fn grammar_state_ident() {
783        let mut gsm = GrammarStateMachine::new();
784        gsm.feed_byte(b'x');
785        assert_eq!(gsm.state(), GrammarState::Ident);
786        gsm.feed_byte(b' ');
787        // After whitespace, state is Whitespace with parent=Ident.
788        assert_eq!(gsm.state(), GrammarState::Whitespace);
789        // Feeding another identifier transitions back to Ident.
790        gsm.feed_byte(b'y');
791        assert_eq!(gsm.state(), GrammarState::Ident);
792    }
793
794    #[test]
795    fn grammar_state_number() {
796        let mut gsm = GrammarStateMachine::new();
797        gsm.feed_byte(b'=');
798        gsm.feed_byte(b' ');
799        // After whitespace, parent is CellExpr → digit starts a number.
800        gsm.feed_byte(b'4');
801        assert_eq!(gsm.state(), GrammarState::Number);
802        gsm.feed_byte(b'2');
803        assert_eq!(gsm.state(), GrammarState::Number);
804    }
805
806    #[test]
807    fn grammar_state_string() {
808        let mut gsm = GrammarStateMachine::new();
809        gsm.feed_byte(b'=');
810        gsm.feed_byte(b' ');
811        // After whitespace, parent is CellExpr → `"` starts a string.
812        gsm.feed_byte(b'"');
813        assert_eq!(gsm.state(), GrammarState::String);
814        gsm.feed_byte(b'h');
815        assert_eq!(gsm.state(), GrammarState::String);
816        gsm.feed_byte(b'"');
817        // String ended.
818        assert_ne!(gsm.state(), GrammarState::String);
819    }
820
821    #[test]
822    fn grammar_state_block_nesting() {
823        let mut gsm = GrammarStateMachine::new();
824        // `fn x () {}`
825        gsm.feed_byte(b'f');
826        gsm.feed_byte(b'n');
827        assert_eq!(gsm.state(), GrammarState::Ident);
828        gsm.feed_byte(b' ');
829        assert_eq!(gsm.state(), GrammarState::Whitespace);
830        gsm.feed_byte(b'x');
831        assert_eq!(gsm.state(), GrammarState::Ident);
832        gsm.feed_byte(b' ');
833        assert_eq!(gsm.state(), GrammarState::Whitespace);
834        gsm.feed_byte(b'(');
835        assert_eq!(gsm.state(), GrammarState::Paren);
836        gsm.feed_byte(b')');
837        assert_ne!(gsm.state(), GrammarState::Paren);
838        gsm.feed_byte(b' ');
839        gsm.feed_byte(b'{');
840        assert_eq!(gsm.state(), GrammarState::Block);
841        gsm.feed_byte(b'}');
842        assert_ne!(gsm.state(), GrammarState::Block);
843    }
844
845    #[test]
846    fn domino_masker_inactive_noop() {
847        let vocab = test_vocab();
848        let mut masker = DominoMasker::new(&vocab);
849        let mut logits = [1.0f32, 2.0, 3.0, 4.0];
850        masker.apply_mask(&mut logits);
851        // Inactive — logits unchanged.
852        assert_eq!(logits, [1.0, 2.0, 3.0, 4.0]);
853    }
854
855    #[test]
856    fn domino_masker_active_masks() {
857        let vocab = test_vocab();
858        let mut masker = DominoMasker::new(&vocab);
859        masker.enable();
860        let mut logits = vec![1.0f32; 22];
861        masker.apply_mask(&mut logits);
862        // At Start state, only tokens starting with '=', whitespace, or alpha
863        // should be unmasked.
864        let unmasked = logits.iter().filter(|&&l| l > f32::NEG_INFINITY).count();
865        assert!(unmasked > 0, "at least some tokens should be valid");
866        assert!(unmasked < 22, "not all tokens should be valid at Start");
867    }
868
869    #[test]
870    fn domino_masker_feed_and_transition() {
871        let vocab = test_vocab();
872        let mut masker = DominoMasker::new(&vocab);
873        masker.enable();
874        // Feed '=' token.
875        masker.feed_token(b"=");
876        assert_eq!(masker.grammar_state(), GrammarState::CellExpr);
877        // Now only expression-starting tokens should be valid.
878        let mut logits = vec![1.0f32; 22];
879        masker.apply_mask(&mut logits);
880        let unmasked = logits.iter().filter(|&&l| l > f32::NEG_INFINITY).count();
881        assert!(unmasked > 0);
882    }
883
884    #[test]
885    fn domino_masker_reset() {
886        let vocab = test_vocab();
887        let mut masker = DominoMasker::new(&vocab);
888        masker.enable();
889        masker.feed_token(b"=");
890        assert_ne!(masker.grammar_state(), GrammarState::Start);
891        masker.reset();
892        assert_eq!(masker.grammar_state(), GrammarState::Start);
893    }
894
895    #[test]
896    fn domino_masker_disable() {
897        let vocab = test_vocab();
898        let mut masker = DominoMasker::new(&vocab);
899        masker.enable();
900        assert!(masker.is_active());
901        masker.disable();
902        assert!(!masker.is_active());
903        let mut logits = vec![1.0f32; 22];
904        masker.apply_mask(&mut logits);
905        // All logits unchanged.
906        assert!(logits.iter().all(|&l| l == 1.0));
907    }
908
909    #[test]
910    fn domino_masker_preserving() {
911        let vocab = test_vocab();
912        let mut masker = DominoMasker::new(&vocab);
913        masker.enable();
914        let mut logits = vec![1.0f32, 2.0, 3.0, 4.0, 5.0];
915        let original = logits.clone();
916        masker.apply_mask_preserving(&mut logits);
917        // Valid tokens should have their original values, invalid should be -inf.
918        let has_neg_inf = logits.iter().any(|&l| l == f32::NEG_INFINITY);
919        assert!(has_neg_inf, "some tokens should be masked");
920        let has_original = logits.iter().enumerate().any(|(i, &l)| l == original[i]);
921        assert!(has_original, "some tokens should be unmasked");
922    }
923
924    #[test]
925    fn byte_allowed_start_state() {
926        let gsm = GrammarStateMachine::new();
927        // At Start: whitespace, '=', alpha, '_' allowed.
928        assert!(gsm.byte_allowed(b' ', 0));
929        assert!(gsm.byte_allowed(b'=', 0));
930        assert!(gsm.byte_allowed(b'x', 0));
931        assert!(gsm.byte_allowed(b'_', 0));
932        // Digits, '{', etc. not allowed at Start.
933        assert!(!gsm.byte_allowed(b'1', 0));
934        assert!(!gsm.byte_allowed(b'{', 0));
935    }
936
937    #[test]
938    fn byte_allowed_cell_expr_state() {
939        let mut gsm = GrammarStateMachine::new();
940        gsm.feed_byte(b'=');
941        // At CellExpr (before whitespace): digits, strings, idents, etc. allowed.
942        assert!(gsm.byte_allowed(b'1', 0));
943        assert!(gsm.byte_allowed(b'"', 0));
944        assert!(gsm.byte_allowed(b'x', 0));
945    }
946
947    #[test]
948    fn trie_max_depth_respected() {
949        let vocab = vec![(0, "a".repeat(40))];
950        let trie = TokenTrie::build_from_strings(&vocab);
951        let mut out = [0u32; 10];
952        let count = trie.collect_valid(&|_b, _d| true, &mut out);
953        // Token longer than MAX_TRIE_DEPTH should still be indexed (truncated).
954        assert!(count > 0);
955    }
956
957    #[test]
958    fn grammar_unconstrained_relax() {
959        let mut gsm = GrammarStateMachine::new();
960        // Feed an unexpected byte at Start.
961        gsm.feed_byte(b'!');
962        assert_eq!(gsm.state(), GrammarState::Unconstrained);
963        // Once unconstrained, everything is allowed.
964        assert!(gsm.byte_allowed(b'x', 0));
965        assert!(gsm.byte_allowed(b'!', 0));
966    }
967}
968
969#[path = "speculative_decode/prepared.rs"]
970mod prepared;
971pub use prepared::{DominoPreparationBudget, PreparedDomino};