typesayer_parser/marker.rs
1// Copyright 2026 Thomas Santerre and Moderately AI Inc.
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Tail-buffered marker detector for the streaming chat-adapter parser.
6//!
7//! Scans incoming text chunks for `[[ ## <name> ## ]]` patterns. The
8//! tricky case is markers split across token boundaries: a chunk might
9//! end with `[[ ##` and the next chunk start with ` fname ## ]]`. The
10//! detector holds an internal tail buffer of ambiguous trailing bytes
11//! that could be the start of a marker until either the marker
12//! completes or enough non-marker content arrives to confirm the bytes
13//! are literal content (e.g. a string field happens to contain `[[`).
14//!
15//! Used by [`super::parser::ChatStreamParser`]; not part of the
16//! public adapter API.
17
18use std::sync::LazyLock;
19
20use regex::Regex;
21
22/// Full-marker regex. Captures the field name. Mirrors
23/// `FIELD_MARKER` from `typesayer` — kept as a sibling rather than
24/// re-exported because the streaming detector wraps it with tail-
25/// buffering logic that doesn't belong on the buffered parser.
26#[expect(
27 clippy::expect_used,
28 reason = "static LazyLock built from a literal regex: compile-time verifiable, \
29 so a runtime parse failure would mean the binary was linked against \
30 a broken `regex` crate and panicking at first-use is the only \
31 meaningful recovery"
32)]
33static FULL_MARKER: LazyLock<Regex> =
34 LazyLock::new(|| Regex::new(r"\[\[ ## (\w+) ## \]\]").expect("static regex is always valid"));
35
36/// Result of one scan of `tail_buffer + chunk`.
37#[derive(Debug, PartialEq, Eq)]
38pub(super) enum MarkerScan {
39 /// No complete marker found. `content_before` is the prefix of the
40 /// working slice that's safe to forward to the current field
41 /// parser as plain content. The detector's tail buffer holds the
42 /// remaining bytes that could be the start of a marker.
43 NoMarker { content_before: String },
44 /// A complete marker was found. `content_before` is content prior
45 /// to the marker; `name` is the captured field name; `remainder`
46 /// is everything after the marker — caller passes it back via
47 /// another `push` to continue scanning (or holds it internally
48 /// during a re-entrant scan).
49 MarkerFound {
50 content_before: String,
51 name: String,
52 remainder: String,
53 },
54}
55
56/// Detects `[[ ## name ## ]]` markers across token-stream chunks with
57/// tail-buffering to handle markers split mid-token.
58#[derive(Debug, Default)]
59pub(super) struct MarkerDetector {
60 tail_buffer: String,
61}
62
63impl MarkerDetector {
64 pub(super) fn new() -> Self {
65 Self::default()
66 }
67
68 /// Feed one chunk in; return the next scan result. May leave the
69 /// detector with a non-empty tail buffer if the chunk ends with
70 /// what looks like the start of a marker.
71 pub(super) fn push(&mut self, chunk: &str) -> MarkerScan {
72 // Fast path: tail buffer empty (true on the vast majority of
73 // streaming pushes; `tail_buffer` is non-empty only briefly,
74 // while a possible marker prefix is being assembled). Scan
75 // `chunk` directly to avoid the up-front concatenation alloc.
76 if self.tail_buffer.is_empty() {
77 return Self::scan(chunk, &mut self.tail_buffer);
78 }
79
80 // Slow path: held bytes from a previous push need to be
81 // combined with `chunk` before scanning so a marker split
82 // across chunk boundaries is detected when its closing bytes
83 // arrive.
84 let mut working = std::mem::take(&mut self.tail_buffer);
85 working.push_str(chunk);
86 Self::scan(&working, &mut self.tail_buffer)
87 }
88
89 /// Scan one already-combined working slice for a marker and either
90 /// return [`MarkerScan::MarkerFound`] or, on no match, refill
91 /// `tail_buffer_out` with the longest trailing potential-prefix
92 /// slice and return [`MarkerScan::NoMarker`]. Pulled out of `push`
93 /// so the empty-tail fast path can call it on a borrowed chunk
94 /// without first allocating an owned working copy.
95 fn scan(working: &str, tail_buffer_out: &mut String) -> MarkerScan {
96 if let Some(cap) = FULL_MARKER.captures(working) {
97 let full_match = cap.get(0).unwrap_or_else(|| {
98 unreachable!("regex group 0 always present on a match");
99 });
100 let name = cap.get(1).unwrap_or_else(|| {
101 unreachable!("regex group 1 always present on this pattern");
102 });
103 return MarkerScan::MarkerFound {
104 content_before: working[..full_match.start()].to_owned(),
105 name: name.as_str().to_owned(),
106 remainder: working[full_match.end()..].to_owned(),
107 };
108 }
109
110 // No complete marker. Find the longest trailing slice of
111 // `working` that could be a partial marker prefix. Everything
112 // before that slice is safe to forward; the slice itself
113 // refills the tail buffer.
114 let split_point = longest_partial_marker_suffix_start(working);
115 let content_before = working[..split_point].to_owned();
116 working[split_point..].clone_into(tail_buffer_out);
117 MarkerScan::NoMarker { content_before }
118 }
119
120 /// Drain any held tail bytes at end-of-stream. Called by the
121 /// parser's `finish()` to recover content that was held against a
122 /// possible-marker hypothesis the LM never completed (e.g. a
123 /// string field that ended with literal `[[`).
124 pub(super) fn drain_tail(&mut self) -> String {
125 std::mem::take(&mut self.tail_buffer)
126 }
127
128 #[cfg(test)]
129 pub(super) fn tail(&self) -> &str {
130 &self.tail_buffer
131 }
132}
133
134/// Find the byte index where a suffix of `s` starts that could be the
135/// beginning of a marker. Returns `s.len()` when no suffix could be a
136/// marker prefix (so the whole buffer is safe to forward).
137///
138/// Walks back at most `MAX_MARKER_PREFIX` bytes — beyond that the
139/// suffix is too long to be a marker prefix (markers cap at the field
140/// name's length, and we don't see fields longer than a few dozen
141/// chars in practice). Bounded scan keeps the per-chunk cost O(1)
142/// regardless of buffer size.
143fn longest_partial_marker_suffix_start(s: &str) -> usize {
144 let bytes = s.as_bytes();
145 let scan_start = bytes.len().saturating_sub(MAX_MARKER_PREFIX);
146
147 // Walk forward from scan_start; for each `[` we find, check if the
148 // suffix from that point could be a marker prefix. Return the
149 // earliest such position. That's the longest suffix that's
150 // ambiguous; everything before it is safe to forward.
151 for i in scan_start..bytes.len() {
152 if bytes[i] == b'[' && is_potential_marker_prefix(&s[i..]) {
153 return i;
154 }
155 }
156 bytes.len()
157}
158
159/// Bound on how far back we scan for a potential marker prefix.
160/// `"[[ ## " + 64 word chars + " ## ]"` = 12 + 64 = 76. Use 128 to be
161/// safe against any reasonable field-name length without scanning
162/// unbounded history.
163const MAX_MARKER_PREFIX: usize = 128;
164
165/// Returns `true` if `s` could be extended to form a complete
166/// `[[ ## name ## ]]` marker. Walks the fixed grammar with a small
167/// state machine; on the first character that violates the grammar,
168/// returns `false`. Empty input returns `false` (nothing to buffer).
169///
170/// Crucially, returns `false` for a COMPLETE marker — the caller's
171/// regex path handles those; this function is only for prefixes that
172/// need to wait for more bytes.
173fn is_potential_marker_prefix(s: &str) -> bool {
174 if s.is_empty() {
175 return false;
176 }
177 let mut st = State::Start;
178 for ch in s.chars() {
179 st = match (st, ch) {
180 (State::Start, '[') => State::Bracket1,
181 (State::Bracket1, '[') => State::Bracket2,
182 (State::Bracket2, ' ') => State::Space1,
183 (State::Space1, '#') => State::Hash1a,
184 (State::Hash1a, '#') => State::Hash1b,
185 (State::Hash1b, ' ') => State::Space2,
186 (State::Space2, c) if is_name_char(c) => State::InsideName,
187 (State::InsideName, c) if is_name_char(c) => State::InsideName,
188 (State::InsideName, ' ') => State::Space3,
189 (State::Space3, '#') => State::Hash2a,
190 (State::Hash2a, '#') => State::Hash2b,
191 (State::Hash2b, ' ') => State::Space4,
192 (State::Space4, ']') => State::CloseBracket1,
193 // A COMPLETE marker (CloseBracket1 + ']') would terminate the
194 // partial-prefix scan, but the FULL_MARKER regex already
195 // handled the complete-marker case before we entered the
196 // partial-prefix path — so by the time we reach the
197 // CloseBracket1 state here, the partial-prefix hypothesis is
198 // refuted and we collapse it with the rest of the failures.
199 _ => return false,
200 }
201 }
202 true
203}
204
205const fn is_name_char(c: char) -> bool {
206 c.is_ascii_alphanumeric() || c == '_'
207}
208
209#[derive(Debug, Clone, Copy)]
210enum State {
211 Start,
212 Bracket1,
213 Bracket2,
214 Space1,
215 Hash1a,
216 Hash1b,
217 Space2,
218 InsideName,
219 Space3,
220 Hash2a,
221 Hash2b,
222 Space4,
223 CloseBracket1,
224}
225
226#[cfg(test)]
227mod tests {
228 use super::*;
229
230 fn detect_one(chunk: &str) -> MarkerScan {
231 let mut d = MarkerDetector::new();
232 d.push(chunk)
233 }
234
235 #[test]
236 fn complete_marker_in_one_chunk() {
237 match detect_one("hello [[ ## answer ## ]] world") {
238 MarkerScan::MarkerFound {
239 content_before,
240 name,
241 remainder,
242 } => {
243 assert_eq!(content_before, "hello ");
244 assert_eq!(name, "answer");
245 assert_eq!(remainder, " world");
246 }
247 scan @ MarkerScan::NoMarker { .. } => {
248 panic!("expected MarkerFound, got {scan:?}")
249 }
250 }
251 }
252
253 #[test]
254 fn multiple_markers_in_one_chunk() {
255 // The detector returns the FIRST marker; ChatStreamParser
256 // re-pushes the `remainder` to find the next one. Verify
257 // both calls cleanly hit MarkerFound — this is the loop
258 // semantics ChatStreamParser::process relies on.
259 let mut d = MarkerDetector::new();
260 let scan_a = d.push("[[ ## a ## ]]content1[[ ## b ## ]]content2");
261 let remainder_after_a = match scan_a {
262 MarkerScan::MarkerFound {
263 content_before,
264 name,
265 remainder,
266 } => {
267 assert_eq!(content_before, "");
268 assert_eq!(name, "a");
269 remainder
270 }
271 scan @ MarkerScan::NoMarker { .. } => {
272 panic!("expected MarkerFound(a), got {scan:?}")
273 }
274 };
275 // Re-push the remainder; the detector should find marker `b`.
276 match d.push(&remainder_after_a) {
277 MarkerScan::MarkerFound {
278 content_before,
279 name,
280 remainder,
281 } => {
282 assert_eq!(content_before, "content1");
283 assert_eq!(name, "b");
284 assert_eq!(remainder, "content2");
285 }
286 scan @ MarkerScan::NoMarker { .. } => {
287 panic!("expected MarkerFound(b), got {scan:?}")
288 }
289 }
290 // Tail should be empty after the second marker found.
291 assert_eq!(d.tail(), "");
292 }
293
294 #[test]
295 fn empty_chunk_handled_safely() {
296 // Empty input must not panic, must not leave the tail
297 // buffer holding anything, and must report no content.
298 let mut d = MarkerDetector::new();
299 match d.push("") {
300 MarkerScan::NoMarker { content_before } => assert_eq!(content_before, ""),
301 scan @ MarkerScan::MarkerFound { .. } => {
302 panic!("expected NoMarker for empty input, got {scan:?}")
303 }
304 }
305 assert_eq!(d.tail(), "");
306 // A second empty push should also be a no-op.
307 match d.push("") {
308 MarkerScan::NoMarker { content_before } => assert_eq!(content_before, ""),
309 scan @ MarkerScan::MarkerFound { .. } => panic!("got {scan:?}"),
310 }
311 assert_eq!(d.tail(), "");
312 }
313
314 #[test]
315 fn no_marker_clean_content() {
316 let mut d = MarkerDetector::new();
317 match d.push("just text here") {
318 MarkerScan::NoMarker { content_before } => {
319 assert_eq!(content_before, "just text here");
320 }
321 scan @ MarkerScan::MarkerFound { .. } => {
322 panic!("expected NoMarker, got {scan:?}")
323 }
324 }
325 assert_eq!(d.tail(), "");
326 }
327
328 #[test]
329 fn marker_split_across_chunks_at_every_boundary() {
330 let full = "before [[ ## fname ## ]] after";
331 // Try splitting `full` at every character boundary; the union
332 // of the two pushes' results should reconstruct the same
333 // content-before / name / content-after as the single-chunk
334 // case.
335 for split in 1..full.len() {
336 let mut d = MarkerDetector::new();
337 let first = d.push(&full[..split]);
338 let second = d.push(&full[split..]);
339
340 // Exactly one of the two pushes must report MarkerFound.
341 // NoMarker.content_before semantics depend on whether the
342 // marker has been seen: BEFORE the marker, it's pre-marker
343 // safe-to-forward content; AFTER the marker, it's
344 // trailing content that belongs in `remainder`.
345 let mut content_before = String::new();
346 let mut name: Option<String> = None;
347 let mut remainder = String::new();
348 let mut marker_found = false;
349 for scan in [first, second] {
350 match scan {
351 MarkerScan::NoMarker { content_before: c } => {
352 if marker_found {
353 remainder.push_str(&c);
354 } else {
355 content_before.push_str(&c);
356 }
357 }
358 MarkerScan::MarkerFound {
359 content_before: c,
360 name: n,
361 remainder: r,
362 } => {
363 content_before.push_str(&c);
364 name = Some(n);
365 remainder.push_str(&r);
366 marker_found = true;
367 }
368 }
369 }
370 assert_eq!(name.as_deref(), Some("fname"), "split={split}");
371 assert_eq!(content_before, "before ", "split={split}");
372 assert_eq!(remainder, " after", "split={split}");
373 assert_eq!(
374 d.tail(),
375 "",
376 "tail should be empty after marker found; split={split}"
377 );
378 }
379 }
380
381 #[test]
382 fn tail_buffer_holds_partial_marker_prefixes() {
383 let prefixes = [
384 "[",
385 "[[",
386 "[[ ",
387 "[[ #",
388 "[[ ##",
389 "[[ ## ",
390 "[[ ## fname",
391 "[[ ## fname ",
392 "[[ ## fname #",
393 "[[ ## fname ##",
394 "[[ ## fname ## ",
395 "[[ ## fname ## ]",
396 ];
397 for prefix in prefixes {
398 let mut d = MarkerDetector::new();
399 let chunk = format!("safe content {prefix}");
400 match d.push(&chunk) {
401 MarkerScan::NoMarker { content_before } => {
402 assert_eq!(content_before, "safe content ", "prefix={prefix:?}");
403 assert_eq!(d.tail(), prefix, "prefix={prefix:?}");
404 }
405 scan @ MarkerScan::MarkerFound { .. } => {
406 panic!("expected NoMarker for prefix {prefix:?}, got {scan:?}")
407 }
408 }
409 }
410 }
411
412 #[test]
413 fn literal_double_bracket_not_marker_flushes_after_disambiguation() {
414 let mut d = MarkerDetector::new();
415 // First push: `[[` buffered, content_before is "literal "
416 match d.push("literal [[") {
417 MarkerScan::NoMarker { content_before } => assert_eq!(content_before, "literal "),
418 scan @ MarkerScan::MarkerFound { .. } => panic!("got {scan:?}"),
419 }
420 assert_eq!(d.tail(), "[[");
421 // Second push extends the tail with characters that break the
422 // marker grammar — `[[!` is not a marker prefix. The detector
423 // should flush.
424 match d.push("!not marker") {
425 MarkerScan::NoMarker { content_before } => {
426 assert_eq!(content_before, "[[!not marker");
427 }
428 scan @ MarkerScan::MarkerFound { .. } => panic!("got {scan:?}"),
429 }
430 assert_eq!(d.tail(), "");
431 }
432
433 #[test]
434 fn completed_marker_split_across_chunks() {
435 let mut d = MarkerDetector::new();
436 let s1 = d.push("[[ ## comple");
437 match s1 {
438 MarkerScan::NoMarker { content_before } => assert_eq!(content_before, ""),
439 scan @ MarkerScan::MarkerFound { .. } => {
440 panic!("expected NoMarker, got {scan:?}")
441 }
442 }
443 match d.push("ted ## ]]") {
444 MarkerScan::MarkerFound {
445 content_before,
446 name,
447 remainder,
448 } => {
449 assert_eq!(content_before, "");
450 assert_eq!(name, "completed");
451 assert_eq!(remainder, "");
452 }
453 scan @ MarkerScan::NoMarker { .. } => {
454 panic!("expected MarkerFound, got {scan:?}")
455 }
456 }
457 }
458
459 #[test]
460 fn drain_tail_returns_held_bytes() {
461 let mut d = MarkerDetector::new();
462 d.push("content [[ ##");
463 assert_eq!(d.tail(), "[[ ##");
464 assert_eq!(d.drain_tail(), "[[ ##");
465 assert_eq!(d.tail(), "");
466 }
467
468 #[test]
469 fn potential_prefix_rejects_complete_marker() {
470 // A COMPLETE marker should NOT be a "potential prefix" — the
471 // regex path handles those. This guarantees we don't double-
472 // count a complete marker as also-a-prefix-of-itself.
473 assert!(!is_potential_marker_prefix("[[ ## x ## ]]"));
474 }
475
476 #[test]
477 fn potential_prefix_rejects_garbage() {
478 for s in ["foo", "[x", "[[ #x", "[[ ## name## ]]", "[[ ## name ## ] ]"] {
479 assert!(!is_potential_marker_prefix(s), "should reject {s:?}");
480 }
481 }
482}