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
17const MAX_PENDING_STATE_BYTES: usize = 2 * 1024 * 1024;
19const 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#[derive(Clone)]
30pub(crate) struct Pending {
31 pub(crate) text: String,
32 start_byte: usize,
33 start_char: usize,
34 tokens: usize,
36 exact_total: Option<usize>,
38 joins: usize,
40 headers: Headers,
41 pub(crate) prefix: String,
44 prefix_start_byte: usize,
45 prefix_start_char: usize,
46}
47
48pub 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 fit_cache: Option<(Headers, Headers)>,
66 scratch: Vec<Block>,
67 small_count_cache: RefCell<HashMap<String, usize>>,
70}
71
72impl SmartChunker {
73 pub fn new(cfg: ChunkConfig, backend: Arc<Backend>) -> Self {
74 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 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 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 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 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 pub(crate) fn finalize(&self, c: Chunk, out: &mut Vec<Chunk>) -> Result<(), ChipError> {
214 self.finalize_with_count(c, out, None)
215 }
216
217 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 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 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 let mut best: Option<(usize, usize)> = None;
289 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 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 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 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 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)); }
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 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 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 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 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 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 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 if self.cfg.include_context && self.cfg.max_tokens > 0 {
588 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 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 let b_tokens = self.count_block_text(&b.text);
628
629 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 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 if can_build_candidate {
671 'merge: {
672 let mut fast_merge: Option<(usize, Option<usize>, usize)> = None;
674 #[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 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 if ctx_t + body_est > max + 2 * (joins + 1) {
713 record_event(CountSite::MergeEarlyReject, candidate_len);
714 break 'merge;
715 }
716 }
717 } else {
718 record_event(CountSite::MergeFastDisabled, candidate_len);
721 }
722
723 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 record_event(CountSite::MergeFastPrefix, candidate_len);
751 }
752
753 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 #[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 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 let b = match self.keep_list_item_together(b, out)? {
848 Some(b) => b,
849 None => return Ok(()),
850 };
851
852 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 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 Some(piece.token_count)
932 } else {
933 None
935 };
936 self.finalize_with_count(piece, out, known_total)?;
937 }
938 Ok(())
939 }
940}
941
942fn 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
962pub(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 pub(crate) const DEFAULT_MIN_BYTES: usize = 2 * 1024 * 1024;
1005 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 pub(crate) const DEFAULT_MIN_SEGMENT_BYTES: usize = 256 * 1024;
1013 const MIN_AVG_BLOCK_BYTES_FOR_PARALLEL: usize = 32;
1017 const MIN_PIECES_FOR_PARALLEL_FINALIZE: usize = 64;
1019 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 pub(crate) min_bytes: usize,
1027 pub(crate) min_segment_bytes: usize,
1029 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 #[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 #[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 pub(crate) resynced: usize,
1072 pub(crate) restitched_blocks: usize,
1074 }
1075
1076 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 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 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 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 struct SegRun {
1192 chunks: Vec<Chunk>,
1194 snaps: Vec<(usize, Option<Pending>)>,
1197 end_state: Option<Pending>,
1199 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 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 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 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 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 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 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 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 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 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 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 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 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 state = ch.pending.take();
1424 }
1425 }
1426 }
1427
1428 if let Some(e) = parse_err {
1430 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 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
1467mod 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 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 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 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 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 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};