1use std::collections::HashMap;
31
32pub const MAX_TRIE_DEPTH: usize = 32;
36
37#[derive(Debug, Default, Clone)]
39struct TrieNode {
40 children: HashMap<u8, TrieNode>,
42 token_ids: Vec<u32>,
44}
45
46#[derive(Clone)]
48pub struct TokenTrie {
49 root: TrieNode,
50 vocab_size: usize,
51}
52
53impl TokenTrie {
54 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 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 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 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 pub fn vocab_size(&self) -> usize {
128 self.vocab_size
129 }
130}
131
132#[derive(Debug, Clone, Copy, PartialEq, Eq)]
137pub enum GrammarState {
138 Start,
140 CellExpr,
142 KeywordOrIdent,
145 Whitespace,
147 Ident,
149 Number,
151 String,
153 Iri,
155 Block,
157 Triple,
159 Reified,
161 List,
163 Paren,
165 Unconstrained,
167}
168
169impl Default for GrammarState {
170 fn default() -> Self {
171 Self::Start
172 }
173}
174
175#[derive(Clone)]
178pub struct GrammarStateMachine {
179 state: GrammarState,
181 stack: Vec<GrammarState>,
183 text: String,
185 whitespace_parent: GrammarState,
188}
189
190impl GrammarStateMachine {
191 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 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 pub fn feed_byte(&mut self, b: u8) {
211 self.text.push(b as char);
212 self.state = self.transition(b);
213 }
214
215 pub fn feed_token(&mut self, bytes: &[u8]) {
217 for &b in bytes {
218 self.feed_byte(b);
219 }
220 }
221
222 fn transition(&mut self, b: u8) -> GrammarState {
224 use GrammarState::*;
225 let c = b as char;
226
227 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 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 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 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 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 pub fn state(&self) -> GrammarState {
468 self.state
469 }
470
471 pub fn is_active(&self) -> bool {
473 self.state != GrammarState::Unconstrained
474 }
475
476 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 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, 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 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#[derive(Clone)]
585pub struct DominoMasker {
586 trie: TokenTrie,
587 grammar: GrammarStateMachine,
588 valid_buf: Vec<u32>,
590 active: bool,
592}
593
594impl DominoMasker {
595 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 pub fn enable(&mut self) {
607 self.active = true;
608 self.grammar.reset();
609 }
610
611 pub fn disable(&mut self) {
613 self.active = false;
614 }
615
616 pub fn is_active(&self) -> bool {
618 self.active && self.grammar.is_active()
619 }
620
621 pub fn apply_mask(&mut self, logits: &mut [f32]) {
626 if !self.is_active() {
627 return;
628 }
629 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 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; }
647 }
648 }
649
650 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 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 pub fn feed_token(&mut self, bytes: &[u8]) {
685 if self.active {
686 self.grammar.feed_token(bytes);
687 }
688 }
689
690 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 pub fn grammar_state(&self) -> GrammarState {
705 self.grammar.state()
706 }
707
708 pub fn reset(&mut self) {
710 self.grammar.reset();
711 }
712}
713
714#[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 let count = trie.collect_valid(&|b, depth| depth == 0 && b == b'=', &mut out);
764 assert!(count > 0);
765 for i in 0..count {
767 assert!(out[i] == 0 || out[i] == 17); }
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 assert_eq!(gsm.state(), GrammarState::Whitespace);
789 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 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 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 assert_ne!(gsm.state(), GrammarState::String);
819 }
820
821 #[test]
822 fn grammar_state_block_nesting() {
823 let mut gsm = GrammarStateMachine::new();
824 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 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 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 masker.feed_token(b"=");
876 assert_eq!(masker.grammar_state(), GrammarState::CellExpr);
877 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 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 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 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 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 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 assert!(count > 0);
955 }
956
957 #[test]
958 fn grammar_unconstrained_relax() {
959 let mut gsm = GrammarStateMachine::new();
960 gsm.feed_byte(b'!');
962 assert_eq!(gsm.state(), GrammarState::Unconstrained);
963 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};