Skip to main content

text_chipper/
chunker.rs

1use std::cell::RefCell;
2use std::collections::HashMap;
3use std::sync::Arc;
4use unicode_segmentation::UnicodeSegmentation;
5
6use super::{
7    backend::{record_event, Backend, CountSite},
8    block::{Block, Headers},
9    chunk_types::{context_prefix, fit_context_headers, Chunk, ChunkConfig},
10    markdown::BlockParser,
11    split_engine::{
12        char_len, empty_headers, split_by_tokens_with_lists_known, trim_bounds, ListCuts, Origin,
13    },
14    ChipError,
15};
16
17/// Upper bound for the chunker's retained pending text plus deferred heading prefix.
18const MAX_PENDING_STATE_BYTES: usize = 2 * 1024 * 1024;
19/// Only cache short, repeatedly occurring structural fragments. This keeps both hashing
20/// overhead and retained memory bounded for varied documents.
21/// Blocks up to this size are always counted whole by `count_block_text`; larger ones may be
22/// answered with a prefix lower bound. A count is therefore exact iff `len <= this`.
23const BLOCK_PROBE_MIN_BYTES: usize = 16 * 1024;
24const SMALL_COUNT_CACHE_MAX_TEXT_BYTES: usize = 128;
25const SMALL_COUNT_CACHE_MAX_ENTRIES: usize = 256;
26
27// Pending-chunk state and the SmartChunker (block-level packing).
28
29#[derive(Clone)]
30pub(crate) struct Pending {
31    pub(crate) text: String,
32    start_byte: usize,
33    start_char: usize,
34    /// Estimated body-only tokens (exact right after an exact count or for a single block).
35    tokens: usize,
36    /// Exact token count of the delivered text (context prefix + body) when known.
37    exact_total: Option<usize>,
38    /// Block joins accumulated since the last exact count; bounds the estimate's drift.
39    joins: usize,
40    headers: Headers,
41    // Source heading prefix is held separately until a cross-section merge is actually made.
42    // This keeps the original source text of ordinary single-section chunks.
43    pub(crate) prefix: String,
44    prefix_start_byte: usize,
45    prefix_start_char: usize,
46}
47
48/// Incremental, block-aware chunker: feed it lines with [`SmartChunker::push_line`], then call
49/// [`SmartChunker::finish`]. It drives the Markdown [`BlockParser`], packs blocks into chunks
50/// and splits oversized blocks.
51///
52/// Used by the streaming file reader and by the whole-document path when
53/// `include_context = true`. With `include_context = false` the parser still recognizes
54/// fenced code and lists but does not track headings; neither the whole-document API nor
55/// `FileChunker` uses this chunker in that mode (they use flat windows, see [`ChunkConfig`]).
56pub struct SmartChunker {
57    cfg: ChunkConfig,
58    backend: Arc<Backend>,
59    pub(crate) parser: BlockParser,
60    pub(crate) pending: Option<Pending>,
61    peak_pending_bytes: usize,
62    ctx_cache: Option<(Headers, usize)>,
63    // The parser shares one Headers Arc across consecutive blocks in the same section.
64    // Cache its fitted form so long sections do not tokenize the same context repeatedly.
65    fit_cache: Option<(Headers, Headers)>,
66    scratch: Vec<Block>,
67    /// Exact token counts for short repeated blocks and separators. A bounded per-chunker
68    /// cache avoids re-tokenizing the same Markdown fragments without a process-global lock.
69    small_count_cache: RefCell<HashMap<String, usize>>,
70}
71
72impl SmartChunker {
73    pub fn new(cfg: ChunkConfig, backend: Arc<Backend>) -> Self {
74        // Heading tracking (and with it `Chunk::headers`) exists only in context mode.
75        let parse_headings = cfg.include_context;
76        SmartChunker {
77            cfg,
78            backend,
79            parser: BlockParser::with_headings(parse_headings),
80            pending: None,
81            peak_pending_bytes: 0,
82            ctx_cache: None,
83            fit_cache: None,
84            scratch: Vec::new(),
85            small_count_cache: RefCell::new(HashMap::with_capacity(64)),
86        }
87    }
88
89    pub(crate) fn peak_pending_bytes(&self) -> usize {
90        self.peak_pending_bytes
91    }
92
93    pub fn push_line(&mut self, line: &str, out: &mut Vec<Chunk>) -> Result<(), ChipError> {
94        let mut blocks = std::mem::take(&mut self.scratch);
95        self.parser.push_line(line, &mut blocks)?;
96        for b in blocks.drain(..) {
97            self.handle_block(b, out)?;
98        }
99        self.scratch = blocks;
100        Ok(())
101    }
102
103    pub fn finish(&mut self, out: &mut Vec<Chunk>) -> Result<(), ChipError> {
104        let mut blocks = std::mem::take(&mut self.scratch);
105        self.parser.finish(&mut blocks);
106        for b in blocks.drain(..) {
107            self.handle_block(b, out)?;
108        }
109        self.scratch = blocks;
110        self.flush_pending(out)?;
111        Ok(())
112    }
113
114    /// Earliest source position that a not-yet-emitted chunk may still reference.
115    /// Includes the pending cross-block merge, the parser's open block, and its
116    /// separator/heading gap. The gap must be included because a later merge can
117    /// pull those source characters back into a chunk.
118    pub(crate) fn earliest_future_start(&self) -> (usize, usize) {
119        let (mut byte, mut chr) = self.parser.earliest_future_start();
120        if let Some(pending) = &self.pending {
121            byte = byte.min(pending.start_byte).min(pending.prefix_start_byte);
122            chr = chr.min(pending.start_char).min(pending.prefix_start_char);
123        }
124        (byte, chr)
125    }
126
127    /// Count short structural fragments once per chunker. Cache hits are exact because the
128    /// key is the complete UTF-8 string, not a hash-only fingerprint. The cache is deliberately
129    /// bounded and excludes longer prose/candidate strings, where hashing and retention would
130    /// cost more than the occasional tokenizer call.
131    fn count_small_cached_at(&self, text: &str, site: CountSite) -> usize {
132        if text.len() > SMALL_COUNT_CACHE_MAX_TEXT_BYTES {
133            return self.backend.count_at(text, site);
134        }
135        if let Some(&tokens) = self.small_count_cache.borrow().get(text) {
136            return tokens;
137        }
138        let tokens = self.backend.count_at(text, site);
139        let mut cache = self.small_count_cache.borrow_mut();
140        if cache.len() >= SMALL_COUNT_CACHE_MAX_ENTRIES {
141            cache.clear();
142        }
143        cache.insert(text.to_owned(), tokens);
144        tokens
145    }
146
147    fn fit_headers(&mut self, headers: &Headers, max_context_tokens: usize) -> Headers {
148        if let Some((source, fitted)) = &self.fit_cache {
149            if Arc::ptr_eq(source, headers) {
150                return Arc::clone(fitted);
151            }
152        }
153        let fitted = fit_context_headers(headers, max_context_tokens, &self.backend);
154        self.fit_cache = Some((Arc::clone(headers), Arc::clone(&fitted)));
155        fitted
156    }
157
158    fn ctx_tokens(&mut self, headers: &Headers) -> usize {
159        if let Some((h, n)) = &self.ctx_cache {
160            if Arc::ptr_eq(h, headers) {
161                return *n;
162            }
163        }
164        let n = self
165            .backend
166            .count_at(&context_prefix(headers), CountSite::Context);
167        self.ctx_cache = Some((Arc::clone(headers), n));
168        n
169    }
170
171    /// Context-prefix tokens without touching the cache (usable while `pending` is borrowed).
172    fn ctx_tokens_ro(&self, headers: &Headers) -> usize {
173        if !self.cfg.include_context || headers.is_empty() {
174            return 0;
175        }
176        if let Some((h, n)) = &self.ctx_cache {
177            if Arc::ptr_eq(h, headers) {
178                return *n;
179            }
180        }
181        self.backend
182            .count_at(&context_prefix(headers), CountSite::Context)
183    }
184
185    fn budget_for(&mut self, headers: &Headers) -> usize {
186        let max = self.cfg.max_tokens;
187        if max == 0 {
188            return usize::MAX;
189        }
190        let ctx = if self.cfg.include_context && !headers.is_empty() {
191            self.ctx_tokens(headers)
192        } else {
193            0
194        };
195        max.saturating_sub(ctx).max(1)
196    }
197
198    /// Count exactly what downstream embedding code receives, including context.
199    fn count_delivered_at(&self, headers: &Headers, text: &str, site: CountSite) -> usize {
200        if self.cfg.include_context && !headers.is_empty() {
201            let mut full = context_prefix(headers);
202            full.push_str(text);
203            self.backend.count_at(&full, site)
204        } else {
205            self.backend.count_at(text, site)
206        }
207    }
208
209    /// Final safety gate. The fast splitter uses body-only estimates; this gate re-tokenizes
210    /// the actual delivered string and, if necessary, splits at UTF-8 character boundaries.
211    /// It never relies on the sum of independently-tokenized fragments (which is not additive
212    /// for BPE tokenizers).
213    pub(crate) fn finalize(&self, c: Chunk, out: &mut Vec<Chunk>) -> Result<(), ChipError> {
214        self.finalize_with_count(c, out, None)
215    }
216
217    /// `known_total` is supplied only when an upstream operation has already counted the
218    /// exact delivered string. This avoids repeating a tokenizer pass for intact blocks.
219    fn finalize_with_count(
220        &self,
221        mut c: Chunk,
222        out: &mut Vec<Chunk>,
223        known_total: Option<usize>,
224    ) -> Result<(), ChipError> {
225        let max = self.cfg.max_tokens;
226        if !self.cfg.strict || max == 0 {
227            // Chunks that carry headers only know their body count (or 0), so recount them
228            // to report the delivered (context + body) size. Header-less chunks keep the
229            // splitter's count, which is an estimate for chunks well below the limit;
230            // only strict mode guarantees an exact `token_count`.
231            if let Some(k) = known_total {
232                c.token_count = k;
233            } else if self.cfg.include_context && !c.headers.is_empty() {
234                c.token_count =
235                    self.count_delivered_at(&c.headers, &c.text, CountSite::FinalizeInput);
236            }
237            out.push(c);
238            return Ok(());
239        }
240
241        // `token_count` is part of the public result and is exact in strict mode. Reuse an
242        // upstream exact count when available; otherwise perform one authoritative count here.
243        // Do not substitute atom sums, which would make the reported token_count approximate.
244        // Count the actual delivered representation first. Most chunks fit with their
245        // context, so this ordering avoids a separate context+first-scalar tokenization pass.
246        // Only when the full contextualized chunk is over budget do we test whether context
247        // itself prevents even the first scalar from fitting and should be dropped.
248        // `known_total`, when present, is an exact count of the delivered string
249        // (context prefix + body), whether or not headers are attached.
250        let mut total = match known_total {
251            Some(k) => k,
252            None => self.count_delivered_at(&c.headers, &c.text, CountSite::FinalizeInput),
253        };
254        if total <= max {
255            c.token_count = total;
256            out.push(c);
257            return Ok(());
258        }
259        if !c.headers.is_empty() {
260            if let Some((_, first)) = c.text.grapheme_indices(true).next() {
261                let first_end = first.len();
262                if self.count_delivered_at(
263                    &c.headers,
264                    &c.text[..first_end],
265                    CountSite::FinalizeHeaderCheck,
266                ) > max
267                {
268                    c.headers = empty_headers();
269                    total = self.count_delivered_at(&c.headers, &c.text, CountSite::FinalizeRetry);
270                    if total <= max {
271                        c.token_count = total;
272                        out.push(c);
273                        return Ok(());
274                    }
275                }
276            }
277        }
278
279        let text = c.text.as_str();
280        let mut boundaries: Vec<usize> = text.grapheme_indices(true).map(|(i, _)| i).collect();
281        boundaries.push(text.len());
282        if boundaries.len() <= 1 {
283            return Ok(());
284        }
285        let mut bi = 0usize;
286        while bi + 1 < boundaries.len() {
287            // Find the longest suffix from this start whose *combined* representation fits.
288            let mut best: Option<(usize, usize)> = None;
289            // Scan the (already approximately-sized) candidate window. BPE token counts are
290            // not strictly monotonic as bytes are appended, so binary search is not sound.
291            for end_i in (bi + 1)..boundaries.len() {
292                let end = boundaries[end_i];
293                let (ts, te) = trim_bounds(text, boundaries[bi], end);
294                if ts >= te {
295                    best = Some((end_i, 0));
296                    continue;
297                }
298                let n =
299                    self.count_delivered_at(&c.headers, &text[ts..te], CountSite::FinalizeRetry);
300                if n <= max {
301                    best = Some((end_i, n));
302                }
303            }
304            let (mut end_i, mut n) = match best {
305                Some(v) if v.0 > bi => v,
306                _ => {
307                    // A complete Unicode grapheme can itself exceed an exceptionally small
308                    // token budget. There is no lossless non-empty chunk satisfying the invariant.
309                    // Return a typed error rather than panic or emit an oversized chunk.
310                    let one_end = boundaries[bi + 1];
311                    let (ts, te) = trim_bounds(text, boundaries[bi], one_end);
312                    if ts >= te {
313                        bi += 1;
314                        continue;
315                    }
316                    let one_n = self.count_delivered_at(
317                        &c.headers,
318                        &text[ts..te],
319                        CountSite::FinalizeRetry,
320                    );
321                    if one_n > max {
322                        return Err(ChipError::ChunkTooLarge {
323                            required_tokens: one_n,
324                            max_tokens: max,
325                            start_byte: c.start_byte + boundaries[bi],
326                        });
327                    }
328                    (bi + 1, one_n)
329                }
330            };
331
332            // Optional word snap, but only if the snapped candidate remains non-empty and fits.
333            if self.cfg.snap_words && end_i + 1 < boundaries.len() {
334                let end_byte = boundaries[end_i];
335                if let Some(rel) = text[boundaries[bi]..end_byte].rfind(char::is_whitespace) {
336                    let snapped = boundaries[bi] + rel;
337                    if snapped > boundaries[bi] {
338                        let (ts, te) = trim_bounds(text, boundaries[bi], snapped);
339                        if ts < te {
340                            let sn = self.count_delivered_at(
341                                &c.headers,
342                                &text[ts..te],
343                                CountSite::FinalizeSnap,
344                            );
345                            if sn > 0 && sn <= max {
346                                if let Ok(idx) = boundaries.binary_search(&snapped) {
347                                    end_i = idx;
348                                    n = sn;
349                                }
350                            }
351                        }
352                    }
353                }
354            }
355
356            let raw_s = boundaries[bi];
357            let raw_e = boundaries[end_i];
358            let (ts, te) = trim_bounds(text, raw_s, raw_e);
359            if ts < te {
360                let prefix_chars = char_len(&text[..ts]);
361                let body_chars = char_len(&text[ts..te]);
362                let start_byte = c.start_byte + ts;
363                let end_byte = c.start_byte + te;
364                let start_char = c.start_char + prefix_chars;
365                let end_char = start_char + body_chars;
366                let piece = Chunk {
367                    text: text[ts..te].to_string(),
368                    start_char,
369                    end_char,
370                    start_byte,
371                    end_byte,
372                    token_count: n,
373                    headers: Arc::clone(&c.headers),
374                };
375                // `n` was counted against this exact trimmed slice above; do not tokenize it again.
376                if n <= max {
377                    out.push(piece);
378                } else {
379                    return Err(ChipError::ChunkTooLarge {
380                        required_tokens: n,
381                        max_tokens: max,
382                        start_byte,
383                    });
384                }
385            }
386            bi = end_i.max(bi + 1);
387        }
388        Ok(())
389    }
390
391    fn flush_pending(&mut self, out: &mut Vec<Chunk>) -> Result<(), ChipError> {
392        if let Some(p) = self.pending.take() {
393            let end_char = p.start_char + char_len(&p.text);
394            let end_byte = p.start_byte + p.text.len();
395            let known_total = p.exact_total;
396            let c = Chunk {
397                text: p.text,
398                start_char: p.start_char,
399                end_char,
400                start_byte: p.start_byte,
401                end_byte,
402                token_count: p.exact_total.unwrap_or(p.tokens),
403                headers: p.headers,
404            };
405            self.finalize_with_count(c, out, known_total)?;
406        }
407        Ok(())
408    }
409
410    /// The parser closes a block at every blank line, so a multi-paragraph list item arrives as
411    /// several blocks ("4. next", then "   continuation paragraph\n5. last": the continuation
412    /// block may also carry the NEXT item, because only blank lines end a block). When the
413    /// pending chunk is full, flushing it would cut the item in half even though the item fits.
414    ///
415    /// If `b` starts with an indented continuation of the pending chunk's last top-level list
416    /// item and that whole item fits the budget, this flushes only the text BEFORE the item,
417    /// keeps the item pending, merges the continuation part of `b` into it and then handles the
418    /// rest of `b` normally. Returns `None` when `b` was fully handled, or gives `b` back
419    /// untouched when the rule does not apply (no list item, item too big, other section...).
420    fn keep_list_item_together(
421        &mut self,
422        b: Block,
423        out: &mut Vec<Chunk>,
424    ) -> Result<Option<Block>, ChipError> {
425        let max = self.cfg.max_tokens;
426        if max == 0 || b.is_code || !b.text.starts_with([' ', '\t']) {
427            return Ok(Some(b));
428        }
429        let Some(p) = self.pending.as_ref() else {
430            return Ok(Some(b));
431        };
432        if p.headers.as_slice() != b.headers.as_slice() {
433            return Ok(Some(b));
434        }
435        let items = crate::markdown::list_parser::parse_list_items(&p.text);
436        let Some(tail_start) = items
437            .iter()
438            .rev()
439            .find(|i| i.depth == 0)
440            .map(|i| i.start_byte)
441        else {
442            return Ok(Some(b));
443        };
444        let head_len = p.text[..tail_start].trim_end().len();
445        if head_len == 0 {
446            return Ok(Some(b)); // the pending chunk already starts with this item
447        }
448        let tail_len = p.text.len() - tail_start;
449        let mut cand = String::with_capacity(tail_len + b.sep_before.len() + b.text.len());
450        cand.push_str(&p.text[tail_start..]);
451        cand.push_str(&b.sep_before);
452        cand.push_str(&b.text);
453        let join_len = tail_len + b.sep_before.len();
454        // Where does the item end? It must reach into `b` (indented continuation lines).
455        let item_end = match crate::markdown::list_parser::parse_list_items(&cand).first() {
456            Some(f) if f.depth == 0 && f.start_byte == 0 && f.end_byte > join_len => {
457                f.end_byte.min(cand.len())
458            }
459            _ => return Ok(Some(b)),
460        };
461        let item_text = cand[..item_end].trim_end();
462        if item_text.len() <= join_len
463            || self.count_delivered_at(&p.headers, item_text, CountSite::ListItemCheck) > max
464        {
465            return Ok(Some(b));
466        }
467        // Part of `b` that belongs to the item (relative to b.text), and the rest.
468        let b1_len = item_text.len() - join_len;
469        let rest_start = b.text[b1_len..]
470            .find(|c: char| !c.is_whitespace())
471            .map(|i| b1_len + i);
472
473        // Flush everything before the item; the item stays pending.
474        let Some(p) = self.pending.take() else {
475            return Ok(Some(b));
476        };
477        let head_text = &p.text[..head_len];
478        let head_chunk = Chunk {
479            text: head_text.to_string(),
480            start_char: p.start_char,
481            end_char: p.start_char + char_len(head_text),
482            start_byte: p.start_byte,
483            end_byte: p.start_byte + head_len,
484            token_count: self
485                .backend
486                .count_at(head_text, CountSite::PendingListSplit),
487            headers: Arc::clone(&p.headers),
488        };
489        let tail_text = p.text[tail_start..].to_string();
490        let tail_tokens = self
491            .backend
492            .count_at(&tail_text, CountSite::PendingListSplit);
493        let tail_byte = p.start_byte + tail_start;
494        let tail_char = p.start_char + char_len(&p.text[..tail_start]);
495        self.pending = Some(Pending {
496            text: tail_text,
497            start_byte: tail_byte,
498            start_char: tail_char,
499            tokens: tail_tokens,
500            exact_total: if p.headers.is_empty() {
501                Some(tail_tokens)
502            } else {
503                None
504            },
505            joins: 0,
506            headers: p.headers,
507            prefix: String::new(),
508            prefix_start_byte: tail_byte,
509            prefix_start_char: tail_char,
510        });
511        self.finalize_with_count(head_chunk, out, None)?;
512
513        match rest_start {
514            None => self.handle_block(b, out)?,
515            Some(k) => {
516                let b2 = Block {
517                    text: b.text[k..].to_string(),
518                    start_byte: b.start_byte + k,
519                    start_char: b.start_char + char_len(&b.text[..k]),
520                    sep_before: b.text[b1_len..k].to_string(),
521                    headers: Arc::clone(&b.headers),
522                    is_code: false,
523                };
524                let b1 = Block {
525                    text: b.text[..b1_len].to_string(),
526                    ..b
527                };
528                self.handle_block(b1, out)?;
529                self.handle_block(b2, out)?;
530            }
531        }
532        Ok(None)
533    }
534
535    /// Token count of a whole block. For very large blocks a prefix is counted first, with
536    /// doubling sizes: as soon as a prefix alone exceeds `max_tokens` the block certainly
537    /// does not fit, and that (lower-bound) count is returned instead of tokenizing the whole
538    /// text. Callers only compare the result with a budget <= `max_tokens` or use it as an
539    /// estimate that is re-verified with an exact count, so a lower bound above the limit is
540    /// equivalent. Some tokenizers are superlinear on huge pre-tokens (whitespace floods).
541    fn count_block_text(&self, text: &str) -> usize {
542        let max = self.cfg.max_tokens;
543        if max == 0 || max == usize::MAX || text.len() <= BLOCK_PROBE_MIN_BYTES {
544            return self.count_small_cached_at(text, CountSite::BlockWhole);
545        }
546        // Probe only small prefixes: if the block does fit, the full count below is needed
547        // anyway and large probes would just add to it (superlinear tokenizers).
548        let mut size = max.saturating_mul(4).max(2048);
549        let probe_limit = size.max(8 * 1024);
550        while size <= probe_limit && size.saturating_mul(2) <= text.len() {
551            let mut end = size;
552            while !text.is_char_boundary(end) {
553                end -= 1;
554            }
555            let c = self.backend.count_at(&text[..end], CountSite::BlockPrefix);
556            if c > max {
557                return c;
558            }
559            size = size.saturating_mul(2);
560        }
561        self.count_small_cached_at(text, CountSite::BlockWhole)
562    }
563
564    pub fn handle_block(&mut self, mut b: Block, out: &mut Vec<Chunk>) -> Result<(), ChipError> {
565        if b.sep_before.len() > crate::markdown::MAX_PARSER_GAP_BYTES {
566            return Err(ChipError::Io(std::io::Error::new(
567                std::io::ErrorKind::InvalidData,
568                "block separator exceeds the parser byte limit",
569            )));
570        }
571        // Public callers can construct Blocks directly. Reject oversized values rather
572        // than split_off() a giant String and temporarily duplicate its allocation; the
573        // streaming parser already emits source-contiguous fragments within this bound.
574        if b.text.len() > crate::markdown::MAX_OPEN_BLOCK_BYTES {
575            return Err(ChipError::Io(std::io::Error::new(
576                std::io::ErrorKind::InvalidData,
577                format!(
578                    "block exceeds the {}-byte chunker input limit",
579                    crate::markdown::MAX_OPEN_BLOCK_BYTES
580                ),
581            )));
582        }
583
584        // Context is useful metadata, but a very long heading must not reduce the body
585        // allowance to one token. Reserve at most one quarter of the total budget for it.
586        // The deepest heading is retained preferentially by fit_context_headers().
587        if self.cfg.include_context && self.cfg.max_tokens > 0 {
588            // Small budgets still get a chance to carry a compact context label.
589            // Reserve at least five tokens where possible, but always leave body capacity.
590            let context_cap = (self.cfg.max_tokens / 4)
591                .max(5)
592                .min(self.cfg.max_tokens.saturating_sub(1));
593            b.headers = self.fit_headers(&b.headers, context_cap);
594        }
595
596        // Without merging, preserve the original block/header semantics.
597        if !self.cfg.merge_blocks {
598            self.flush_pending(out)?;
599            let budget = self.budget_for(&b.headers);
600            let b_tokens = self.count_block_text(&b.text);
601            if b_tokens > budget {
602                self.split_block(&b, budget, b_tokens, out)?;
603            } else {
604                let end_char = b.start_char + char_len(&b.text);
605                let end_byte = b.start_byte + b.text.len();
606                let known_total = if b.headers.is_empty() {
607                    Some(b_tokens)
608                } else {
609                    None
610                };
611                let c = Chunk {
612                    text: b.text,
613                    start_char: b.start_char,
614                    end_char,
615                    start_byte: b.start_byte,
616                    end_byte,
617                    token_count: b_tokens,
618                    headers: b.headers,
619                };
620                self.finalize_with_count(c, out, known_total)?;
621            }
622            return Ok(());
623        }
624
625        // Every block is tokenized exactly once; the count feeds both the merge estimate
626        // and, when the block starts a new pending chunk, that chunk's own count.
627        let b_tokens = self.count_block_text(&b.text);
628
629        // A section boundary need not force a chunk boundary. When two adjacent blocks have
630        // different heading paths, their longest common prefix is still truthful context for
631        // both. The heading line is carried in `sep_before`, so a merged body remains a
632        // contiguous slice of the original source and its offsets stay meaningful.
633        if let Some(p) = self.pending.as_ref() {
634            let section_changed = p.headers.as_slice() != b.headers.as_slice();
635            let common_len = if self.cfg.include_context {
636                p.headers
637                    .iter()
638                    .zip(b.headers.iter())
639                    .take_while(|(a, z)| a == z)
640                    .count()
641            } else {
642                0
643            };
644            let common: Headers = if common_len == p.headers.len() {
645                Arc::clone(&p.headers)
646            } else {
647                Arc::new(p.headers[..common_len].to_vec())
648            };
649            let carry_prefix = section_changed && !p.prefix.is_empty();
650            let prefix_len = if section_changed { p.prefix.len() } else { 0 };
651            let candidate_len = prefix_len
652                .saturating_add(p.text.len())
653                .saturating_add(b.sep_before.len())
654                .saturating_add(b.text.len());
655            let retained_prefix_len = if carry_prefix { 0 } else { p.prefix.len() };
656            let can_build_candidate = candidate_len <= MAX_PENDING_STATE_BYTES
657                && candidate_len.saturating_add(retained_prefix_len) <= MAX_PENDING_STATE_BYTES;
658            if !can_build_candidate {
659                record_event(CountSite::MergeCandidateTooLarge, candidate_len);
660            } else if carry_prefix {
661                // Counts all candidate materializations caused by a deferred heading prefix,
662                // whether the cheap token estimate succeeds or falls back to exact counting.
663                record_event(CountSite::MergePrefixCandidate, candidate_len);
664            }
665            let max = self.cfg.max_tokens;
666            let ctx_t = self.ctx_tokens_ro(&common);
667
668            // Do not allocate a concatenated candidate unless the complete pending
669            // state (including a deferred heading prefix) stays within its byte cap.
670            if can_build_candidate {
671              'merge: {
672                // Calculate the cheap estimate before allocating the candidate.
673                let mut fast_merge: Option<(usize, Option<usize>, usize)> = None;
674                // Retain the estimate before the +2 safety margin for diagnostics only
675                // (read only in `stats` builds).
676                #[cfg(feature = "stats")]
677                let mut rejected_base_estimate: Option<usize> = None;
678
679                if max > 0 {
680                    let sep_t = if b.sep_before.is_empty() {
681                        0
682                    } else {
683                        self.count_small_cached_at(&b.sep_before, CountSite::MergeSeparator)
684                    };
685
686                    let prefix_t = if carry_prefix {
687                        self.count_small_cached_at(&p.prefix, CountSite::MergePrefix)
688                    } else {
689                        0
690                    };
691
692                    let body_est = p.tokens + prefix_t + sep_t + b_tokens;
693                    // A separator that ends in a newline starts a fresh pre-token in the
694                    // BPE tokenizers, so the parts add up and the per-join slack is unnecessary.
695                    let join_cost = if b.sep_before.ends_with('\n') && self.backend.joins_are_additive() {
696                        0
697                    } else {
698                        1
699                    };
700                    let joins = p.joins + join_cost + usize::from(carry_prefix);
701
702                    if ctx_t + body_est + joins < max {
703                        fast_merge = Some((body_est, None, joins));
704                    } else {
705                        #[cfg(feature = "stats")]
706                        {
707                            rejected_base_estimate = Some(ctx_t + body_est + joins);
708                        }
709                        record_event(CountSite::MergeEstimateRejected, candidate_len);
710                        // Even if every join cost nothing and BPE saved up to two tokens per
711                        // join, the candidate cannot fit: reject without tokenizing it.
712                        if ctx_t + body_est > max + 2 * (joins + 1) {
713                            record_event(CountSite::MergeEarlyReject, candidate_len);
714                            break 'merge;
715                        }
716                    }
717                } else {
718                    // Unlimited-token mode skips the estimate but still needs exact counts
719                    // to maintain the pending token metadata.
720                    record_event(CountSite::MergeFastDisabled, candidate_len);
721                }
722
723                // Fast path: append directly to the existing pending String.
724                if let Some((tokens, exact_total, joins)) = fast_merge {
725                    if !carry_prefix {
726                        record_event(
727                            CountSite::MergeFastDirect,
728                            b.sep_before.len().saturating_add(b.text.len()),
729                        );
730                        if let Some(p) = self.pending.as_mut() {
731                            p.text
732                                .reserve(b.sep_before.len().saturating_add(b.text.len()));
733                            p.text.push_str(&b.sep_before);
734                            p.text.push_str(&b.text);
735                            p.tokens = tokens;
736                            p.exact_total = exact_total;
737                            p.joins = joins;
738                            p.headers = common;
739
740                            self.peak_pending_bytes = self
741                                .peak_pending_bytes
742                                .max(p.text.len().saturating_add(p.prefix.len()));
743                        }
744
745                        return Ok(());
746                    }
747
748                    // The estimate succeeded, but the deferred heading prefix must be
749                    // materialized into a candidate before the pending state can be updated.
750                    record_event(CountSite::MergeFastPrefix, candidate_len);
751                }
752
753                // Exact-count path: retain the original candidate construction.
754                let mut candidate = String::with_capacity(candidate_len);
755
756                if section_changed {
757                    candidate.push_str(&p.prefix);
758                }
759
760                candidate.push_str(&p.text);
761                candidate.push_str(&b.sep_before);
762                candidate.push_str(&b.text);
763
764                let mut merged = fast_merge;
765
766                if merged.is_none() {
767                    record_event(CountSite::MergeExactFallback, candidate_len);
768                    let candidate_tokens =
769                        self.count_delivered_at(&common, &candidate, CountSite::MergeCandidate);
770
771                    // Compare the pre-margin estimate with the exact delivered-token count.
772                    // These diagnostics run only in stats builds and do not affect decisions.
773                    #[cfg(feature = "stats")]
774                    if let Some(base_estimate) = rejected_base_estimate {
775                        let delta_site = if base_estimate < candidate_tokens {
776                            match candidate_tokens - base_estimate {
777                                1 => CountSite::MergeEstimateUnder1,
778                                _ => CountSite::MergeEstimateUnder2Plus,
779                            }
780                        } else {
781                            match base_estimate - candidate_tokens {
782                                0 => CountSite::MergeEstimateEqual,
783                                1 => CountSite::MergeEstimateOver1,
784                                2 => CountSite::MergeEstimateOver2,
785                                3 => CountSite::MergeEstimateOver3,
786                                _ => CountSite::MergeEstimateOver4Plus,
787                            }
788                        };
789                        record_event(delta_site, candidate_len);
790
791                        // Retrospective simulation: would +1 / +0 have passed the
792                        // estimate gate, and if so, would that have accepted an
793                        // actually-over-budget candidate?
794                        if base_estimate.saturating_add(1) <= max {
795                            record_event(CountSite::MergeMargin1WouldAccept, candidate_len);
796                            if candidate_tokens > max {
797                                record_event(CountSite::MergeMargin1Unsafe, candidate_len);
798                            }
799                        }
800                        if base_estimate <= max {
801                            record_event(CountSite::MergeMargin0WouldAccept, candidate_len);
802                            if candidate_tokens > max {
803                                record_event(CountSite::MergeMargin0Unsafe, candidate_len);
804                            }
805                        }
806                    }
807
808                    if max == 0 || candidate_tokens <= max {
809                        record_event(CountSite::MergeExactAccept, candidate_len);
810                        merged = Some((
811                            candidate_tokens.saturating_sub(ctx_t),
812                            Some(candidate_tokens),
813                            0,
814                        ));
815                    } else {
816                        record_event(CountSite::MergeExactReject, candidate_len);
817                    }
818                }
819
820                if let Some((tokens, exact_total, joins)) = merged {
821                    if let Some(p) = self.pending.as_mut() {
822                        if section_changed && !p.prefix.is_empty() {
823                            p.start_byte = p.prefix_start_byte;
824                            p.start_char = p.prefix_start_char;
825                            p.prefix.clear();
826                        }
827
828                        p.text = candidate;
829                        p.tokens = tokens;
830                        p.exact_total = exact_total;
831                        p.joins = joins;
832                        p.headers = common;
833
834                        self.peak_pending_bytes = self
835                            .peak_pending_bytes
836                            .max(p.text.len().saturating_add(p.prefix.len()));
837                    }
838
839                    return Ok(());
840                }
841              }
842            }
843        }
844
845        // Keep a multi-paragraph list item together: move its already-pending part into a
846        // fresh pending chunk and let this continuation block merge into it.
847        let b = match self.keep_list_item_together(b, out)? {
848            Some(b) => b,
849            None => return Ok(()),
850        };
851
852        // The previous pending chunk did not fit with this block (or no pending chunk exists).
853        self.flush_pending(out)?;
854        let budget = self.budget_for(&b.headers);
855        if b_tokens > budget {
856            self.split_block(&b, budget, b_tokens, out)?;
857            return Ok(());
858        }
859        let trimmed_prefix = b.sep_before.trim_start_matches(char::is_whitespace);
860        let has_heading_prefix = trimmed_prefix.starts_with('#');
861        let (prefix, prefix_start_byte, prefix_start_char) = if has_heading_prefix {
862            let leading_bytes = b.sep_before.len() - trimmed_prefix.len();
863            let leading_chars = char_len(&b.sep_before[..leading_bytes]);
864            (
865                trimmed_prefix.to_string(),
866                b.start_byte
867                    .saturating_sub(b.sep_before.len())
868                    .saturating_add(leading_bytes),
869                b.start_char
870                    .saturating_sub(char_len(&b.sep_before))
871                    .saturating_add(leading_chars),
872            )
873        } else {
874            (String::new(), b.start_byte, b.start_char)
875        };
876        self.pending = Some(Pending {
877            text: b.text,
878            start_byte: b.start_byte,
879            start_char: b.start_char,
880            tokens: b_tokens,
881            exact_total: if b.headers.is_empty() {
882                Some(b_tokens)
883            } else {
884                None
885            },
886            joins: 0,
887            headers: b.headers,
888            prefix,
889            prefix_start_byte,
890            prefix_start_char,
891        });
892        if let Some(pending) = &self.pending {
893            self.peak_pending_bytes = self
894                .peak_pending_bytes
895                .max(pending.text.len().saturating_add(pending.prefix.len()));
896        }
897        Ok(())
898    }
899
900    fn split_block(
901        &self,
902        b: &Block,
903        budget: usize,
904        b_tokens: usize,
905        out: &mut Vec<Chunk>,
906    ) -> Result<(), ChipError> {
907        // `count_block_text` returns an exact count only when it tokenized the whole block;
908        // above BLOCK_PROBE_MIN_BYTES it may return a prefix lower bound instead.
909        let known_total = (b.text.len() <= BLOCK_PROBE_MIN_BYTES).then_some(b_tokens);
910        let origin = Origin {
911            byte: b.start_byte,
912            chr: b.start_char,
913        };
914        let mut pieces = Vec::new();
915        split_by_tokens_with_lists_known(
916            &b.text,
917            origin,
918            budget,
919            self.cfg.overlap_tokens,
920            self.cfg.snap_words,
921            &self.backend,
922            &b.headers,
923            list_cuts(b),
924            known_total,
925            &mut pieces,
926        );
927        for piece in pieces {
928            let known_total = if self.cfg.snap_words && piece.headers.is_empty() {
929                // With snapping enabled, split_engine only emits chunks after an exact count
930                // against the delivered body slice. The strict gate can reuse that count.
931                Some(piece.token_count)
932            } else {
933                // Context changes the tokenization of the delivered string; verify it whole.
934                None
935            };
936            self.finalize_with_count(piece, out, known_total)?;
937        }
938        Ok(())
939    }
940}
941
942/// List-item start offsets inside a block, used to prefer item boundaries when an oversized
943/// block has to be split. Fenced code blocks yield none.
944fn list_cuts(b: &Block) -> ListCuts {
945    let mut cuts = ListCuts::default();
946    if b.is_code {
947        return cuts;
948    }
949    for item in crate::markdown::list_parser::parse_list_items(&b.text) {
950        if item.start_byte == 0 {
951            continue;
952        }
953        if item.depth == 0 {
954            cuts.top.push(item.start_byte);
955        } else {
956            cuts.nested.push(item.start_byte);
957        }
958    }
959    cuts
960}
961
962// ============================================================================
963// Intra-document parallelism
964// ============================================================================
965//
966// The chunker is a deterministic left-to-right fold over the parser's blocks, and the ONLY
967// piece of state that influences its output is `SmartChunker::pending` (the other fields are
968// memoization caches keyed by header identity, or statistics). That makes the following
969// scheme exact rather than approximate:
970//
971//   1. Parse the whole (normalized) document into blocks. The parser never depends on the
972//      chunker, so this yields exactly the blocks the interleaved sequential loop would see.
973//   2. Cut the block list into contiguous segments and run each one on its own thread,
974//      *speculatively* starting from an empty `pending`. Segment 0 really does start from an
975//      empty state, so its result is final.
976//   3. Stitch sequentially. For segment k the true entry state is known (the end state of
977//      segment k-1). Re-run the first few blocks of segment k from that true state, and after
978//      every block compare the true `pending` with the speculative run's snapshot after the
979//      same block. Both runs are deterministic functions of (state, remaining blocks), so
980//      once the states are *equal* the rest of the speculative output IS the true output and
981//      is spliced in. Greedy packing is self-synchronizing in practice, so this happens after
982//      a handful of blocks; if it does not (or snapshots run out) the true run simply
983//      continues through the whole segment. The result is therefore always identical to the
984//      sequential result; only the amount of parallel speed-up depends on resynchronization.
985//
986// Errors follow the same rule: the first error in document order wins, a speculative error is
987// only trusted after a successful resync, and a parser error is reported only if no chunking
988// error occurs in the blocks that precede it (exactly the sequential interleaving).
989pub(crate) mod parallel {
990    use std::sync::Arc;
991
992    use rayon::prelude::*;
993
994    use super::{Pending, SmartChunker};
995    use crate::{
996        backend::Backend,
997        block::Block,
998        chunk_types::{Chunk, ChunkConfig},
999        markdown::BlockParser,
1000        ChipError,
1001    };
1002
1003    /// Normalized documents smaller than this always take the sequential path.
1004    pub(crate) const DEFAULT_MIN_BYTES: usize = 2 * 1024 * 1024;
1005    /// Inspect only a bounded prefix before materializing the full block vector. Dense tiny
1006    /// paragraphs are better handled by the streaming fold, which does not retain every Block
1007    /// allocation at once.
1008    const DENSE_PREFLIGHT_SAMPLE_BYTES: usize = 64 * 1024;
1009    const DENSE_PREFLIGHT_MIN_BLANK_LINES: usize = 128;
1010    const DENSE_PREFLIGHT_MAX_AVG_BYTES_PER_PARAGRAPH: usize = 32;
1011    /// Smallest segment worth a task of its own.
1012    pub(crate) const DEFAULT_MIN_SEGMENT_BYTES: usize = 256 * 1024;
1013    /// Tiny-block documents do not amortize speculative segment runs and stitching.
1014    /// Require at least this many source bytes per parsed block before using the
1015    /// context-aware parallel fold. This is independent of language and block kind.
1016    const MIN_AVG_BLOCK_BYTES_FOR_PARALLEL: usize = 32;
1017    /// Fewer pieces than this are not worth fanning out in the no-context path.
1018    const MIN_PIECES_FOR_PARALLEL_FINALIZE: usize = 64;
1019    /// Resync bookkeeping limits per speculative segment (memory bound).
1020    const MAX_SNAPSHOTS_PER_SEGMENT: usize = 1024;
1021    const MAX_SNAPSHOT_BYTES_PER_SEGMENT: usize = 2 * 1024 * 1024;
1022
1023    #[derive(Clone, Copy, Debug)]
1024    pub(crate) struct ParallelOpts {
1025        /// Use the parallel path only for normalized documents of at least this many bytes.
1026        pub(crate) min_bytes: usize,
1027        /// Lower bound for the bytes handled by one segment.
1028        pub(crate) min_segment_bytes: usize,
1029        /// 0 = automatic (2 x rayon threads, and never parallel on a single thread);
1030        /// otherwise exactly this many segments at most, regardless of the thread count.
1031        pub(crate) max_segments: usize,
1032    }
1033
1034    impl Default for ParallelOpts {
1035        fn default() -> Self {
1036            ParallelOpts {
1037                min_bytes: DEFAULT_MIN_BYTES,
1038                min_segment_bytes: DEFAULT_MIN_SEGMENT_BYTES,
1039                max_segments: 0,
1040            }
1041        }
1042    }
1043
1044    impl ParallelOpts {
1045        /// Never take the parallel path (reference behaviour for tests).
1046        #[cfg(test)]
1047        pub(crate) fn never() -> Self {
1048            ParallelOpts {
1049                min_bytes: usize::MAX,
1050                min_segment_bytes: DEFAULT_MIN_SEGMENT_BYTES,
1051                max_segments: 0,
1052            }
1053        }
1054
1055        /// Force the parallel path with up to `segments` segments (tests).
1056        #[cfg(test)]
1057        pub(crate) fn forced(segments: usize) -> Self {
1058            ParallelOpts {
1059                min_bytes: 0,
1060                min_segment_bytes: 1,
1061                max_segments: segments,
1062            }
1063        }
1064    }
1065
1066    #[derive(Clone, Copy, Debug, Default)]
1067    #[allow(dead_code)]
1068    pub(crate) struct ParallelStats {
1069        pub(crate) segments: usize,
1070        /// Seams where the true state re-synchronized with the speculative run.
1071        pub(crate) resynced: usize,
1072        /// Blocks that had to be processed a second time by the sequential stitch.
1073        pub(crate) restitched_blocks: usize,
1074    }
1075
1076    /// Cheap, allocation-free admission check for documents dominated by very short
1077    /// paragraphs. It intentionally samples only the prefix: this is a scheduling heuristic,
1078    /// not a parser, and a false positive only selects the exact sequential implementation.
1079    pub(crate) fn has_dense_tiny_paragraph_prefix(normalized: &str) -> bool {
1080        let mut sample_end = normalized.len().min(DENSE_PREFLIGHT_SAMPLE_BYTES);
1081        while !normalized.is_char_boundary(sample_end) {
1082            sample_end -= 1;
1083        }
1084        let sample = &normalized[..sample_end];
1085        if sample.is_empty() {
1086            return false;
1087        }
1088
1089        let blank_lines = sample
1090            .split_inclusive('\n')
1091            .filter(|line| {
1092                let line = line.strip_suffix('\n').unwrap_or(line);
1093                let line = line.strip_suffix('\r').unwrap_or(line);
1094                line.trim().is_empty()
1095            })
1096            .count();
1097
1098        blank_lines >= DENSE_PREFLIGHT_MIN_BLANK_LINES
1099            && sample.len() / blank_lines.max(1) < DENSE_PREFLIGHT_MAX_AVG_BYTES_PER_PARAGRAPH
1100    }
1101
1102    /// Number of segments to use for the block-fold path, or `None` for "stay sequential".
1103    pub(crate) fn plan(normalized_len: usize, opts: &ParallelOpts) -> Option<usize> {
1104        if normalized_len < opts.min_bytes {
1105            return None;
1106        }
1107        let cap = if opts.max_segments > 0 {
1108            opts.max_segments
1109        } else {
1110            let threads = rayon::current_num_threads();
1111            if threads < 2 {
1112                return None;
1113            }
1114            threads.saturating_mul(2)
1115        };
1116        let by_size = normalized_len / opts.min_segment_bytes.max(1);
1117        let n = cap.min(by_size);
1118        if n < 2 {
1119            None
1120        } else {
1121            Some(n)
1122        }
1123    }
1124
1125    /// Whether the no-context path should finalize its pieces in parallel.
1126    pub(crate) fn plan_finalize(normalized_len: usize, pieces: usize, opts: &ParallelOpts) -> bool {
1127        if normalized_len < opts.min_bytes {
1128            return false;
1129        }
1130        if opts.max_segments > 0 {
1131            return pieces >= 2;
1132        }
1133        rayon::current_num_threads() >= 2 && pieces >= MIN_PIECES_FOR_PARALLEL_FINALIZE
1134    }
1135
1136    /// Complete field-by-field comparison of two chunker states. Destructuring without `..`
1137    /// makes adding a field to `Pending` a compile error here, so the comparison cannot
1138    /// silently become incomplete. Headers are compared by value (identity only matters to
1139    /// the memoization caches).
1140    fn same_state(a: &Option<Pending>, b: &Option<Pending>) -> bool {
1141        match (a, b) {
1142            (None, None) => true,
1143            (Some(x), Some(y)) => {
1144                let Pending {
1145                    text: x_text,
1146                    start_byte: x_start_byte,
1147                    start_char: x_start_char,
1148                    tokens: x_tokens,
1149                    exact_total: x_exact_total,
1150                    joins: x_joins,
1151                    headers: x_headers,
1152                    prefix: x_prefix,
1153                    prefix_start_byte: x_prefix_start_byte,
1154                    prefix_start_char: x_prefix_start_char,
1155                } = x;
1156                let Pending {
1157                    text: y_text,
1158                    start_byte: y_start_byte,
1159                    start_char: y_start_char,
1160                    tokens: y_tokens,
1161                    exact_total: y_exact_total,
1162                    joins: y_joins,
1163                    headers: y_headers,
1164                    prefix: y_prefix,
1165                    prefix_start_byte: y_prefix_start_byte,
1166                    prefix_start_char: y_prefix_start_char,
1167                } = y;
1168                x_start_byte == y_start_byte
1169                    && x_start_char == y_start_char
1170                    && x_tokens == y_tokens
1171                    && x_exact_total == y_exact_total
1172                    && x_joins == y_joins
1173                    && x_prefix_start_byte == y_prefix_start_byte
1174                    && x_prefix_start_char == y_prefix_start_char
1175                    && x_headers.as_slice() == y_headers.as_slice()
1176                    && x_text == y_text
1177                    && x_prefix == y_prefix
1178            }
1179            _ => false,
1180        }
1181    }
1182
1183    fn state_bytes(p: &Option<Pending>) -> usize {
1184        match p {
1185            Some(p) => p.text.len() + p.prefix.len() + 64,
1186            None => 64,
1187        }
1188    }
1189
1190    /// Result of running one segment from an empty state.
1191    struct SegRun {
1192        /// Chunks emitted while handling the segment's blocks (the end state is NOT flushed).
1193        chunks: Vec<Chunk>,
1194        /// `snaps[i]` = (chunks emitted so far, pending state) right after block `i`.
1195        /// Only a prefix of the segment is recorded (see the MAX_* limits).
1196        snaps: Vec<(usize, Option<Pending>)>,
1197        /// State after the last block; meaningful only when `err` is `None`.
1198        end_state: Option<Pending>,
1199        /// Error raised by the block with index `snaps.len() <= e`, if any.
1200        err: Option<ChipError>,
1201    }
1202
1203    fn run_segment(
1204        blocks: &[Block],
1205        cfg: &ChunkConfig,
1206        backend: &Arc<Backend>,
1207        record_snapshots: bool,
1208    ) -> SegRun {
1209        let mut ch = SmartChunker::new(cfg.clone(), Arc::clone(backend));
1210        let mut chunks: Vec<Chunk> = Vec::new();
1211        let mut snaps: Vec<(usize, Option<Pending>)> = Vec::new();
1212        let mut snap_bytes = 0usize;
1213        let mut recording = record_snapshots;
1214        for b in blocks {
1215            if let Err(e) = ch.handle_block(b.clone(), &mut chunks) {
1216                return SegRun {
1217                    chunks,
1218                    snaps,
1219                    end_state: None,
1220                    err: Some(e),
1221                };
1222            }
1223            if recording {
1224                let sz = state_bytes(&ch.pending);
1225                if snaps.len() >= MAX_SNAPSHOTS_PER_SEGMENT
1226                    || snap_bytes.saturating_add(sz) > MAX_SNAPSHOT_BYTES_PER_SEGMENT
1227                {
1228                    recording = false;
1229                } else {
1230                    snap_bytes += sz;
1231                    snaps.push((chunks.len(), ch.pending.clone()));
1232                }
1233            }
1234        }
1235        SegRun {
1236            chunks,
1237            snaps,
1238            end_state: ch.pending.take(),
1239            err: None,
1240        }
1241    }
1242
1243    /// Split blocks into at most `nseg` contiguous, roughly byte-balanced segments.
1244    fn split_segments(blocks: Vec<Block>, nseg: usize) -> Vec<Vec<Block>> {
1245        let total: usize = blocks
1246            .iter()
1247            .map(|b| b.text.len() + b.sep_before.len())
1248            .sum();
1249        let target = (total / nseg.max(1)).max(1);
1250        let mut segs: Vec<Vec<Block>> = Vec::with_capacity(nseg);
1251        let mut cur: Vec<Block> = Vec::new();
1252        let mut acc = 0usize;
1253        for b in blocks {
1254            acc += b.text.len() + b.sep_before.len();
1255            cur.push(b);
1256            if acc >= target && segs.len() + 1 < nseg {
1257                segs.push(std::mem::take(&mut cur));
1258                acc = 0;
1259            }
1260        }
1261        if !cur.is_empty() {
1262            segs.push(cur);
1263        }
1264        segs
1265    }
1266
1267    /// Parallel equivalent of the `include_context` branch of the sequential driver
1268    /// (`push_line` for every line, then `finish`). `normalized` must be non-empty.
1269    pub(crate) fn chunk_context_parallel(
1270        normalized: &str,
1271        cfg: &ChunkConfig,
1272        backend: &Arc<Backend>,
1273        nseg: usize,
1274    ) -> Result<(Vec<Chunk>, ParallelStats), ChipError> {
1275        // Check density before collecting Blocks: for hundreds of thousands of tiny
1276        // paragraphs, parsing the whole document into a Vec<Block> would itself dominate the
1277        // runtime even though the later fold falls back to sequential processing. Such inputs
1278        // take the ordinary streaming path, which retains only the current parser/chunker
1279        // state.
1280        if has_dense_tiny_paragraph_prefix(normalized) {
1281            let mut ch = SmartChunker::new(cfg.clone(), Arc::clone(backend));
1282            let mut out: Vec<Chunk> = Vec::new();
1283            for line in normalized.split_inclusive('\n') {
1284                ch.push_line(line, &mut out)?;
1285            }
1286            ch.finish(&mut out)?;
1287            return Ok((
1288                out,
1289                ParallelStats {
1290                    segments: 1,
1291                    ..ParallelStats::default()
1292                },
1293            ));
1294        }
1295
1296        // ---- 1. parse (sequential, mirrors SmartChunker::push_line / finish) ----------------
1297        let mut parser = BlockParser::with_headings(cfg.include_context);
1298        let mut blocks: Vec<Block> = Vec::new();
1299        let mut parse_err: Option<ChipError> = None;
1300        for line in normalized.split_inclusive('\n') {
1301            let mark = blocks.len();
1302            if let Err(e) = parser.push_line(line, &mut blocks) {
1303                // The sequential driver drops blocks produced by the failing call unhandled.
1304                blocks.truncate(mark);
1305                parse_err = Some(e);
1306                break;
1307            }
1308        }
1309        if parse_err.is_none() {
1310            parser.finish(&mut blocks);
1311        }
1312
1313        // ---- 2. admission check and speculative parallel runs -------------------------------
1314        // The block-fold strategy speculatively processes each segment and may need to
1315        // reprocess its prefix while stitching. On documents made of hundreds of thousands
1316        // of tiny paragraphs, that overhead can dominate the useful work and make scaling
1317        // superlinear. Keep those dense-block inputs on the ordinary sequential fold.
1318        //
1319        // Measure source bytes represented by parsed blocks (body + preceding separator),
1320        // rather than language-specific text features. The threshold is deliberately a
1321        // coarse admission heuristic only; it never changes parsing or chunk boundaries.
1322        let represented_bytes = blocks.iter().fold(0usize, |sum, block| {
1323            sum.saturating_add(block.text.len())
1324                .saturating_add(block.sep_before.len())
1325        });
1326        let min_parallel_bytes = blocks
1327            .len()
1328            .saturating_mul(MIN_AVG_BLOCK_BYTES_FOR_PARALLEL);
1329        if !blocks.is_empty() && represented_bytes < min_parallel_bytes {
1330            let mut ch = SmartChunker::new(cfg.clone(), Arc::clone(backend));
1331            let mut out: Vec<Chunk> = Vec::new();
1332            for block in blocks {
1333                ch.handle_block(block, &mut out)?;
1334            }
1335            // Match the streaming sequential driver's error order: process every block
1336            // emitted before the parser error, but do not flush pending state afterwards.
1337            if let Some(e) = parse_err {
1338                return Err(e);
1339            }
1340            ch.flush_pending(&mut out)?;
1341            return Ok((
1342                out,
1343                ParallelStats {
1344                    segments: 1,
1345                    ..ParallelStats::default()
1346                },
1347            ));
1348        }
1349
1350        let segs = split_segments(blocks, nseg);
1351        let runs: Vec<SegRun> = segs
1352            .par_iter()
1353            .enumerate()
1354            .map(|(i, s)| run_segment(s, cfg, backend, i > 0))
1355            .collect();
1356
1357        // ---- 3. sequential stitch ------------------------------------------------------------
1358        let mut stats = ParallelStats {
1359            segments: segs.len(),
1360            ..ParallelStats::default()
1361        };
1362        let mut out: Vec<Chunk> = Vec::new();
1363        let mut state: Option<Pending> = None;
1364
1365        for (k, mut run) in runs.into_iter().enumerate() {
1366            if k == 0 {
1367                // Segment 0 starts from the true initial state: its result is final.
1368                if let Some(e) = run.err {
1369                    return Err(e);
1370                }
1371                out = std::mem::take(&mut run.chunks);
1372                state = run.end_state.take();
1373                continue;
1374            }
1375
1376            let seg_blocks = &segs[k];
1377            let mut ch = SmartChunker::new(cfg.clone(), Arc::clone(backend));
1378            ch.pending = state.take();
1379            let mut true_out: Vec<Chunk> = Vec::new();
1380            let mut consumed = 0usize;
1381            let mut resume_at: Option<usize> = None;
1382            loop {
1383                // Is the true state after `consumed` blocks equal to the speculative state
1384                // after the same number of blocks?
1385                let spec_chunks: Option<usize> = if consumed == 0 {
1386                    if ch.pending.is_none() {
1387                        Some(0)
1388                    } else {
1389                        None
1390                    }
1391                } else {
1392                    match run.snaps.get(consumed - 1) {
1393                        Some((cnt, st)) if same_state(&ch.pending, st) => Some(*cnt),
1394                        _ => None,
1395                    }
1396                };
1397                if spec_chunks.is_some() {
1398                    resume_at = spec_chunks;
1399                    break;
1400                }
1401                if consumed == seg_blocks.len() {
1402                    break;
1403                }
1404                // Not synchronized yet: process the next block from the true state.
1405                ch.handle_block(seg_blocks[consumed].clone(), &mut true_out)?;
1406                consumed += 1;
1407            }
1408            stats.restitched_blocks += consumed;
1409            out.append(&mut true_out);
1410            match resume_at {
1411                Some(cnt) => {
1412                    stats.resynced += 1;
1413                    // From here on the true run is identical to the speculative run, including
1414                    // any error it hit (that block index is >= `consumed`).
1415                    if let Some(e) = run.err.take() {
1416                        return Err(e);
1417                    }
1418                    out.extend(run.chunks.drain(cnt..));
1419                    state = run.end_state.take();
1420                }
1421                None => {
1422                    // The true run covered the whole segment on its own.
1423                    state = ch.pending.take();
1424                }
1425            }
1426        }
1427
1428        // ---- 4. tail --------------------------------------------------------------------------
1429        if let Some(e) = parse_err {
1430            // Sequential semantics: `finish()` (and its final flush) is never reached.
1431            return Err(e);
1432        }
1433        let mut ch = SmartChunker::new(cfg.clone(), Arc::clone(backend));
1434        ch.pending = state;
1435        ch.flush_pending(&mut out)?;
1436        Ok((out, stats))
1437    }
1438
1439    /// Order-preserving parallel version of `for piece in pieces { gate.finalize(piece, out)? }`.
1440    /// `finalize` is a pure function of (piece, config, backend), so the pieces are independent.
1441    /// The FIRST error in piece order is returned, exactly like the sequential loop (rayon's own
1442    /// `collect::<Result<_, _>>()` would pick an arbitrary error).
1443    pub(crate) fn finalize_pieces(
1444        pieces: Vec<Chunk>,
1445        cfg: &ChunkConfig,
1446        backend: &Arc<Backend>,
1447        out: &mut Vec<Chunk>,
1448    ) -> Result<(), ChipError> {
1449        let results: Vec<Result<Vec<Chunk>, ChipError>> = pieces
1450            .into_par_iter()
1451            .with_min_len(8)
1452            .map_init(
1453                || SmartChunker::new(cfg.clone(), Arc::clone(backend)),
1454                |gate, piece| {
1455                    let mut v: Vec<Chunk> = Vec::with_capacity(1);
1456                    gate.finalize(piece, &mut v).map(|()| v)
1457                },
1458            )
1459            .collect();
1460        for r in results {
1461            out.extend(r?);
1462        }
1463        Ok(())
1464    }
1465}
1466
1467// Whole-document orchestration shares the chunker lifecycle and finalization rules.
1468
1469mod whole_document {
1470    use std::sync::Arc;
1471
1472    use super::parallel::{self, ParallelOpts};
1473    use super::SmartChunker;
1474    use crate::{
1475        backend::Backend,
1476        chunk_types::{Chunk, ChunkConfig},
1477        normalization::{NormBase, NormMap, OrigSpan},
1478        split_engine::{empty_headers, split_by_tokens, Origin},
1479        ChipError,
1480    };
1481
1482    /// Chunk text while retaining a mapping from normalized offsets back to the original input.
1483    /// Very large documents are processed on several threads; the result is identical to the
1484    /// sequential one (see the `parallel` module for the argument).
1485    pub(crate) fn smart_chunk_mapped_profile(
1486        text: &str,
1487        cfg: &ChunkConfig,
1488        backend: &Arc<Backend>,
1489    ) -> Result<(Vec<Chunk>, Vec<OrigSpan>, usize), ChipError> {
1490        smart_chunk_mapped_profile_with(text, cfg, backend, &ParallelOpts::default())
1491    }
1492
1493    pub(crate) fn smart_chunk_mapped_profile_with(
1494        text: &str,
1495        cfg: &ChunkConfig,
1496        backend: &Arc<Backend>,
1497        opts: &ParallelOpts,
1498    ) -> Result<(Vec<Chunk>, Vec<OrigSpan>, usize), ChipError> {
1499        let mut map = NormMap::default();
1500        let normalized = cfg
1501            .normalization
1502            .apply_mapped(text, NormBase::default(), &mut map);
1503        let mut out = Vec::new();
1504        if normalized.is_empty() {
1505            return Ok((out, Vec::new(), map.segs.len()));
1506        }
1507
1508        // Two different algorithms, selected by `include_context` (documented on ChunkConfig):
1509        //  * context mode: Markdown block parser + block packing (parallel for large inputs);
1510        //  * flat mode: plain token windows over the whole normalized text, no Markdown parsing.
1511        if cfg.include_context {
1512            if let Some(nseg) = parallel::plan(normalized.len(), opts) {
1513                out = parallel::chunk_context_parallel(&normalized, cfg, backend, nseg)?.0;
1514            } else {
1515                let mut chunker = SmartChunker::new(cfg.clone(), Arc::clone(backend));
1516                for line in normalized.split_inclusive('\n') {
1517                    chunker.push_line(line, &mut out)?;
1518                }
1519                chunker.finish(&mut out)?;
1520            }
1521        } else {
1522            // Flat mode: the Markdown structure is deliberately ignored here, so fences, lists
1523            // and tables may be cut and no headers are attached (`empty_headers()` below).
1524            let mut pieces = Vec::new();
1525            split_by_tokens(
1526                &normalized,
1527                Origin::default(),
1528                cfg.max_tokens,
1529                cfg.overlap_tokens,
1530                cfg.snap_words,
1531                backend,
1532                &empty_headers(),
1533                &mut pieces,
1534            );
1535            if parallel::plan_finalize(normalized.len(), pieces.len(), opts) {
1536                parallel::finalize_pieces(pieces, cfg, backend, &mut out)?;
1537            } else {
1538                let gate = SmartChunker::new(cfg.clone(), Arc::clone(backend));
1539                for piece in pieces {
1540                    gate.finalize(piece, &mut out)?;
1541                }
1542            }
1543        }
1544        let spans = out.iter().map(|c| map.span(c)).collect();
1545        Ok((out, spans, map.segs.len()))
1546    }
1547
1548    /// Chunk `text` and also return, for every chunk, its span in the *original* text
1549    /// (before normalization). See [`ChunkConfig`] for the two chunking modes and the budget
1550    /// guarantee. Errors are returned, never swallowed.
1551    pub fn smart_chunk_mapped(
1552        text: &str,
1553        cfg: &ChunkConfig,
1554        backend: &Arc<Backend>,
1555    ) -> Result<(Vec<Chunk>, Vec<OrigSpan>), ChipError> {
1556        let (chunks, spans, _) = smart_chunk_mapped_profile(text, cfg, backend)?;
1557        Ok((chunks, spans))
1558    }
1559
1560    /// Chunk `text`; offsets in the result refer to the normalized text. See
1561    /// [`smart_chunk_mapped`] for original-text spans and [`ChunkConfig`] for semantics.
1562    pub fn smart_chunk(
1563        text: &str,
1564        cfg: &ChunkConfig,
1565        backend: &Arc<Backend>,
1566    ) -> Result<Vec<Chunk>, ChipError> {
1567        Ok(smart_chunk_mapped(text, cfg, backend)?.0)
1568    }
1569}
1570
1571pub(crate) use whole_document::smart_chunk_mapped_profile;
1572#[cfg(test)]
1573pub(crate) use whole_document::smart_chunk_mapped_profile_with;
1574pub use whole_document::{smart_chunk, smart_chunk_mapped};