Skip to main content

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}