metrale_grammar/matcher/
mod.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Grammar matcher — port wave W6, the final algorithmic subsystem.
4//
5// Pure-Rust port of `cpp/grammar_matcher.cc` + `include/xgrammar/
6// matcher.h`. The matcher is the per-request, per-decode-step state
7// Metrale Engine drives: it accepts sampled tokens, fills the next-token accept
8// bitmask, supports rollback (for speculative decoding) and detects
9// termination.
10//
11// Module map:
12//   bitmask  — `TokenBitmask` / `BitmaskSlice`: the packed i32
13//              bit-per-token mask, byte-compatible with the upstream
14//              CUDA `apply_token_bitmask` kernel.
15//   matcher  — `GrammarMatcher`: construction, accept token/string,
16//              rollback, termination, reset.
17//   fill     — `FillNextTokenBitmask` + `FindJumpForwardString`.
18//   coalesce — Coalescence forced-token fast-path (Tier 3b):
19//              `forced_token` / `next_forced_tokens`.
20//   completion — `find_completion_to_accept`: shortest grammar-legal
21//              close to a stop-legal state (Metrale Engine budget-aware close).
22//   batch    — `BatchGrammarMatcher`: parallel batched bitmask fill.
23//
24// PORT NOTES / SIMPLIFICATIONS vs C++
25// -----------------------------------
26//  * The C++ `Impl` inherits `EarleyParser`; the Rust port composes
27//    one. The parser already exposes `advance` / `pop_last_states` /
28//    `push_one_state_to_check` / `is_completed`.
29//  * The C++ matcher reads `stop_token_is_accepted_` off the parser
30//    base. That field is cleared on every `pop_last_states`, which is
31//    wrong for a matcher rollback that does not reach the stop step.
32//    The Rust matcher owns its own `stop_token_accepted` flag, undone
33//    precisely by `rollback` via the zero-length history entry.
34//  * The bitmask is a packed `i32` slice / owned `TokenBitmask` rather
35//    than a `DLTensor` — the W7 API shim adapts it to Metrale Engine's tensor.
36//  * `BatchGrammarMatcher`'s parallel path requires the natural
37//    matcher-to-slice mapping (see `batch.rs`); an arbitrary `indices`
38//    permutation falls back to the (always-correct) sequential path.
39//  * `max_rollback_tokens` is accepted but ignored — the C++ also
40//    deprecated and ignores it; rollback is unbounded.
41//  * `_DebugPrintInternalState` is not ported (debug-only, the C++
42//    notes its representation is unstable).
43
44mod batch;
45mod bitmask;
46mod coalesce;
47mod completion;
48mod fill;
49// The `GrammarMatcher` struct lives in `matcher.rs`; the file split
50// (struct vs. `fill.rs`) is required by the 250-line-per-file cap.
51#[allow(clippy::module_inception)]
52mod matcher;
53
54pub use batch::BatchGrammarMatcher;
55pub use bitmask::{BITS_PER_WORD, BitmaskSlice, TokenBitmask, bitmask_size};
56pub use fill::FillError;
57pub use matcher::GrammarMatcher;
58
59#[cfg(test)]
60mod tests;
metrale_grammar/matcher/mod.rs

metrale_grammar/matcher/
mod.rs
