Skip to main content

docling_core/
chunker.rs

1//! Document chunking for RAG pipelines — the Rust port of docling-core's
2//! `docling_core.transforms.chunker`.
3//!
4//! Two chunkers, matching docling's semantics output-for-output:
5//!
6//! * [`HierarchicalChunker`] walks the document tree and yields one chunk per
7//!   top-level item (paragraph, whole list, table, picture caption, …), each
8//!   carrying the heading path it sits under. Tables are serialized in
9//!   docling's *triplet* form (`row, column = value`), pictures contribute
10//!   their captions.
11//! * [`HybridChunker`] refines the hierarchical chunks with a tokenizer:
12//!   oversized chunks are split (at item boundaries first, then within the
13//!   text by docling's `semchunk` algorithm), and undersized neighbours that
14//!   share the same headings are merged back together.
15//!
16//! [`contextualize`] renders a chunk to the string an embedding model should
17//! see: the heading path plus the chunk text.
18//!
19//! Anything tokenizer-related is abstracted behind [`ChunkTokenizer`]; a
20//! HuggingFace `tokenizers` implementation ships behind the `chunking` cargo
21//! feature as [`HuggingFaceTokenizer`].
22
23use std::collections::{BTreeMap, VecDeque};
24
25use crate::document::{DoclingDocument, Node, Table};
26
27/// What kind of document item a [`ChunkItem`] points at — only what the
28/// hybrid splitting logic needs to know.
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub enum ChunkItemKind {
31    /// A text-ish item (paragraph, list item, code, formula, caption, …).
32    Text,
33    /// A table item (single-item oversized chunks re-split per line, repeating
34    /// docling's header handling).
35    Table,
36    /// A picture item.
37    Picture,
38}
39
40/// One document item contributing to a chunk — the analogue of an entry in
41/// docling's `DocMeta.doc_items`.
42#[derive(Debug, Clone, PartialEq)]
43pub struct ChunkItem {
44    /// The item's ref in [`DoclingDocument::export_to_json`] output
45    /// (`#/texts/12`, `#/tables/0`, `#/pictures/1`, …).
46    pub self_ref: String,
47    pub kind: ChunkItemKind,
48    /// The item serialized *standalone* (docling re-serializes individual
49    /// items when splitting an oversized multi-item chunk — e.g. a nested
50    /// list item flattens to `- text` with no indentation).
51    pub text: String,
52}
53
54/// One chunk — the analogue of docling's `DocChunk` (text + `DocMeta`).
55#[derive(Debug, Clone, PartialEq)]
56pub struct DocChunk {
57    /// The chunk body (markdown-flavoured, unescaped — same text docling puts
58    /// in `DocChunk.text`).
59    pub text: String,
60    /// The heading path above this chunk, outermost first (`DocMeta.headings`;
61    /// `None` when the chunk sits above any heading).
62    pub headings: Option<Vec<String>>,
63    /// The document items the chunk was built from (`DocMeta.doc_items`).
64    pub doc_items: Vec<ChunkItem>,
65}
66
67/// Render a chunk for embedding: the heading path, then the text, joined with
68/// newlines — docling's `BaseChunker.contextualize()`.
69pub fn contextualize(chunk: &DocChunk) -> String {
70    let mut parts: Vec<&str> = Vec::new();
71    if let Some(h) = &chunk.headings {
72        parts.extend(h.iter().map(String::as_str));
73    }
74    parts.push(&chunk.text);
75    parts.join("\n")
76}
77
78// ---------------------------------------------------------------------------
79// Hierarchical chunker
80// ---------------------------------------------------------------------------
81
82/// Structure-driven chunker: one chunk per document item, lists and inline
83/// groups kept whole, heading path tracked as metadata — docling-core's
84/// `HierarchicalChunker` with default parameters.
85#[derive(Debug, Clone, Default)]
86pub struct HierarchicalChunker;
87
88impl HierarchicalChunker {
89    /// Chunk the document.
90    pub fn chunk(&self, doc: &DoclingDocument) -> Vec<DocChunk> {
91        let mut chunks = Vec::new();
92        self.chunk_with(doc, &mut |c| {
93            chunks.push(c);
94            true
95        });
96        chunks
97    }
98
99    /// Stream the chunks: `sink` is called with each chunk as the document
100    /// walk produces it, so a consumer can process (embed, forward) chunks
101    /// without materializing the whole `Vec` first. A `false` return from
102    /// `sink` cancels the walk. [`Self::chunk`] is this with a collecting
103    /// sink — the chunks and their order are identical.
104    pub fn chunk_with(&self, doc: &DoclingDocument, sink: &mut dyn FnMut(DocChunk) -> bool) {
105        let mut w = Walker {
106            alloc: Alloc::default(),
107            headings: BTreeMap::new(),
108            stopped: false,
109            sink,
110        };
111        w.walk(&doc.nodes);
112    }
113}
114
115/// Ref allocator mirroring the numbering `json.rs` gives every item, so
116/// `ChunkItem::self_ref` matches the document's JSON export.
117#[derive(Debug, Default)]
118struct Alloc {
119    texts: usize,
120    groups: usize,
121    tables: usize,
122    pictures: usize,
123    field_regions: usize,
124    field_items: usize,
125}
126
127impl Alloc {
128    fn text(&mut self) -> String {
129        let r = format!("#/texts/{}", self.texts);
130        self.texts += 1;
131        r
132    }
133    fn group(&mut self) -> String {
134        let r = format!("#/groups/{}", self.groups);
135        self.groups += 1;
136        r
137    }
138    fn table(&mut self) -> String {
139        let r = format!("#/tables/{}", self.tables);
140        self.tables += 1;
141        r
142    }
143    fn picture(&mut self) -> String {
144        let r = format!("#/pictures/{}", self.pictures);
145        self.pictures += 1;
146        r
147    }
148    fn field_region(&mut self) -> String {
149        let r = format!("#/field_regions/{}", self.field_regions);
150        self.field_regions += 1;
151        r
152    }
153    fn field_item(&mut self) -> String {
154        let r = format!("#/field_items/{}", self.field_items);
155        self.field_items += 1;
156        r
157    }
158}
159
160struct Walker<'s> {
161    alloc: Alloc,
162    /// Active heading per docling level (title = 0, `section_header` = its
163    /// `level`), pruned like docling's `heading_by_level`.
164    headings: BTreeMap<u8, String>,
165    /// Set once the sink refuses a chunk; the walk unwinds without emitting.
166    stopped: bool,
167    sink: &'s mut dyn FnMut(DocChunk) -> bool,
168}
169
170impl Walker<'_> {
171    fn emit(&mut self, text: String, doc_items: Vec<ChunkItem>) {
172        if self.stopped || text.is_empty() {
173            return;
174        }
175        let headings: Vec<String> = self.headings.values().cloned().collect();
176        self.stopped = !(self.sink)(DocChunk {
177            text,
178            headings: (!headings.is_empty()).then_some(headings),
179            doc_items,
180        });
181    }
182
183    /// Emit a text chunk whose doc items follow docling's inline granularity:
184    /// mixed inline content (a paragraph docling represents as an inline group)
185    /// contributes one item per span, plain text one item.
186    fn emit_inline(&mut self, md_text: &str, self_ref: String) {
187        self.emit_inline_with_runs(md_text, self_ref, &[]);
188    }
189
190    fn emit_inline_with_runs(
191        &mut self,
192        md_text: &str,
193        self_ref: String,
194        runs: &[crate::InlineRun],
195    ) {
196        let body = unescape_text(md_text);
197        if body.is_empty() {
198            return;
199        }
200        let segments: Vec<String> = inline_segments_tagged(md_text)
201            .into_iter()
202            .flat_map(|(text, is_plain)| {
203                if is_plain {
204                    if let Some(split) = split_plain_by_runs(&text, runs) {
205                        return split;
206                    }
207                }
208                vec![text]
209            })
210            .collect();
211        let items: Vec<ChunkItem> = if segments.len() <= 1 {
212            vec![ChunkItem {
213                self_ref,
214                kind: ChunkItemKind::Text,
215                text: body.clone(),
216            }]
217        } else {
218            segments
219                .into_iter()
220                .map(|text| ChunkItem {
221                    self_ref: self_ref.clone(),
222                    kind: ChunkItemKind::Text,
223                    text,
224                })
225                .collect()
226        };
227        self.emit(body, items);
228    }
229
230    fn set_heading(&mut self, doc_level: u8, text: String) {
231        self.headings.retain(|k, _| *k < doc_level);
232        self.headings.insert(doc_level, text);
233    }
234
235    fn walk(&mut self, nodes: &[Node]) {
236        let mut i = 0;
237        while i < nodes.len() {
238            if self.stopped {
239                return;
240            }
241            if matches!(nodes[i], Node::ListItem { .. }) {
242                let start = i;
243                i += 1;
244                loop {
245                    match nodes.get(i) {
246                        Some(Node::ListItem { .. }) => i += 1,
247                        // An empty paragraph between two list items is absorbed
248                        // into the run (mirrors json.rs / markdown.rs).
249                        Some(Node::Paragraph { text })
250                            if text.is_empty()
251                                && matches!(nodes.get(i + 1), Some(Node::ListItem { .. })) =>
252                        {
253                            i += 1
254                        }
255                        _ => break,
256                    }
257                }
258                self.sibling_lists(&nodes[start..i]);
259            } else {
260                self.one(&nodes[i]);
261                i += 1;
262            }
263        }
264    }
265
266    /// Split a run of list items into sibling lists exactly like
267    /// `json.rs::add_sibling_lists`, chunking each list separately (docling
268    /// yields one chunk per `ListGroup`).
269    fn sibling_lists(&mut self, run: &[Node]) {
270        let base = level_of(&run[0]);
271        let mut seg = 0;
272        for k in 0..run.len() {
273            let Node::ListItem {
274                first_in_list,
275                level,
276                ..
277            } = &run[k]
278            else {
279                continue;
280            };
281            if *level != base {
282                continue; // nested item — handled inside `list`
283            }
284            // The backend's list boundary, as in `json.rs::add_sibling_lists`.
285            if k > seg && *first_in_list {
286                self.list(&run[seg..k]);
287                seg = k;
288            }
289        }
290        self.list(&run[seg..]);
291    }
292
293    /// One `ListGroup`: allocate refs in `json.rs::add_list` order (group,
294    /// then per top item its text ref followed by any nested groups) and emit
295    /// a single chunk whose text is the indented markdown list.
296    fn list(&mut self, items: &[Node]) {
297        self.alloc.group();
298        let mut chunk_items = Vec::new();
299        self.list_refs(items, &mut chunk_items);
300        let text = render_list(items);
301        self.emit(text, chunk_items);
302    }
303
304    /// Allocate refs for one list's items (and nested sibling lists), mirroring
305    /// `json.rs::add_list` / `add_sibling_lists` recursion, collecting the
306    /// non-furniture items in allocation (= document) order.
307    fn list_refs(&mut self, items: &[Node], out: &mut Vec<ChunkItem>) {
308        let base = level_of(&items[0]);
309        let mut i = 0;
310        while i < items.len() {
311            let Node::ListItem {
312                ordered,
313                number,
314                text,
315                level,
316                layer,
317                ..
318            } = &items[i]
319            else {
320                i += 1;
321                continue;
322            };
323            if *level > base {
324                i += 1;
325                continue;
326            }
327            let item_ref = self.alloc.text();
328            let mut j = i + 1;
329            while j < items.len() && level_of(&items[j]) > base {
330                j += 1;
331            }
332            let has_nested = j > i + 1;
333            if layer.is_none() {
334                let marker = if *ordered {
335                    format!("{number}.")
336                } else {
337                    "-".to_string()
338                };
339                // An item that carries both inline spans and a nested list is an
340                // empty list item wrapping an inline group in docling's model:
341                // its marker and each inline span are separate doc items.
342                // docling represents a list item whose content is not pure
343                // inline text (it carries a nested list or child pictures) as
344                // an empty item wrapping an inline group: its marker and each
345                // inline span become separate doc items.
346                // docling represents a list item whose content is not pure
347                // inline text (it carries a nested list or its own images) as
348                // an empty item wrapping an inline group: its marker and each
349                // inline span become separate doc items. The chunker's
350                // image placeholder is empty, so the markers are stripped from
351                // the text before segmentation.
352                let has_pics = text.contains("<!-- image -->");
353                let text = strip_image_markers(text);
354                let text = text.as_str();
355                let segments = inline_segments(text);
356                if (has_nested || has_pics) && segments.len() > 1 && text.contains("](") {
357                    out.push(ChunkItem {
358                        self_ref: item_ref.clone(),
359                        kind: ChunkItemKind::Text,
360                        text: format!("{marker} "),
361                    });
362                    for seg in segments {
363                        out.push(ChunkItem {
364                            self_ref: item_ref.clone(),
365                            kind: ChunkItemKind::Text,
366                            text: seg,
367                        });
368                    }
369                } else {
370                    out.push(ChunkItem {
371                        self_ref: item_ref.clone(),
372                        kind: ChunkItemKind::Text,
373                        text: format!("{marker} {}", unescape_text(text)),
374                    });
375                }
376            }
377            // nested items group under this one; each nested sibling list is a
378            // fresh group ref
379            if j > i + 1 {
380                self.nested_sibling_lists(&items[i + 1..j], out);
381            }
382            i = j;
383        }
384    }
385
386    fn nested_sibling_lists(&mut self, run: &[Node], out: &mut Vec<ChunkItem>) {
387        let base = level_of(&run[0]);
388        let mut seg = 0;
389        for k in 0..run.len() {
390            let Node::ListItem {
391                first_in_list,
392                level,
393                ..
394            } = &run[k]
395            else {
396                continue;
397            };
398            if *level != base {
399                continue;
400            }
401            if k > seg && *first_in_list {
402                self.alloc.group();
403                self.list_refs(&run[seg..k], out);
404                seg = k;
405            }
406        }
407        self.alloc.group();
408        self.list_refs(&run[seg..], out);
409    }
410
411    fn one(&mut self, node: &Node) {
412        match node {
413            Node::Heading { level, text } => {
414                let doc_level = if *level == 1 {
415                    0
416                } else {
417                    level.saturating_sub(1)
418                };
419                let self_ref = self.alloc.text();
420                // docling stores heading text unformatted: a heading that is one
421                // uniformly formatted span keeps its plain text; a *partially*
422                // formatted heading becomes an empty heading whose content is an
423                // inline group — which the chunker then yields as a chunk of its
424                // own (under the freshly-set empty heading).
425                let runs = crate::inline_runs_from_markdown(text);
426                if runs.len() <= 1 {
427                    let plain = runs
428                        .first()
429                        .map(|r| r.text.clone())
430                        .unwrap_or_else(|| text.clone());
431                    self.set_heading(doc_level, unescape_text(&plain));
432                } else {
433                    self.set_heading(doc_level, String::new());
434                    let body = unescape_text(text);
435                    self.emit(
436                        body.clone(),
437                        vec![ChunkItem {
438                            self_ref,
439                            kind: ChunkItemKind::Text,
440                            text: body,
441                        }],
442                    );
443                }
444            }
445            Node::Paragraph { text } | Node::ListText { text, .. } => {
446                let t = text.trim();
447                let self_ref = self.alloc.text();
448                // A whole-paragraph display equation is a formula item; docling's
449                // chunk serializer re-wraps the raw latex in `$$…$$`.
450                if let Some(inner) = t
451                    .strip_prefix("$$")
452                    .and_then(|s| s.strip_suffix("$$"))
453                    .filter(|s| !s.is_empty())
454                {
455                    let body = format!("$${inner}$$");
456                    self.emit(
457                        body.clone(),
458                        vec![ChunkItem {
459                            self_ref,
460                            kind: ChunkItemKind::Text,
461                            text: body,
462                        }],
463                    );
464                    return;
465                }
466                self.emit_inline(text, self_ref);
467            }
468            // A standalone caption chunks like any text item (docling's chunker
469            // does not treat `caption` specially outside a table/picture).
470            Node::Caption { text, .. } => {
471                let self_ref = self.alloc.text();
472                self.emit_inline(text, self_ref);
473            }
474            Node::LabeledText { .. } => self.one(&node.labeled_as_paragraph()),
475            Node::CheckboxItem { checked, text } => {
476                let self_ref = self.alloc.text();
477                let mark = if *checked { "- [x] " } else { "- [ ] " };
478                let body = format!("{mark}{}", unescape_text(text));
479                self.emit(
480                    body.clone(),
481                    vec![ChunkItem {
482                        self_ref,
483                        kind: ChunkItemKind::Text,
484                        text: body,
485                    }],
486                );
487            }
488            // An enriched display formula chunks like docling's formula item:
489            // the LaTeX is the chunk text.
490            Node::Formula { latex, .. } => {
491                let self_ref = self.alloc.text();
492                let body = format!("$${}$$", latex);
493                self.emit(
494                    body.clone(),
495                    vec![ChunkItem {
496                        self_ref,
497                        kind: ChunkItemKind::Text,
498                        text: body,
499                    }],
500                );
501            }
502            Node::Code { text, .. } => {
503                let self_ref = self.alloc.text();
504                let body = crate::markdown::code_fence("", &unescape_text(text));
505                self.emit(
506                    body.clone(),
507                    vec![ChunkItem {
508                        self_ref,
509                        kind: ChunkItemKind::Text,
510                        text: body,
511                    }],
512                );
513            }
514            Node::Table(t) => {
515                let self_ref = self.alloc.table();
516                let body = triplet_table_text(t);
517                self.emit(
518                    body.clone(),
519                    vec![ChunkItem {
520                        self_ref,
521                        kind: ChunkItemKind::Table,
522                        text: body,
523                    }],
524                );
525            }
526            Node::Picture {
527                caption,
528                description,
529                ..
530            } => {
531                let cap = caption.as_deref().filter(|c| !c.is_empty());
532                let cap_item = cap.map(|c| ChunkItem {
533                    self_ref: self.alloc.text(),
534                    kind: ChunkItemKind::Text,
535                    text: unescape_text(c),
536                });
537                let pic_ref = self.alloc.picture();
538                // The picture itself serializes to the (empty) chunking image
539                // placeholder, and its caption is already consumed by the
540                // caption chunk — so only the caption text is emitted. A
541                // description (the picture-OCR text, #645) is the picture's
542                // own annotation text — docling's chunker serializes the
543                // picture through the Markdown picture serializer, so the
544                // description lands in the chunk after the caption.
545                let desc = description
546                    .as_ref()
547                    .map(|d| d.text.as_str())
548                    .filter(|t| !t.is_empty());
549                match (cap_item, desc) {
550                    (Some(cap_item), None) => {
551                        let body = cap_item.text.clone();
552                        self.emit(body, vec![cap_item]);
553                    }
554                    (Some(cap_item), Some(desc)) => {
555                        let body = format!("{}\n\n{desc}", cap_item.text);
556                        let pic_item = ChunkItem {
557                            self_ref: pic_ref,
558                            kind: ChunkItemKind::Picture,
559                            text: desc.to_string(),
560                        };
561                        self.emit(body, vec![cap_item, pic_item]);
562                    }
563                    (None, Some(desc)) => {
564                        let pic_item = ChunkItem {
565                            self_ref: pic_ref,
566                            kind: ChunkItemKind::Picture,
567                            text: desc.to_string(),
568                        };
569                        self.emit(desc.to_string(), vec![pic_item]);
570                    }
571                    (None, None) => {}
572                }
573            }
574            Node::Chart {
575                kind,
576                table,
577                caption,
578                ..
579            } => {
580                let cap = caption.as_deref().filter(|c| !c.is_empty());
581                let cap_item = cap.map(|c| ChunkItem {
582                    self_ref: self.alloc.text(),
583                    kind: ChunkItemKind::Text,
584                    text: unescape_text(c),
585                });
586                let pic_ref = self.alloc.picture();
587                // caption, humanized classification, then the chart's data grid
588                // as a (padded) markdown table — docling's picture serializer
589                // parts, joined with blank lines.
590                let mut parts: Vec<String> = Vec::new();
591                if let Some(ci) = &cap_item {
592                    parts.push(ci.text.clone());
593                }
594                parts.push(humanize_label(kind));
595                let grid = crate::markdown::render_table(table, false);
596                if !grid.is_empty() {
597                    parts.push(unescape_text(&grid));
598                }
599                let body = parts.join("\n\n");
600                // Re-serialized standalone (the hybrid window join), the picture
601                // carries its caption itself, while the caption *item* renders
602                // empty — docling's markdown serializer emits caption-label text
603                // only through the picture.
604                let pic_item = ChunkItem {
605                    self_ref: pic_ref,
606                    kind: ChunkItemKind::Picture,
607                    text: body.clone(),
608                };
609                let items = match cap_item {
610                    Some(mut ci) => {
611                        ci.text = String::new();
612                        vec![ci, pic_item]
613                    }
614                    None => vec![pic_item],
615                };
616                self.emit(body, items);
617            }
618            // A group on a non-body layer (a hidden spreadsheet sheet) carries
619            // no chunkable content, like every other non-body item.
620            Node::Group { layer: Some(_), .. } => {}
621            Node::Group { children, .. } => {
622                // A generic group is a structural container: docling recurses
623                // into it rather than chunking it whole.
624                self.alloc.group();
625                self.walk(children);
626            }
627            // A key-value graph holds no text items, so no chunk comes of it.
628            Node::KeyValueGraph { .. } => {}
629            Node::FieldRegion { items } => {
630                // Each field part (marker / key / value) is its own text item,
631                // and docling chunks each one individually.
632                self.alloc.field_region();
633                for item in items {
634                    self.alloc.field_item();
635                    for part in [&item.marker, &item.key, &item.value].into_iter().flatten() {
636                        let self_ref = self.alloc.text();
637                        let body = unescape_text(part);
638                        self.emit(
639                            body.clone(),
640                            vec![ChunkItem {
641                                self_ref,
642                                kind: ChunkItemKind::Text,
643                                text: body,
644                            }],
645                        );
646                    }
647                }
648            }
649            Node::InlineGroup { md_text, runs, .. } => {
650                let self_ref = self.alloc.text();
651                self.emit_inline_with_runs(md_text, self_ref, runs);
652            }
653            Node::TextDump(text) => {
654                let self_ref = self.alloc.text();
655                let body = unescape_text(text);
656                self.emit(
657                    body.clone(),
658                    vec![ChunkItem {
659                        self_ref,
660                        kind: ChunkItemKind::Text,
661                        text: body,
662                    }],
663                );
664            }
665            // Layout provenance and comment annotations are transparent.
666            Node::Located { inner, .. }
667            | Node::Prov { inner, .. }
668            | Node::Track { inner, .. }
669            | Node::Commented { inner, .. } => self.one(inner),
670            // A PDF page header/footer is a furniture-layer JSON text item:
671            // never chunked (docling's chunker reads the body layer), but it
672            // takes a `#/texts/N` number, so later refs keep matching the JSON.
673            Node::PageFurniture { .. } | Node::FurnitureText { .. } => {
674                self.alloc.text();
675            }
676            // A picture's children are JSON items docling's chunker never
677            // reaches (it iterates without `traverse_pictures`): allocate
678            // their refs only — one text each, plus the list group `json.rs`
679            // opens for each list item (each starts its own list) — so later
680            // refs keep matching the JSON.
681            Node::PictureChildren(children) => {
682                for child in children {
683                    match child {
684                        // A header/footer child is numbered exactly as a
685                        // top-level one is, whatever the JSON does with it.
686                        Node::PageFurniture { .. } => self.one(child),
687                        Node::ListItem { .. } => {
688                            self.alloc.group();
689                            self.alloc.text();
690                        }
691                        _ => {
692                            self.alloc.text();
693                        }
694                    }
695                }
696            }
697            // Non-body layers and doclang-only nodes don't reach the chunker
698            // (nor the JSON body).
699            Node::CommentSection { .. }
700            | Node::Furniture { .. }
701            | Node::PageBreak
702            | Node::PageInfo { .. }
703            | Node::Anchor { .. }
704            | Node::DoclangOnly(_) => {}
705            // Runs are grouped by `walk`; a stray single item (hand-built
706            // document, `Located` wrapper) still chunks instead of panicking.
707            Node::ListItem { .. } => self.sibling_lists(std::slice::from_ref(node)),
708        }
709    }
710}
711
712fn level_of(node: &Node) -> u8 {
713    match node {
714        Node::ListItem { level, .. } => *level,
715        _ => 0,
716    }
717}
718
719/// Render one sibling list as its markdown chunk text (indented items, same
720/// rules as the full markdown serializer's list rendering).
721fn render_list(items: &[Node]) -> String {
722    let mut lines: Vec<String> = Vec::new();
723    for item in items {
724        let Node::ListItem {
725            ordered,
726            number,
727            text,
728            level,
729            layer,
730            ..
731        } = item
732        else {
733            continue;
734        };
735        if layer.is_some() {
736            continue;
737        }
738        let indent = "    ".repeat(*level as usize);
739        let marker = if *ordered {
740            format!("{number}.")
741        } else {
742            "-".to_string()
743        };
744        lines.push(format!(
745            "{indent}{marker} {}",
746            unescape_text(&strip_image_markers(text))
747        ));
748    }
749    lines.join("\n")
750}
751
752/// Strip the Markdown image placeholders a list item's own images fold into
753/// its text (the chunking serializer's `image_placeholder` is empty, so
754/// docling's chunk text carries no marker), collapsing the newlines that
755/// carried them.
756fn strip_image_markers(text: &str) -> String {
757    if !text.contains("<!-- image -->") {
758        return text.to_string();
759    }
760    let cleaned: Vec<&str> = text
761        .split('\n')
762        .map(str::trim_end)
763        .filter(|l| *l != "<!-- image -->")
764        .collect();
765    cleaned.join("\n").trim_end().to_string()
766}
767
768/// docling-core's `_humanize_text`: underscores to spaces, first letter
769/// capitalized (`line_chart` → `Line chart`).
770fn humanize_label(label: &str) -> String {
771    let text = label.replace('_', " ");
772    let mut chars = text.chars();
773    match chars.next() {
774        Some(f) => f.to_uppercase().collect::<String>() + chars.as_str(),
775        None => text,
776    }
777}
778
779/// docling's `TripletTableSerializer` over `export_to_dataframe` semantics: the
780/// leading rows carrying column-header cells become the dataframe's column
781/// names (multiple header rows join per column with `.`; no header rows at all
782/// yield pandas' integer column names), the rest are data rows; the dataframe
783/// is then rendered as `row, column = value` sentences (with the header-only /
784/// single-column special cases and the plain-text flatten fallback).
785fn triplet_table_text(t: &Table) -> String {
786    let anchors = t.span_anchors();
787    let rows: Vec<Vec<String>> = t
788        .rows
789        .iter()
790        .enumerate()
791        .map(|(ri, r)| {
792            (0..r.len())
793                .map(|ci| cell_chunk_text(t, &anchors, ri, ci))
794                .collect()
795        })
796        .collect();
797    let num_rows = rows.len();
798    let num_cols = rows.iter().map(Vec::len).max().unwrap_or(0);
799    if num_rows == 0 || num_cols == 0 {
800        return String::new();
801    }
802    let cell = |r: usize, c: usize| -> &str {
803        rows.get(r)
804            .and_then(|row| row.get(c))
805            .map(String::as_str)
806            .unwrap_or("")
807    };
808
809    // The header block is the one the Markdown serializer uses
810    // (`Table::column_header_row_count`, docling-core#767), without its
811    // "no flags -> row 0" fallback: pandas then gets integer column names.
812    let num_headers = t.column_header_row_count().min(num_rows);
813
814    // Column names: header-row texts joined per column with '.', or the integer
815    // positions when there are no header rows.
816    let columns: Vec<String> = if num_headers > 0 {
817        (0..num_cols)
818            .map(|c| {
819                let mut name = String::new();
820                for r in 0..num_headers {
821                    if !name.is_empty() {
822                        name.push('.');
823                    }
824                    name.push_str(cell(r, c));
825                }
826                name
827            })
828            .collect()
829    } else {
830        (0..num_cols).map(|c| c.to_string()).collect()
831    };
832    let data_rows = num_headers..num_rows;
833    let n_data = data_rows.len();
834
835    // Header-only table: emit the header texts directly.
836    if n_data == 0 {
837        return columns
838            .iter()
839            .map(|s| s.trim())
840            .filter(|s| !s.is_empty())
841            .collect::<Vec<_>>()
842            .join(". ");
843    }
844
845    let data = |r: usize, c: usize| -> &str { cell(num_headers + r, c) };
846    let text = if num_cols == 1 {
847        // Single-column: the first data row is the column name, the rest are
848        // values (a single data row emits its cell text alone).
849        let col_name = data(0, 0).trim().to_string();
850        if n_data == 1 {
851            col_name
852        } else {
853            (1..n_data)
854                .map(|r| format!("{col_name} = {}", data(r, 0).trim()))
855                .collect::<Vec<_>>()
856                .join(". ")
857        }
858    } else {
859        // Triplets over the dataframe with the column names copied as row 0.
860        let mut parts = Vec::new();
861        for r in 0..n_data {
862            for (c, col_name) in columns.iter().enumerate().skip(1) {
863                parts.push(format!(
864                    "{}, {} = {}",
865                    data(r, 0).trim(),
866                    col_name.trim(),
867                    data(r, c).trim()
868                ));
869            }
870        }
871        parts.join(". ")
872    };
873    if !text.is_empty() {
874        return text;
875    }
876
877    // Last-resort flatten: the data rows' non-blank cells joined with '. '
878    // (the header rows are the dataframe's columns, so they are not included).
879    (0..n_data)
880        .flat_map(|r| (0..num_cols).map(move |c| (r, c)))
881        .map(|(r, c)| data(r, c).trim())
882        .filter(|s| !s.is_empty())
883        .collect::<Vec<_>>()
884        .join(". ")
885}
886
887/// Split a markdown-flavoured text into docling's inline-item granularity: a
888/// hyperlink / formatted span / inline formula is its own document item in
889/// docling's model, with plain text runs between them. Returns the standalone
890/// serialization of each item (`[text](url)`, `**bold**`, a formula re-wrapped
891/// as `$$latex$$`, plain text), or a single-element vector when the text is one
892/// uniform item. The single space docling's serializer inserts between inline
893/// items is stripped from the adjacent plain runs.
894fn inline_segments(md: &str) -> Vec<String> {
895    inline_segments_tagged(md)
896        .into_iter()
897        .map(|(t, _)| t)
898        .collect()
899}
900
901/// Like [`inline_segments`], with each segment tagged `true` when it came from
902/// plain (unmarked) text — those may still need splitting at run boundaries
903/// invisible in markdown (underline, soft breaks).
904fn inline_segments_tagged(md: &str) -> Vec<(String, bool)> {
905    let chars: Vec<char> = md.chars().collect();
906    let n = chars.len();
907    let find = |from: usize, pat: &str| -> Option<usize> {
908        let hay: String = chars[from..].iter().collect();
909        hay.find(pat).map(|p| from + hay[..p].chars().count())
910    };
911    let mut out: Vec<(String, bool)> = Vec::new();
912    let mut plain = String::new();
913    let mut after_span = false;
914
915    fn flush(
916        out: &mut Vec<(String, bool)>,
917        plain: &mut String,
918        before_span: bool,
919        after_span: bool,
920    ) {
921        let mut p = std::mem::take(plain);
922        if after_span {
923            if let Some(rest) = p.strip_prefix(' ') {
924                p = rest.to_string();
925            }
926        }
927        if before_span {
928            if let Some(rest) = p.strip_suffix(' ') {
929                p = rest.to_string();
930            }
931        }
932        if !p.is_empty() {
933            out.push((unescape_text(&p), true));
934        }
935    }
936
937    let mut i = 0;
938    while i < n {
939        let rest: String = chars[i..].iter().collect();
940        // A hyperlink span (not an image): the whole `[text](url)` is one item.
941        // The URL may itself contain balanced parentheses (`/Duck_(film)`),
942        // so the closing `)` is found by paren depth, not first match.
943        if chars[i] == '[' && !rest.starts_with("[](") {
944            // The label may itself contain balanced brackets (`[[ 1 ]](#ref)`
945            // has label `[ 1 ]`), but an *unbalanced* `[` means this bracket is
946            // plain text preceding a real link (`[ [*note*](url) ]`).
947            let balanced = |c: usize| {
948                let mut d = 0i32;
949                for &ch in &chars[i + 1..c] {
950                    match ch {
951                        '[' => d += 1,
952                        ']' => d -= 1,
953                        _ => {}
954                    }
955                }
956                d == 0
957            };
958            if let Some(close) = find(i + 1, "](").filter(|&c| balanced(c)) {
959                let mut depth = 0usize;
960                let mut url_end = None;
961                for (k, &c) in chars.iter().enumerate().skip(close + 2) {
962                    match c {
963                        '(' => depth += 1,
964                        ')' => {
965                            if depth == 0 {
966                                url_end = Some(k);
967                                break;
968                            }
969                            depth -= 1;
970                        }
971                        _ => {}
972                    }
973                }
974                if let Some(endp) = url_end {
975                    // An unsafe destination (`javascript:`, #860) is plain
976                    // text, not a hyperlink item.
977                    let url: String = chars[close + 2..endp].iter().collect();
978                    if !crate::hyperlink::is_safe_hyperlink(&url) {
979                        plain.extend(&chars[i + 1..close]);
980                        i = endp + 1;
981                        continue;
982                    }
983                    flush(&mut out, &mut plain, true, after_span);
984                    out.push((
985                        unescape_text(&chars[i..=endp].iter().collect::<String>()),
986                        false,
987                    ));
988                    i = endp + 1;
989                    after_span = true;
990                    continue;
991                }
992            }
993        }
994        // An inline code span is a code item in docling's model, whose
995        // standalone form is a fenced block; its backticks may run longer
996        // than one (#859).
997        if chars[i] == '`' {
998            if let Some((s, e, after)) = crate::markdown::code_span_bounds(&chars, i) {
999                if e > s && !chars[s..e].iter().all(|c| c.is_whitespace()) {
1000                    flush(&mut out, &mut plain, true, after_span);
1001                    let inner: String = chars[s..e].iter().collect();
1002                    out.push((
1003                        crate::markdown::code_fence("", &unescape_text(&inner)),
1004                        false,
1005                    ));
1006                    i = after;
1007                    after_span = true;
1008                    continue;
1009                }
1010            }
1011        }
1012        // A formatted span; longest markers first.
1013        let mut matched = false;
1014        for marker in ["***", "**", "*", "~~"] {
1015            if rest.starts_with(marker) {
1016                let mlen = marker.chars().count();
1017                if let Some(end) = find(i + mlen, marker) {
1018                    // A whitespace-only span (`* *` from a literal asterisk in
1019                    // running text next to a real italic) is not a docling run:
1020                    // treat the marker as plain text.
1021                    let inner_blank = chars[i + mlen..end].iter().all(|c| c.is_whitespace());
1022                    if end > i + mlen && !inner_blank {
1023                        flush(&mut out, &mut plain, true, after_span);
1024                        out.push((
1025                            unescape_text(&chars[i..end + mlen].iter().collect::<String>()),
1026                            false,
1027                        ));
1028                        i = end + mlen;
1029                        after_span = true;
1030                        matched = true;
1031                    }
1032                }
1033                break;
1034            }
1035        }
1036        if matched {
1037            continue;
1038        }
1039        // A literal `$$` inside running text is not an inline formula: copy it
1040        // through as plain characters.
1041        if rest.starts_with("$$") {
1042            plain.push_str("$$");
1043            i += 2;
1044            continue;
1045        }
1046        // An inline formula: standalone it re-serializes in display form.
1047        if chars[i] == '$' {
1048            if let Some(end) = find(i + 1, "$") {
1049                if end > i + 1 {
1050                    flush(&mut out, &mut plain, true, after_span);
1051                    let latex: String = chars[i + 1..end].iter().collect();
1052                    out.push((format!("$${latex}$$"), false));
1053                    i = end + 1;
1054                    after_span = true;
1055                    continue;
1056                }
1057            }
1058        }
1059        plain.push(chars[i]);
1060        i += 1;
1061    }
1062    flush(&mut out, &mut plain, false, after_span);
1063    if out.is_empty() {
1064        out.push((unescape_text(md), true));
1065    }
1066    out
1067}
1068
1069/// Split a plain markdown segment at run boundaries the markdown cannot show
1070/// (an underlined run, a `<sub>`/`<sup>` run): when a consecutive window of
1071/// two or more unmarked runs exactly covers the segment, each run is its own
1072/// document item.
1073fn split_plain_by_runs(segment: &str, runs: &[crate::InlineRun]) -> Option<Vec<String>> {
1074    let target = segment.trim();
1075    if target.is_empty() {
1076        return None;
1077    }
1078    let plainish =
1079        |r: &crate::InlineRun| !r.bold && !r.italic && !r.strike && !r.code && !r.formula;
1080    let fully_plain =
1081        |r: &crate::InlineRun| plainish(r) && !r.underline && r.script == crate::Script::Baseline;
1082    let unmarked: Vec<(&str, bool)> = runs
1083        .iter()
1084        .filter(|r| plainish(r))
1085        .map(|r| (r.text.as_str(), fully_plain(r)))
1086        .collect();
1087    for start in 0..unmarked.len() {
1088        let mut rest = target;
1089        let mut taken: Vec<(String, bool)> = Vec::new();
1090        for (t, fully) in &unmarked[start..] {
1091            let t = t.trim();
1092            if t.is_empty() {
1093                continue;
1094            }
1095            match rest.strip_prefix(t) {
1096                Some(r) => {
1097                    taken.push((unescape_text(t), *fully));
1098                    rest = r.trim_start();
1099                    if rest.is_empty() {
1100                        break;
1101                    }
1102                }
1103                None => break,
1104            }
1105        }
1106        if rest.is_empty() && taken.len() >= 2 {
1107            // Consecutive fully-plain pieces (no underline / sub / sup) are one
1108            // annotation in docling's model — `simplify_text_elements` merges
1109            // them joined with a space, so they never split between themselves.
1110            // Only an underline / sub / sup run is a genuine boundary.
1111            let mut merged: Vec<(String, bool)> = Vec::new();
1112            for (t, fully) in taken {
1113                match merged.last_mut() {
1114                    Some((last, true)) if fully => {
1115                        last.push(' ');
1116                        last.push_str(&t);
1117                    }
1118                    _ => merged.push((t, fully)),
1119                }
1120            }
1121            if merged.len() >= 2 {
1122                return Some(merged.into_iter().map(|(t, _)| t).collect());
1123            }
1124            return None;
1125        }
1126    }
1127    None
1128}
1129
1130/// A table cell's text for the triplet serializer. A *rich* cell (one carrying
1131/// block content) is re-serialized the way docling's chunking serializer sees
1132/// it: paragraphs joined with blank lines, a nested table as its own triplet
1133/// sentences, pictures as an empty placeholder. Plain cells use the flat text
1134/// with the markdown image placeholder stripped (the chunking serializer's
1135/// `image_placeholder` is empty).
1136fn cell_chunk_text(t: &Table, anchors: &[Vec<(usize, usize)>], r: usize, c: usize) -> String {
1137    // A rich cell's blocks live on its anchor; every position it covers
1138    // reads them (docling-core#857, #777).
1139    let (ar, ac) = anchors
1140        .get(r)
1141        .and_then(|row| row.get(c))
1142        .copied()
1143        .unwrap_or((r, c));
1144    if let Some(blocks) = t
1145        .cell_blocks
1146        .as_ref()
1147        .and_then(|b| b.get(ar))
1148        .and_then(|row| row.get(ac))
1149        .filter(|b| !b.is_empty())
1150    {
1151        let mut parts: Vec<String> = Vec::new();
1152        for node in blocks.iter() {
1153            let part = block_chunk_text(node);
1154            if !part.is_empty() {
1155                parts.push(part);
1156            }
1157        }
1158        return parts.join("\n\n");
1159    }
1160    let flat = t
1161        .rows
1162        .get(r)
1163        .and_then(|row| row.get(c))
1164        .map(String::as_str)
1165        .unwrap_or("");
1166    unescape_text(flat)
1167        .replace("<!-- image -->", "")
1168        .trim()
1169        .to_string()
1170}
1171
1172/// One block of a rich cell, serialized for chunking.
1173fn block_chunk_text(node: &Node) -> String {
1174    match node {
1175        Node::Paragraph { text } | Node::ListText { text, .. } => unescape_text(text),
1176        Node::LabeledText { .. } => block_chunk_text(&node.labeled_as_paragraph()),
1177        Node::InlineGroup { md_text, .. } => unescape_text(md_text),
1178        Node::Code { text, .. } => crate::markdown::code_fence("", &unescape_text(text)),
1179        Node::Table(inner) => triplet_table_text(inner),
1180        Node::Picture { caption, .. } => caption
1181            .as_deref()
1182            .filter(|c| !c.is_empty())
1183            .map(unescape_text)
1184            .unwrap_or_default(),
1185        Node::ListItem {
1186            ordered,
1187            number,
1188            text,
1189            ..
1190        } => {
1191            let marker = if *ordered {
1192                format!("{number}.")
1193            } else {
1194                "-".to_string()
1195            };
1196            format!("{marker} {}", unescape_text(text))
1197        }
1198        Node::CheckboxItem { checked, text } => {
1199            let mark = if *checked { "- [x] " } else { "- [ ] " };
1200            format!("{mark}{}", unescape_text(text))
1201        }
1202        Node::Heading { text, .. } => unescape_text(text),
1203        Node::Located { inner, .. }
1204        | Node::Prov { inner, .. }
1205        | Node::Track { inner, .. }
1206        | Node::Commented { inner, .. } => block_chunk_text(inner),
1207        Node::Group { layer: Some(_), .. } => String::new(),
1208        Node::Group { children, .. } => children
1209            .iter()
1210            .map(block_chunk_text)
1211            .filter(|s| !s.is_empty())
1212            .collect::<Vec<_>>()
1213            .join("\n"),
1214        _ => String::new(),
1215    }
1216}
1217
1218/// Reverse the model's baked markdown text escaping — same mapping as the JSON
1219/// exporter (docling chunks carry raw text).
1220fn unescape_text(s: &str) -> String {
1221    s.replace("&lt;", "<")
1222        .replace("&gt;", ">")
1223        .replace("&amp;", "&")
1224        .replace("\\_", "_")
1225}
1226
1227// ---------------------------------------------------------------------------
1228// Hybrid chunker
1229// ---------------------------------------------------------------------------
1230
1231/// Token counting for [`HybridChunker`] — docling's `BaseTokenizer`.
1232pub trait ChunkTokenizer {
1233    /// Number of tokens in `text` (no special tokens).
1234    fn count_tokens(&self, text: &str) -> usize;
1235    /// The chunk budget (docling's `max_tokens`, e.g. 256 for MiniLM).
1236    fn max_tokens(&self) -> usize;
1237}
1238
1239/// Tokenization-aware chunker on top of [`HierarchicalChunker`] — docling's
1240/// `HybridChunker` with default parameters (`merge_peers`,
1241/// `repeat_table_header` on; `omit_header_on_overflow` off).
1242pub struct HybridChunker<T: ChunkTokenizer> {
1243    tokenizer: T,
1244    merge_peers: bool,
1245}
1246
1247impl<T: ChunkTokenizer> HybridChunker<T> {
1248    pub fn new(tokenizer: T) -> Self {
1249        Self {
1250            tokenizer,
1251            merge_peers: true,
1252        }
1253    }
1254
1255    /// Disable merging of undersized same-heading neighbours.
1256    pub fn with_merge_peers(mut self, merge_peers: bool) -> Self {
1257        self.merge_peers = merge_peers;
1258        self
1259    }
1260
1261    pub fn max_tokens(&self) -> usize {
1262        self.tokenizer.max_tokens()
1263    }
1264
1265    /// Chunk the document.
1266    pub fn chunk(&self, doc: &DoclingDocument) -> Vec<DocChunk> {
1267        let mut chunks = Vec::new();
1268        self.chunk_with(doc, &mut |c| {
1269            chunks.push(c);
1270            true
1271        });
1272        chunks
1273    }
1274
1275    /// Stream the chunks: each hierarchical chunk is split against the token
1276    /// budget as the document walk produces it, and the peer merge flushes a
1277    /// merged chunk to `sink` as soon as its window closes (a chunk with
1278    /// different headings arrives, or the budget fills). A `false` return from
1279    /// `sink` cancels the chunking. [`Self::chunk`] is this with a collecting
1280    /// sink — the chunks and their order are identical.
1281    pub fn chunk_with(&self, doc: &DoclingDocument, sink: &mut dyn FnMut(DocChunk) -> bool) {
1282        let mut merger = PeerMerger::default();
1283        let mut alive = true;
1284        HierarchicalChunker.chunk_with(doc, &mut |c| {
1285            for split in self.split_by_doc_items(c) {
1286                for chunk in self.split_using_plain_text(split) {
1287                    if !alive {
1288                        return false;
1289                    }
1290                    alive = if self.merge_peers {
1291                        self.merge_push(&mut merger, chunk, sink)
1292                    } else {
1293                        sink(chunk)
1294                    };
1295                }
1296            }
1297            alive
1298        });
1299        if alive {
1300            self.merge_flush(&mut merger, sink);
1301        }
1302    }
1303
1304    fn count_chunk_tokens(&self, chunk: &DocChunk) -> usize {
1305        self.tokenizer.count_tokens(&contextualize(chunk))
1306    }
1307
1308    /// docling's `_make_chunk_from_doc_items`: single-item chunks keep their
1309    /// text; multi-item windows re-join the items' standalone serializations.
1310    fn window_chunk(&self, chunk: &DocChunk, start: usize, end: usize) -> DocChunk {
1311        let doc_items: Vec<ChunkItem> = chunk.doc_items[start..=end].to_vec();
1312        let text = if chunk.doc_items.len() == 1 {
1313            chunk.text.clone()
1314        } else {
1315            doc_items
1316                .iter()
1317                .filter(|it| !it.text.is_empty())
1318                .map(|it| it.text.as_str())
1319                .collect::<Vec<_>>()
1320                .join("\n")
1321        };
1322        DocChunk {
1323            text,
1324            headings: chunk.headings.clone(),
1325            doc_items,
1326        }
1327    }
1328
1329    fn split_by_doc_items(&self, chunk: DocChunk) -> Vec<DocChunk> {
1330        if chunk.doc_items.is_empty() {
1331            return vec![chunk];
1332        }
1333        let max = self.max_tokens();
1334        let num_items = chunk.doc_items.len();
1335        let mut chunks = Vec::new();
1336        let mut window_start = 0usize;
1337        let mut window_end = 0usize; // inclusive
1338        while window_end < num_items {
1339            let mut new_chunk = self.window_chunk(&chunk, window_start, window_end);
1340            if self.count_chunk_tokens(&new_chunk) <= max {
1341                if window_end < num_items - 1 {
1342                    window_end += 1;
1343                    continue;
1344                } else {
1345                    window_end = num_items; // last loop
1346                }
1347            } else if window_start == window_end {
1348                // One item that doesn't fit: keep it; the plain-text splitter
1349                // takes over.
1350                window_end += 1;
1351                window_start = window_end;
1352            } else {
1353                // The window without its last item fit; flush that and start a
1354                // new window at the current item.
1355                new_chunk = self.window_chunk(&chunk, window_start, window_end - 1);
1356                window_start = window_end;
1357            }
1358            chunks.push(new_chunk);
1359        }
1360        chunks
1361    }
1362
1363    fn split_using_plain_text(&self, chunk: DocChunk) -> Vec<DocChunk> {
1364        let total = self.count_chunk_tokens(&chunk);
1365        let max = self.max_tokens();
1366        if total <= max {
1367            return vec![chunk];
1368        }
1369        let text_len = self.tokenizer.count_tokens(&chunk.text);
1370        let other_len = total - text_len;
1371        if other_len >= max {
1372            // Headings alone exceed the budget: drop them and retry.
1373            let stripped = DocChunk {
1374                headings: None,
1375                ..chunk
1376            };
1377            return self.split_using_plain_text(stripped);
1378        }
1379        let available = max - other_len;
1380
1381        let make = |segments: Vec<String>| -> Vec<DocChunk> {
1382            segments
1383                .into_iter()
1384                .map(|s| DocChunk {
1385                    text: s,
1386                    headings: chunk.headings.clone(),
1387                    doc_items: chunk.doc_items.clone(),
1388                })
1389                .collect()
1390        };
1391        if chunk.doc_items.len() == 1 && chunk.doc_items[0].kind == ChunkItemKind::Table {
1392            // Table: split line-based. The triplet serializer has no header
1393            // lines, so this is a line-preserving split of the table text.
1394            // docling-core ≥ 2.103 (docling-core#690, docling.rs#987) budgets
1395            // the pieces at `available` (the window minus the heading path),
1396            // like text, and re-splits with a smaller budget when a piece's
1397            // `contextualize()` still overshoots — token counts are not
1398            // additive, so the subtraction alone can leave a piece a token
1399            // or two over. (≤ 2.102 packed the full window, so every piece
1400            // overran by the heading length — a deliberate fix here.)
1401            let lines: Vec<String> = chunk
1402                .text
1403                .split('\n')
1404                .filter(|l| !l.trim().is_empty())
1405                .map(|l| l.to_string())
1406                .collect();
1407            let mut budget = available;
1408            loop {
1409                let pieces = make(line_chunk_text(&lines, &self.tokenizer, budget));
1410                let overflow = pieces
1411                    .iter()
1412                    .map(|p| self.count_chunk_tokens(p).saturating_sub(max))
1413                    .max()
1414                    .unwrap_or(0);
1415                if overflow == 0 || budget <= overflow {
1416                    return pieces;
1417                }
1418                budget -= overflow;
1419            }
1420        }
1421        make(semchunk(&chunk.text, available, &self.tokenizer))
1422    }
1423
1424    /// One step of docling's `_merge_chunks_with_matching_metadata`, streamed:
1425    /// extend the window with `chunk` when its headings match the window's and
1426    /// the merged window stays within budget, otherwise flush the window to
1427    /// `sink` and start a new one at `chunk`. Returns `false` once the sink
1428    /// cancels.
1429    ///
1430    /// Linear, as docling-core 2.102 has it (docling-core#823, #782): each
1431    /// chunk's text is counted once, the window grows on a running estimate
1432    /// (text tokens, the delimiter's cost, the headings' overhead), an exact
1433    /// count of the merged window runs only where the estimate overflows, and
1434    /// the final window is verified exactly — shrunk back to the largest one
1435    /// that fits when the estimate under-counted, the chunks it gives up
1436    /// starting the next window. Rebuilding and re-tokenizing the whole window
1437    /// for every chunk was quadratic in the window's length.
1438    fn merge_push(
1439        &self,
1440        m: &mut PeerMerger,
1441        chunk: DocChunk,
1442        sink: &mut dyn FnMut(DocChunk) -> bool,
1443    ) -> bool {
1444        self.merge_feed(m, VecDeque::from([(chunk, None)]), sink)
1445    }
1446
1447    /// Feed chunks (with their text token count when already known) to the
1448    /// merge window, closing it whenever a chunk cannot join.
1449    fn merge_feed(
1450        &self,
1451        m: &mut PeerMerger,
1452        mut pending: VecDeque<(DocChunk, Option<usize>)>,
1453        sink: &mut dyn FnMut(DocChunk) -> bool,
1454    ) -> bool {
1455        while let Some((chunk, tokens)) = pending.pop_front() {
1456            let tokens = tokens.unwrap_or_else(|| self.tokenizer.count_tokens(&chunk.text));
1457            if let Err(chunk) = self.merge_extend(m, chunk, tokens) {
1458                let (alive, rest) = self.merge_close(m, sink);
1459                if !alive {
1460                    return false;
1461                }
1462                pending.push_front((chunk, Some(tokens)));
1463                for item in rest.into_iter().rev() {
1464                    pending.push_front(item);
1465                }
1466            }
1467        }
1468        true
1469    }
1470
1471    /// Add `chunk` (of `tokens` text tokens) to the window, or hand it back
1472    /// when its headings differ or the window would overflow.
1473    fn merge_extend(
1474        &self,
1475        m: &mut PeerMerger,
1476        chunk: DocChunk,
1477        tokens: usize,
1478    ) -> Result<(), DocChunk> {
1479        let max = self.max_tokens() as i64;
1480        if m.window.is_empty() {
1481            // The headings' overhead around the joined text is shared by every
1482            // candidate of this window (it may be negative).
1483            m.overhead = self.count_chunk_tokens(&chunk) as i64 - tokens as i64;
1484            m.running = tokens as i64;
1485            m.window.push((chunk, tokens));
1486            return Ok(());
1487        }
1488        if chunk.headings != m.window[0].0.headings {
1489            return Err(chunk);
1490        }
1491        let delim = *m.delim.get_or_insert_with(|| {
1492            // `_estimate_delimiter_tokens`: what joining two texts adds.
1493            let t = &self.tokenizer;
1494            t.count_tokens("a\nb") as i64 - t.count_tokens("a") as i64 - t.count_tokens("b") as i64
1495        });
1496        m.running += tokens as i64 + delim;
1497        if m.running + m.overhead > max {
1498            let exact = self.count_chunk_tokens(&merged_chunk(
1499                m.window.iter().map(|(c, _)| c).chain([&chunk]),
1500            )) as i64;
1501            if exact > max {
1502                return Err(chunk);
1503            }
1504            // The estimate overshot; re-anchor it on the exact count.
1505            m.running = exact - m.overhead;
1506        }
1507        m.window.push((chunk, tokens));
1508        Ok(())
1509    }
1510
1511    /// Close the window: verify it exactly, shrinking it back to the largest
1512    /// prefix that fits, emit that (a single chunk unchanged), and return the
1513    /// chunks given up, which start the next window.
1514    fn merge_close(
1515        &self,
1516        m: &mut PeerMerger,
1517        sink: &mut dyn FnMut(DocChunk) -> bool,
1518    ) -> (bool, Vec<(DocChunk, Option<usize>)>) {
1519        if m.window.is_empty() {
1520            return (true, Vec::new());
1521        }
1522        let max = self.max_tokens();
1523        let mut fit = m.window.len() - 1;
1524        while fit > 0
1525            && self.count_chunk_tokens(&merged_chunk(m.window[..=fit].iter().map(|(c, _)| c))) > max
1526        {
1527            fit -= 1;
1528        }
1529        let rest = m
1530            .window
1531            .split_off(fit + 1)
1532            .into_iter()
1533            .map(|(c, t)| (c, Some(t)))
1534            .collect();
1535        let out = if m.window.len() == 1 {
1536            m.window.pop().expect("single-chunk window").0
1537        } else {
1538            let merged = merged_chunk(m.window.iter().map(|(c, _)| c));
1539            m.window.clear();
1540            merged
1541        };
1542        (sink(out), rest)
1543    }
1544
1545    /// Flush the merge window at the end of the stream (feeding back what a
1546    /// shrunk window gave up). Returns `false` once the sink cancels.
1547    fn merge_flush(&self, m: &mut PeerMerger, sink: &mut dyn FnMut(DocChunk) -> bool) -> bool {
1548        while !m.window.is_empty() {
1549            let (alive, rest) = self.merge_close(m, sink);
1550            if !alive || !self.merge_feed(m, rest.into(), sink) {
1551                return false;
1552            }
1553        }
1554        true
1555    }
1556}
1557
1558/// docling's merged peer chunk: the texts joined by `\n`, every chunk's doc
1559/// items, the first chunk's headings.
1560fn merged_chunk<'a>(chunks: impl Iterator<Item = &'a DocChunk> + Clone) -> DocChunk {
1561    let mut first = chunks.clone();
1562    DocChunk {
1563        text: chunks
1564            .clone()
1565            .map(|c| c.text.as_str())
1566            .collect::<Vec<_>>()
1567            .join("\n"),
1568        headings: first.next().and_then(|c| c.headings.clone()),
1569        doc_items: chunks.flat_map(|c| c.doc_items.iter().cloned()).collect(),
1570    }
1571}
1572
1573/// The in-flight peer-merge window of [`HybridChunker::chunk_with`]: the
1574/// window's chunks with their text token counts, the running token estimate
1575/// of the joined text, the window's headings overhead, and the delimiter's
1576/// token cost (measured once).
1577#[derive(Default)]
1578struct PeerMerger {
1579    window: Vec<(DocChunk, usize)>,
1580    running: i64,
1581    overhead: i64,
1582    delim: Option<i64>,
1583}
1584
1585// ---------------------------------------------------------------------------
1586// Line-based token chunking (docling's LineBasedTokenChunker, empty prefix)
1587// ---------------------------------------------------------------------------
1588
1589/// Pack lines into chunks of at most `max_tokens`, splitting a line only when
1590/// it exceeds the budget on its own — docling's `LineBasedTokenChunker
1591/// .chunk_text` with an empty prefix (which is what the triplet table
1592/// serializer yields). Reproduces its exact output, including the `\n` it
1593/// prepends to a carried-over segment of an oversized line.
1594fn line_chunk_text<T: ChunkTokenizer>(lines: &[String], tok: &T, max_tokens: usize) -> Vec<String> {
1595    let mut chunks: Vec<String> = Vec::new();
1596    let mut current = String::new();
1597    let mut current_len = 0usize;
1598
1599    for line in lines {
1600        let mut remaining: Vec<char> = line.chars().collect();
1601        loop {
1602            let rem_str: String = remaining.iter().collect();
1603            let line_tokens = tok.count_tokens(&rem_str);
1604            let available = max_tokens.saturating_sub(current_len);
1605
1606            if line_tokens <= available {
1607                current.push_str(&rem_str);
1608                current_len += line_tokens;
1609                break;
1610            }
1611            if line_tokens <= max_tokens {
1612                chunks.push(std::mem::take(&mut current));
1613                current_len = 0;
1614                continue;
1615            }
1616            // Too large even for an empty chunk: split off what fits.
1617            let (mut take, rest) = split_by_token_limit(&remaining, available, tok);
1618            let mut rest = rest;
1619            if take.is_empty() {
1620                if rest.is_empty() {
1621                    break;
1622                }
1623                take = rest[..1].iter().collect();
1624                rest = rest[1..].to_vec();
1625            }
1626            current.push('\n');
1627            current.push_str(&take);
1628            chunks.push(std::mem::take(&mut current));
1629            current_len = 0;
1630            remaining = rest;
1631        }
1632    }
1633    if !current.is_empty() {
1634        chunks.push(current);
1635    }
1636    chunks
1637}
1638
1639/// Binary-search the longest char-prefix of `text` within `token_limit`
1640/// tokens, preferring to break at the last ASCII space — docling's
1641/// `split_by_token_limit`.
1642fn split_by_token_limit<T: ChunkTokenizer>(
1643    text: &[char],
1644    token_limit: usize,
1645    tok: &T,
1646) -> (String, Vec<char>) {
1647    if token_limit == 0 || text.is_empty() {
1648        return (String::new(), text.to_vec());
1649    }
1650    let full: String = text.iter().collect();
1651    if tok.count_tokens(&full) <= token_limit {
1652        return (full, Vec::new());
1653    }
1654    let (mut lo, mut hi) = (0usize, text.len());
1655    let mut best: Option<usize> = None;
1656    while lo <= hi {
1657        let mid = (lo + hi) / 2;
1658        let head: String = text[..mid].iter().collect();
1659        if tok.count_tokens(&head) <= token_limit {
1660            best = Some(mid);
1661            lo = mid + 1;
1662        } else {
1663            if mid == 0 {
1664                break;
1665            }
1666            hi = mid - 1;
1667        }
1668    }
1669    let mut best_idx = match best {
1670        Some(b) if b > 0 => b,
1671        _ => return (String::new(), text.to_vec()),
1672    };
1673    // Snap back to the last space, if that leaves a non-empty head.
1674    if let Some(pos) = text[..best_idx].iter().rposition(|c| *c == ' ') {
1675        if pos > 0 {
1676            best_idx = pos;
1677        }
1678    }
1679    (text[..best_idx].iter().collect(), text[best_idx..].to_vec())
1680}
1681
1682// ---------------------------------------------------------------------------
1683// semchunk port (the plain-text splitter HybridChunker delegates to)
1684// ---------------------------------------------------------------------------
1685
1686/// Semantically meaningful non-whitespace splitters, most desirable first.
1687const NON_WS_SPLITTERS: &[&str] = &[
1688    ".", "?", "!", "*", ";", ",", "(", ")", "[", "]", "\u{201c}", "\u{201d}", "\u{2018}",
1689    "\u{2019}", "'", "\"", "`", ":", "\u{2014}", "\u{2026}", "/", "\\", "\u{2013}", "&", "-",
1690];
1691
1692/// Split `text` into chunks of at most `chunk_size` tokens using the most
1693/// semantically meaningful splitter available — the `semchunk` algorithm
1694/// docling's HybridChunker delegates plain-text splitting to.
1695pub fn semchunk<T: ChunkTokenizer>(text: &str, chunk_size: usize, tok: &T) -> Vec<String> {
1696    let mut cache: std::collections::HashMap<String, usize> = std::collections::HashMap::new();
1697    let mut counter = |s: &str| -> usize {
1698        if let Some(n) = cache.get(s) {
1699            return *n;
1700        }
1701        let n = tok.count_tokens(s);
1702        cache.insert(s.to_string(), n);
1703        n
1704    };
1705    let chunks = semchunk_rec(text, chunk_size, &mut counter);
1706    // top-level: drop empty / all-whitespace chunks
1707    chunks
1708        .into_iter()
1709        .filter(|c| !c.is_empty() && !c.chars().all(char::is_whitespace))
1710        .collect()
1711}
1712
1713/// One recursion level of semchunk: split, merge windows back up to size, and
1714/// recurse into oversized splits.
1715fn semchunk_rec(
1716    text: &str,
1717    chunk_size: usize,
1718    counter: &mut dyn FnMut(&str) -> usize,
1719) -> Vec<String> {
1720    let (splitter, splitter_is_ws, splits) = split_text(text);
1721
1722    let split_lens: Vec<usize> = splits.iter().map(|s| s.chars().count()).collect();
1723    let mut cum_lens = Vec::with_capacity(splits.len() + 1);
1724    cum_lens.push(0usize);
1725    for l in &split_lens {
1726        cum_lens.push(cum_lens.last().unwrap() + l);
1727    }
1728    let num_splits_plus_one = splits.len() + 1;
1729
1730    let mut chunks: Vec<String> = Vec::new();
1731    let mut skips: std::collections::HashSet<usize> = std::collections::HashSet::new();
1732
1733    for i in 0..splits.len() {
1734        if skips.contains(&i) {
1735            continue;
1736        }
1737        let split = &splits[i];
1738        if counter(split) > chunk_size {
1739            let inner = semchunk_rec(split, chunk_size, counter);
1740            chunks.extend(inner);
1741        } else {
1742            let (end, merged) = merge_splits(
1743                &splits,
1744                &cum_lens,
1745                chunk_size,
1746                &splitter,
1747                counter,
1748                i,
1749                num_splits_plus_one,
1750            );
1751            for j in (i + 1)..end {
1752                skips.insert(j);
1753            }
1754            chunks.push(merged);
1755        }
1756        // Re-attach a non-whitespace splitter to the last chunk (or emit it as
1757        // its own chunk if it doesn't fit).
1758        let is_last = i == splits.len() - 1 || ((i + 1)..splits.len()).all(|j| skips.contains(&j));
1759        if !splitter_is_ws && !is_last {
1760            let with_splitter = format!(
1761                "{}{}",
1762                chunks.last().map(String::as_str).unwrap_or(""),
1763                splitter
1764            );
1765            if counter(&with_splitter) <= chunk_size {
1766                if let Some(last) = chunks.last_mut() {
1767                    *last = with_splitter;
1768                } else {
1769                    chunks.push(with_splitter);
1770                }
1771            } else {
1772                chunks.push(splitter.clone());
1773            }
1774        }
1775    }
1776    chunks
1777}
1778
1779/// docling/semchunk's `merge_splits`: extend the window with a cum-length-guided
1780/// binary search until the token budget is hit.
1781fn merge_splits(
1782    splits: &[String],
1783    cum_lens: &[usize],
1784    chunk_size: usize,
1785    splitter: &str,
1786    counter: &mut dyn FnMut(&str) -> usize,
1787    start: usize,
1788    high_init: usize,
1789) -> (usize, String) {
1790    let mut average = 0.2f64;
1791    let mut low = start;
1792    let mut high = high_init;
1793    let offset = cum_lens[start];
1794    let mut target = offset as f64 + (chunk_size as f64 * average);
1795
1796    while low < high {
1797        let i = bisect_left(cum_lens, target, low, high);
1798        let midpoint = i.min(high - 1);
1799        let joined = splits[start..midpoint.max(start)].join(splitter);
1800        let tokens = counter(&joined);
1801        let local_cum = cum_lens[midpoint] - offset;
1802        if local_cum > 0 && tokens > 0 {
1803            average = local_cum as f64 / tokens as f64;
1804            target = offset as f64 + (chunk_size as f64 * average);
1805        }
1806        if tokens > chunk_size {
1807            high = midpoint;
1808        } else {
1809            low = midpoint + 1;
1810        }
1811    }
1812    let end = low - 1;
1813    (end, splits[start..end.max(start)].join(splitter))
1814}
1815
1816fn bisect_left(sorted: &[usize], target: f64, mut low: usize, mut high: usize) -> usize {
1817    while low < high {
1818        let mid = (low + high) / 2;
1819        if (sorted[mid] as f64) < target {
1820            low = mid + 1;
1821        } else {
1822            high = mid;
1823        }
1824    }
1825    low
1826}
1827
1828/// semchunk's `_split_text`: pick the most desirable splitter present.
1829fn split_text(text: &str) -> (String, bool, Vec<String>) {
1830    // Longest run of newlines/carriage returns.
1831    if text.contains('\n') || text.contains('\r') {
1832        let splitter = longest_run(text, |c| c == '\n' || c == '\r');
1833        return (splitter.clone(), true, split_on(text, &splitter));
1834    }
1835    // Longest run of tabs.
1836    if text.contains('\t') {
1837        let splitter = longest_run(text, |c| c == '\t');
1838        return (splitter.clone(), true, split_on(text, &splitter));
1839    }
1840    // Longest run of whitespace.
1841    if text.chars().any(char::is_whitespace) {
1842        let splitter = longest_run(text, char::is_whitespace);
1843        if splitter.chars().count() == 1 {
1844            // Prefer a whitespace char preceded by a semantic splitter.
1845            for preceder in NON_WS_SPLITTERS {
1846                if let Some((ws, parts)) = split_after_preceder(text, preceder) {
1847                    return (ws, true, parts);
1848                }
1849            }
1850        }
1851        return (splitter.clone(), true, split_on(text, &splitter));
1852    }
1853    // Most desirable semantic splitter present.
1854    for s in NON_WS_SPLITTERS {
1855        if text.contains(s) {
1856            return (s.to_string(), false, split_on(text, s));
1857        }
1858    }
1859    // No splitter at all: split into characters.
1860    (
1861        String::new(),
1862        true,
1863        text.chars().map(|c| c.to_string()).collect(),
1864    )
1865}
1866
1867/// The longest maximal run of chars matching `pred` (first one wins ties).
1868fn longest_run(text: &str, pred: impl Fn(char) -> bool) -> String {
1869    let mut best = String::new();
1870    let mut cur = String::new();
1871    for c in text.chars() {
1872        if pred(c) {
1873            cur.push(c);
1874        } else {
1875            if cur.chars().count() > best.chars().count() {
1876                best = cur.clone();
1877            }
1878            cur.clear();
1879        }
1880    }
1881    if cur.chars().count() > best.chars().count() {
1882        best = cur;
1883    }
1884    best
1885}
1886
1887fn split_on(text: &str, splitter: &str) -> Vec<String> {
1888    text.split(splitter).map(str::to_string).collect()
1889}
1890
1891/// Python: `re.search(rf'{p}(\s)', text)` → the first whitespace char preceded
1892/// by `p`; then `re.split(rf'(?<={p}){s}', text)` — split at every occurrence
1893/// of that whitespace char immediately preceded by `p`.
1894fn split_after_preceder(text: &str, preceder: &str) -> Option<(String, Vec<String>)> {
1895    let chars: Vec<char> = text.chars().collect();
1896    let p: Vec<char> = preceder.chars().collect();
1897    let mut ws: Option<char> = None;
1898    for i in p.len()..chars.len() {
1899        if chars[i].is_whitespace() && chars[i - p.len()..i] == p[..] {
1900            ws = Some(chars[i]);
1901            break;
1902        }
1903    }
1904    let ws = ws?;
1905    let mut parts = Vec::new();
1906    let mut cur = String::new();
1907    let mut i = 0usize;
1908    while i < chars.len() {
1909        if chars[i] == ws && i >= p.len() && chars[i - p.len()..i] == p[..] {
1910            parts.push(std::mem::take(&mut cur));
1911            i += 1;
1912            continue;
1913        }
1914        cur.push(chars[i]);
1915        i += 1;
1916    }
1917    parts.push(cur);
1918    Some((ws.to_string(), parts))
1919}
1920
1921// ---------------------------------------------------------------------------
1922// HuggingFace tokenizer (feature `chunking`)
1923// ---------------------------------------------------------------------------
1924
1925#[cfg(feature = "chunking")]
1926mod hf {
1927    use super::ChunkTokenizer;
1928
1929    /// Where `scripts/install/download_dependencies.sh` puts the hybrid
1930    /// chunker's default tokenizer (all-MiniLM-L6-v2's `tokenizer.json`),
1931    /// relative to the process's working directory — the same convention as
1932    /// the `.models/` ONNX files.
1933    pub const DEFAULT_TOKENIZER_PATH: &str = ".models/chunk/tokenizer.json";
1934
1935    /// Resolve the tokenizer path for the hybrid chunker: an explicit path
1936    /// wins; otherwise fall back to [`DEFAULT_TOKENIZER_PATH`] when it exists
1937    /// on disk. Errors with the download instructions when neither is
1938    /// available.
1939    pub fn resolve_tokenizer_path(explicit: Option<&str>) -> Result<String, String> {
1940        if let Some(p) = explicit {
1941            return Ok(p.to_string());
1942        }
1943        let resolved = crate::assets::resolve(DEFAULT_TOKENIZER_PATH);
1944        if std::path::Path::new(&resolved).exists() {
1945            return Ok(resolved);
1946        }
1947        Err(format!(
1948            "the hybrid chunker needs a HuggingFace tokenizer.json: none passed and \
1949             {DEFAULT_TOKENIZER_PATH} does not exist — run \
1950             scripts/install/download_dependencies.sh (or pass an explicit path)"
1951        ))
1952    }
1953
1954    /// [`ChunkTokenizer`] backed by a HuggingFace `tokenizer.json` — the Rust
1955    /// analogue of docling's `HuggingFaceTokenizer` (whose default is
1956    /// `sentence-transformers/all-MiniLM-L6-v2` with `max_tokens` 256).
1957    pub struct HuggingFaceTokenizer {
1958        tok: tokenizers::Tokenizer,
1959        max_tokens: usize,
1960    }
1961
1962    impl HuggingFaceTokenizer {
1963        /// Load the tokenizer from an explicit path, or from
1964        /// [`DEFAULT_TOKENIZER_PATH`] when `path` is `None` (see
1965        /// [`resolve_tokenizer_path`]).
1966        pub fn resolve(path: Option<&str>, max_tokens: usize) -> Result<Self, String> {
1967            Self::from_file(resolve_tokenizer_path(path)?, max_tokens)
1968        }
1969
1970        /// Load a `tokenizer.json`. `max_tokens` is the chunk budget (docling
1971        /// resolves it from the model's `sentence_bert_config.json`; for the
1972        /// default MiniLM model that is 256).
1973        pub fn from_file(
1974            path: impl AsRef<std::path::Path>,
1975            max_tokens: usize,
1976        ) -> Result<Self, String> {
1977            let mut tok = tokenizers::Tokenizer::from_file(path.as_ref())
1978                .map_err(|e| format!("failed to load tokenizer: {e}"))?;
1979            // Counting must see the full text (docling tokenizes without
1980            // truncation, padding, or special tokens — MiniLM's tokenizer.json
1981            // ships with fixed-length padding enabled, which would make every
1982            // short string count as the padded length).
1983            let _ = tok.with_truncation(None);
1984            tok.with_padding(None);
1985            Ok(Self { tok, max_tokens })
1986        }
1987    }
1988
1989    impl ChunkTokenizer for HuggingFaceTokenizer {
1990        fn count_tokens(&self, text: &str) -> usize {
1991            self.tok
1992                .encode(text, false)
1993                .map(|e| e.get_tokens().len())
1994                .unwrap_or(0)
1995        }
1996        fn max_tokens(&self) -> usize {
1997            self.max_tokens
1998        }
1999    }
2000}
2001
2002#[cfg(feature = "chunking")]
2003pub use hf::{resolve_tokenizer_path, HuggingFaceTokenizer, DEFAULT_TOKENIZER_PATH};
2004
2005// ---------------------------------------------------------------------------
2006// Window chunker (feature `chunking`) — docling-rag's Markdown window chunker
2007// ---------------------------------------------------------------------------
2008
2009#[cfg(feature = "chunking")]
2010mod window {
2011    use super::DocChunk;
2012    use pulldown_cmark::{Event, HeadingLevel, Parser, Tag, TagEnd};
2013
2014    /// A contiguous run of body text under a heading path.
2015    #[derive(Debug, Clone, Default)]
2016    pub struct Section {
2017        /// The heading stack in effect for this section, outermost first
2018        /// (e.g. `["Guide", "Setup"]`). Empty for pre-heading / body-only text.
2019        pub heading_path: Vec<String>,
2020        /// The plain words of the section body, markup stripped.
2021        pub words: Vec<String>,
2022    }
2023
2024    impl Section {
2025        /// The heading path rendered as a single context line, e.g.
2026        /// `# Guide > Setup`. Empty string when there is no heading.
2027        pub fn heading_context(&self) -> String {
2028            if self.heading_path.is_empty() {
2029                String::new()
2030            } else {
2031                format!("# {}", self.heading_path.join(" > "))
2032            }
2033        }
2034    }
2035
2036    fn level_index(level: HeadingLevel) -> usize {
2037        match level {
2038            HeadingLevel::H1 => 1,
2039            HeadingLevel::H2 => 2,
2040            HeadingLevel::H3 => 3,
2041            HeadingLevel::H4 => 4,
2042            HeadingLevel::H5 => 5,
2043            HeadingLevel::H6 => 6,
2044        }
2045    }
2046
2047    /// Parse Markdown into heading-bounded sections. A new section starts at
2048    /// every heading; the heading path is maintained as a stack keyed by
2049    /// heading level.
2050    pub fn parse_sections(markdown: &str) -> Vec<Section> {
2051        parse_sections_with_stack(markdown, Vec::new()).0
2052    }
2053
2054    /// [`parse_sections`] with an explicit initial heading stack, returning the
2055    /// final stack — lets a streaming caller carry heading context across
2056    /// pieces. `heading_stack[i]` holds the current heading text at level `i+1`
2057    /// (may be empty when a level was skipped).
2058    pub fn parse_sections_with_stack(
2059        markdown: &str,
2060        initial_stack: Vec<String>,
2061    ) -> (Vec<Section>, Vec<String>) {
2062        let mut heading_stack: Vec<String> = initial_stack;
2063        let mut sections: Vec<Section> = Vec::new();
2064        // Text before the first heading of this piece continues the carried-over
2065        // section, so it keeps the heading path in effect at the split point.
2066        let mut current = Section {
2067            heading_path: heading_stack
2068                .iter()
2069                .filter(|h| !h.is_empty())
2070                .cloned()
2071                .collect(),
2072            words: Vec::new(),
2073        };
2074
2075        let mut in_heading = false;
2076        let mut heading_level = 0usize;
2077        let mut heading_buf = String::new();
2078
2079        let push_words = |section: &mut Section, text: &str| {
2080            for w in text.split_whitespace() {
2081                section.words.push(w.to_string());
2082            }
2083        };
2084
2085        let flush = |sections: &mut Vec<Section>, section: &mut Section| {
2086            if !section.words.is_empty() {
2087                sections.push(std::mem::take(section));
2088            } else {
2089                *section = Section::default();
2090            }
2091        };
2092
2093        for event in Parser::new(markdown) {
2094            match event {
2095                Event::Start(Tag::Heading { level, .. }) => {
2096                    in_heading = true;
2097                    heading_level = level_index(level);
2098                    heading_buf.clear();
2099                }
2100                Event::End(TagEnd::Heading(_)) => {
2101                    in_heading = false;
2102                    // Update the heading stack: set this level, drop anything deeper.
2103                    let idx = heading_level.saturating_sub(1);
2104                    if heading_stack.len() <= idx {
2105                        heading_stack.resize(idx + 1, String::new());
2106                    } else {
2107                        heading_stack.truncate(idx + 1);
2108                    }
2109                    heading_stack[idx] = heading_buf.trim().to_string();
2110                    // A heading begins a new section.
2111                    flush(&mut sections, &mut current);
2112                    current.heading_path = heading_stack
2113                        .iter()
2114                        .filter(|h| !h.is_empty())
2115                        .cloned()
2116                        .collect();
2117                }
2118                Event::Text(t) | Event::Code(t) => {
2119                    if in_heading {
2120                        if !heading_buf.is_empty() {
2121                            heading_buf.push(' ');
2122                        }
2123                        heading_buf.push_str(&t);
2124                    } else {
2125                        push_words(&mut current, &t);
2126                    }
2127                }
2128                // Treat hard/soft breaks and rules as whitespace (words already split).
2129                Event::SoftBreak | Event::HardBreak | Event::Rule => {}
2130                _ => {}
2131            }
2132        }
2133        flush(&mut sections, &mut current);
2134        (sections, heading_stack)
2135    }
2136
2137    /// docling-rag's Markdown **window chunker**: the document is split into
2138    /// heading-bounded [`Section`]s of plain words (markup stripped), and a
2139    /// fixed-size window of [`Self::max_words`] words slides over each section
2140    /// with [`Self::overlap`] fractional overlap. A chunk never crosses a
2141    /// heading boundary; [`Self::contextualize`] prefixes the heading path.
2142    #[derive(Debug, Clone)]
2143    pub struct WindowChunker {
2144        /// Window size in words (docling-rag's default 300).
2145        pub max_words: usize,
2146        /// Fractional overlap between consecutive windows (default 0.05 = 5%).
2147        pub overlap: f32,
2148    }
2149
2150    impl Default for WindowChunker {
2151        fn default() -> Self {
2152            WindowChunker {
2153                max_words: 300,
2154                overlap: 0.05,
2155            }
2156        }
2157    }
2158
2159    impl WindowChunker {
2160        pub fn new(max_words: usize, overlap: f32) -> Self {
2161            WindowChunker { max_words, overlap }
2162        }
2163
2164        /// The window size, kept ≥ 1.
2165        fn word_budget(&self) -> usize {
2166            self.max_words.max(1)
2167        }
2168
2169        /// Number of words carried from one window into the next; capped so
2170        /// the window always advances.
2171        fn overlap_words(&self, budget: usize) -> usize {
2172            let o = (budget as f32 * self.overlap).round() as usize;
2173            o.min(budget.saturating_sub(1))
2174        }
2175
2176        /// Chunk a Markdown document.
2177        pub fn chunk(&self, markdown: &str) -> Vec<DocChunk> {
2178            let mut chunks = Vec::new();
2179            self.chunk_with(markdown, &mut |c| {
2180                chunks.push(c);
2181                true
2182            });
2183            chunks
2184        }
2185
2186        /// Stream the chunks: `sink` receives each window as it is cut, and a
2187        /// `false` return cancels. [`Self::chunk`] is this with a collecting
2188        /// sink — the chunks and their order are identical.
2189        pub fn chunk_with(&self, markdown: &str, sink: &mut dyn FnMut(DocChunk) -> bool) {
2190            let (sections, _) = parse_sections_with_stack(markdown, Vec::new());
2191            for section in &sections {
2192                if !self.pack_section(section, sink) {
2193                    return;
2194                }
2195            }
2196        }
2197
2198        /// Slide the window over one completed section, feeding each chunk to
2199        /// `sink`. Returns `false` once the sink cancels — exposed so a
2200        /// streaming caller (docling-rag) can pack sections as they complete.
2201        pub fn pack_section(
2202            &self,
2203            section: &Section,
2204            sink: &mut dyn FnMut(DocChunk) -> bool,
2205        ) -> bool {
2206            let words = &section.words;
2207            if words.is_empty() {
2208                return true;
2209            }
2210            let budget = self.word_budget();
2211            let step = budget - self.overlap_words(budget); // ≥ 1 by construction
2212            let mut start = 0;
2213            loop {
2214                let end = (start + budget).min(words.len());
2215                let chunk = DocChunk {
2216                    text: words[start..end].join(" "),
2217                    headings: (!section.heading_path.is_empty())
2218                        .then(|| section.heading_path.clone()),
2219                    doc_items: Vec::new(),
2220                };
2221                if !sink(chunk) {
2222                    return false;
2223                }
2224                if end >= words.len() {
2225                    return true;
2226                }
2227                start += step;
2228            }
2229        }
2230
2231        /// Render a window chunk for embedding — docling-rag's rendering: the
2232        /// heading path as a `# Outer > Inner` context line, a blank line,
2233        /// then the body (just the body above any heading). Note this differs
2234        /// from the docling chunkers' [`contextualize`](super::contextualize),
2235        /// matching docling-rag instead.
2236        pub fn contextualize(chunk: &DocChunk) -> String {
2237            match &chunk.headings {
2238                Some(h) if !h.is_empty() => format!("# {}\n\n{}", h.join(" > "), chunk.text),
2239                _ => chunk.text.clone(),
2240            }
2241        }
2242    }
2243
2244    #[cfg(test)]
2245    mod tests {
2246        use super::*;
2247
2248        #[test]
2249        fn splits_on_headings_and_tracks_path() {
2250            let md = "\
2251intro words
2252# Chapter 1
2253para one
2254## Section 1.1
2255para two
2256# Chapter 2
2257para three";
2258            let secs = parse_sections(md);
2259            // pre-heading intro, Chapter 1, Section 1.1, Chapter 2.
2260            assert_eq!(secs.len(), 4);
2261            assert!(secs[0].heading_path.is_empty());
2262            assert_eq!(secs[1].heading_path, vec!["Chapter 1"]);
2263            assert_eq!(secs[2].heading_path, vec!["Chapter 1", "Section 1.1"]);
2264            // A deeper heading is dropped when we return to H1.
2265            assert_eq!(secs[3].heading_path, vec!["Chapter 2"]);
2266        }
2267
2268        #[test]
2269        fn strips_markup_to_plain_words() {
2270            let md = "# T\n\nSome **bold** and `code` and [a link](http://x).";
2271            let secs = parse_sections(md);
2272            let words = &secs[0].words;
2273            assert!(words.contains(&"bold".to_string()));
2274            assert!(words.contains(&"code".to_string()));
2275            assert!(words.contains(&"link".to_string()));
2276            // No markdown punctuation survives as its own token.
2277            assert!(!words.iter().any(|w| w.contains('*') || w.contains('`')));
2278        }
2279
2280        #[test]
2281        fn windows_overlap_and_never_cross_headings() {
2282            let body: Vec<String> = (0..25).map(|i| format!("w{i}")).collect();
2283            let md = format!("# A\n\n{}\n\n# B\n\nshort tail\n", body.join(" "));
2284            let chunker = WindowChunker::new(10, 0.2); // step 8, overlap 2
2285            let chunks = chunker.chunk(&md);
2286            // Section A: 25 words → windows [0..10), [8..18), [16..25).
2287            let a: Vec<_> = chunks
2288                .iter()
2289                .filter(|c| c.headings.as_deref() == Some(&["A".to_string()][..]))
2290                .collect();
2291            assert_eq!(a.len(), 3);
2292            assert!(a[0].text.starts_with("w0 ") && a[0].text.ends_with(" w9"));
2293            assert!(a[1].text.starts_with("w8 "), "overlap carries 2 words");
2294            assert!(a[2].text.ends_with(" w24"));
2295            // Section B stays its own chunk; nothing crosses the heading.
2296            let b: Vec<_> = chunks
2297                .iter()
2298                .filter(|c| c.headings.as_deref() == Some(&["B".to_string()][..]))
2299                .collect();
2300            assert_eq!(b.len(), 1);
2301            assert_eq!(b[0].text, "short tail");
2302            assert_eq!(WindowChunker::contextualize(b[0]), "# B\n\nshort tail");
2303        }
2304
2305        #[test]
2306        fn sink_false_cancels_the_window_walk() {
2307            let md = format!(
2308                "# A\n\n{}\n",
2309                (0..50)
2310                    .map(|i| format!("w{i}"))
2311                    .collect::<Vec<_>>()
2312                    .join(" ")
2313            );
2314            let chunker = WindowChunker::new(10, 0.0);
2315            let mut n = 0;
2316            chunker.chunk_with(&md, &mut |_| {
2317                n += 1;
2318                false
2319            });
2320            assert_eq!(n, 1);
2321        }
2322    }
2323}
2324
2325#[cfg(feature = "chunking")]
2326pub use window::{parse_sections, parse_sections_with_stack, Section, WindowChunker};
2327
2328#[cfg(test)]
2329mod tests {
2330    use super::*;
2331
2332    /// A whitespace "tokenizer" for algorithm tests.
2333    struct WordTok(usize);
2334    impl ChunkTokenizer for WordTok {
2335        fn count_tokens(&self, text: &str) -> usize {
2336            text.split_whitespace().count()
2337        }
2338        fn max_tokens(&self) -> usize {
2339            self.0
2340        }
2341    }
2342
2343    fn doc_with(nodes: Vec<Node>) -> DoclingDocument {
2344        let mut d = DoclingDocument::new("t");
2345        for n in nodes {
2346            d.push(n);
2347        }
2348        d
2349    }
2350
2351    #[test]
2352    fn hierarchical_headings_and_items() {
2353        let doc = doc_with(vec![
2354            Node::Heading {
2355                level: 1,
2356                text: "Title".into(),
2357            },
2358            Node::Paragraph {
2359                text: "Intro".into(),
2360            },
2361            Node::Heading {
2362                level: 2,
2363                text: "Sec".into(),
2364            },
2365            Node::Paragraph {
2366                text: "Body".into(),
2367            },
2368        ]);
2369        let chunks = HierarchicalChunker.chunk(&doc);
2370        assert_eq!(chunks.len(), 2);
2371        assert_eq!(chunks[0].text, "Intro");
2372        assert_eq!(chunks[0].headings.as_deref(), Some(&["Title".into()][..]));
2373        assert_eq!(chunks[0].doc_items[0].self_ref, "#/texts/1");
2374        assert_eq!(
2375            chunks[1].headings.as_deref(),
2376            Some(&["Title".into(), "Sec".into()][..])
2377        );
2378        assert_eq!(contextualize(&chunks[1]), "Title\nSec\nBody");
2379    }
2380
2381    /// A page footer is a JSON text item (furniture layer) the chunker never
2382    /// chunks; the refs of the items after it still match the JSON.
2383    #[test]
2384    fn page_furniture_keeps_refs_aligned_with_json() {
2385        let doc = doc_with(vec![
2386            Node::Paragraph {
2387                text: "Before".into(),
2388            },
2389            Node::PageFurniture {
2390                footer: true,
2391                location: [0, 490, 100, 512],
2392                text: "1.10.2".into(),
2393            },
2394            Node::Paragraph {
2395                text: "After".into(),
2396            },
2397        ]);
2398        let chunks = HierarchicalChunker.chunk(&doc);
2399        assert_eq!(chunks.len(), 2);
2400        assert_eq!(chunks[1].text, "After");
2401        let json: serde_json::Value = serde_json::from_str(&doc.export_to_json()).unwrap();
2402        assert_eq!(json["texts"][2]["text"], "After");
2403        assert_eq!(chunks[1].doc_items[0].self_ref, "#/texts/2");
2404    }
2405
2406    /// A picture's children are never chunked, but they take `#/texts/N`
2407    /// (and list-group) slots in the JSON — the refs after them must still
2408    /// point at the right items.
2409    #[test]
2410    fn picture_children_are_not_chunked_but_keep_refs_aligned() {
2411        let doc = doc_with(vec![
2412            Node::Picture {
2413                caption: None,
2414                caption_href: None,
2415                image: None,
2416                classification: None,
2417                description: None,
2418                caption_parent: crate::CaptionParent::Item,
2419                caption_location: None,
2420            },
2421            Node::PictureChildren(vec![
2422                Node::Paragraph {
2423                    text: "axis label".into(),
2424                },
2425                Node::ListItem {
2426                    ordered: false,
2427                    number: 0,
2428                    first_in_list: true,
2429                    text: "callout".into(),
2430                    level: 0,
2431                    marker: None,
2432                    location: None,
2433                    dclx: None,
2434                    href: None,
2435                    layer: None,
2436                },
2437            ]),
2438            Node::Paragraph {
2439                text: "Body".into(),
2440            },
2441        ]);
2442        let chunks = HierarchicalChunker.chunk(&doc);
2443        assert_eq!(chunks.len(), 1);
2444        assert_eq!(chunks[0].text, "Body");
2445        let json = doc.export_to_json_value();
2446        assert_eq!(json["texts"][2]["text"], "Body");
2447        assert_eq!(chunks[0].doc_items[0].self_ref, "#/texts/2");
2448    }
2449
2450    #[test]
2451    fn heading_shadowing_prunes_deeper_levels() {
2452        let doc = doc_with(vec![
2453            Node::Heading {
2454                level: 2,
2455                text: "A".into(),
2456            },
2457            Node::Heading {
2458                level: 3,
2459                text: "A.1".into(),
2460            },
2461            Node::Heading {
2462                level: 2,
2463                text: "B".into(),
2464            },
2465            Node::Paragraph { text: "p".into() },
2466        ]);
2467        let chunks = HierarchicalChunker.chunk(&doc);
2468        assert_eq!(chunks[0].headings.as_deref(), Some(&["B".into()][..]));
2469    }
2470
2471    /// docling.rs#987 (docling-core#690): table pieces are budgeted at the
2472    /// window minus the heading path, so `contextualize()` stays in budget.
2473    #[test]
2474    fn split_table_pieces_fit_with_headings() {
2475        let rows: Vec<Vec<String>> = std::iter::once(vec!["".to_string(), "A".into(), "B".into()])
2476            .chain((0..40).map(|i| vec![format!("R{i}"), format!("{i}"), format!("v{i}")]))
2477            .collect();
2478        let doc = doc_with(vec![
2479            Node::Heading {
2480                level: 1,
2481                text: "one two three four five six".into(),
2482            },
2483            Node::Table(Table {
2484                rows,
2485                ..Default::default()
2486            }),
2487        ]);
2488        let h = HybridChunker::new(WordTok(20));
2489        let chunks = h.chunk(&doc);
2490        assert!(chunks.len() > 1);
2491        for c in &chunks {
2492            assert!(
2493                h.count_chunk_tokens(c) <= 20,
2494                "over budget: {}",
2495                h.count_chunk_tokens(c)
2496            );
2497        }
2498    }
2499
2500    #[test]
2501    fn triplet_table() {
2502        let t = Table {
2503            rows: vec![
2504                vec!["".into(), "Col1".into()],
2505                vec!["Row1".into(), "v".into()],
2506            ],
2507            ..Default::default()
2508        };
2509        assert_eq!(triplet_table_text(&t), "Row1, Col1 = v");
2510        // Single-column: row 0 is the dataframe header, the first data row
2511        // becomes the column name, the rest the values.
2512        let single = Table {
2513            rows: vec![vec!["H".into()], vec!["a".into()], vec!["b".into()]],
2514            ..Default::default()
2515        };
2516        assert_eq!(triplet_table_text(&single), "a = b");
2517    }
2518
2519    /// The peer merge before docling-core#823 (#782): rebuild and re-count
2520    /// the whole window for every chunk. The linear merge must give the
2521    /// same chunks.
2522    fn quadratic_merge<T: ChunkTokenizer>(
2523        h: &HybridChunker<T>,
2524        chunks: Vec<DocChunk>,
2525    ) -> Vec<DocChunk> {
2526        let mut out = Vec::new();
2527        let mut window: Vec<DocChunk> = Vec::new();
2528        let flush = |window: &mut Vec<DocChunk>, out: &mut Vec<DocChunk>| match window.len() {
2529            0 => {}
2530            1 => out.push(window.pop().unwrap()),
2531            _ => {
2532                out.push(merged_chunk(window.iter()));
2533                window.clear();
2534            }
2535        };
2536        for chunk in chunks {
2537            if window.is_empty() {
2538                window.push(chunk);
2539                continue;
2540            }
2541            let candidate = merged_chunk(window.iter().chain([&chunk]));
2542            if chunk.headings == window[0].headings
2543                && h.count_chunk_tokens(&candidate) <= h.max_tokens()
2544            {
2545                window.push(chunk);
2546            } else {
2547                flush(&mut window, &mut out);
2548                window.push(chunk);
2549            }
2550        }
2551        flush(&mut window, &mut out);
2552        out
2553    }
2554
2555    fn linear_merge<T: ChunkTokenizer>(
2556        h: &HybridChunker<T>,
2557        chunks: Vec<DocChunk>,
2558    ) -> Vec<DocChunk> {
2559        let mut out = Vec::new();
2560        let mut sink = |c| {
2561            out.push(c);
2562            true
2563        };
2564        let mut m = PeerMerger::default();
2565        for c in chunks {
2566            assert!(h.merge_push(&mut m, c, &mut sink));
2567        }
2568        assert!(h.merge_flush(&mut m, &mut sink));
2569        out
2570    }
2571
2572    /// A non-additive "tokenizer": a token per started 4 characters, so the
2573    /// joined text counts differently from the sum of its parts and the
2574    /// delimiter's measured cost is negative — the running estimate is
2575    /// re-anchored and the final window shrunk back.
2576    struct QuadCharTok(usize);
2577    impl ChunkTokenizer for QuadCharTok {
2578        fn count_tokens(&self, text: &str) -> usize {
2579            text.chars().count().div_ceil(4)
2580        }
2581        fn max_tokens(&self) -> usize {
2582            self.0
2583        }
2584    }
2585
2586    /// Pseudo-random chunks: short texts of 1–12 words under one of three
2587    /// heading paths (runs of equal headings, as the walk yields them).
2588    fn random_chunks(seed: u64, n: usize) -> Vec<DocChunk> {
2589        let mut state = seed;
2590        let mut next = move |m: u64| {
2591            state = state
2592                .wrapping_mul(6364136223846793005)
2593                .wrapping_add(1442695040888963407);
2594            (state >> 33) % m
2595        };
2596        let headings = [
2597            None,
2598            Some(vec!["A".to_string()]),
2599            Some(vec!["A".into(), "B".into()]),
2600        ];
2601        let mut current = 0;
2602        (0..n)
2603            .map(|i| {
2604                if next(4) == 0 {
2605                    current = next(3) as usize;
2606                }
2607                let words = 1 + next(12) as usize;
2608                let text = (0..words)
2609                    .map(|w| ["x", "lorem", "ipsum", "dolor", "sit"][(w + i) % 5])
2610                    .collect::<Vec<_>>()
2611                    .join(" ");
2612                DocChunk {
2613                    text,
2614                    headings: headings[current].clone(),
2615                    doc_items: vec![ChunkItem {
2616                        self_ref: format!("#/texts/{i}"),
2617                        kind: ChunkItemKind::Text,
2618                        text: String::new(),
2619                    }],
2620                }
2621            })
2622            .collect()
2623    }
2624
2625    /// #782 (docling-core#823): the linear peer merge gives exactly the
2626    /// chunks of the quadratic one, with an additive and a non-additive
2627    /// tokenizer, over many budgets.
2628    #[test]
2629    fn linear_peer_merge_matches_the_quadratic_one() {
2630        for seed in 0..40 {
2631            let chunks = random_chunks(seed, 60);
2632            for max in [3, 8, 16, 40, 200] {
2633                let h = HybridChunker::new(WordTok(max));
2634                assert_eq!(
2635                    linear_merge(&h, chunks.clone()),
2636                    quadratic_merge(&h, chunks.clone()),
2637                    "words, seed {seed}, max {max}"
2638                );
2639                let h = HybridChunker::new(QuadCharTok(max));
2640                assert_eq!(
2641                    linear_merge(&h, chunks.clone()),
2642                    quadratic_merge(&h, chunks.clone()),
2643                    "chars/4, seed {seed}, max {max}"
2644                );
2645            }
2646        }
2647    }
2648
2649    /// 10k tiny paragraphs at an 8192-token budget — docling-core#823's
2650    /// benchmark. `cargo test -p docling-core --release -- --ignored
2651    /// peer_merge_bench --nocapture` prints both timings.
2652    #[test]
2653    #[ignore]
2654    fn peer_merge_bench() {
2655        let chunks: Vec<DocChunk> = (0..10_000)
2656            .map(|i| DocChunk {
2657                text: format!("Paragraph number {i} is short."),
2658                headings: Some(vec!["Section".into()]),
2659                doc_items: Vec::new(),
2660            })
2661            .collect();
2662        let h = HybridChunker::new(WordTok(8192));
2663        let t = std::time::Instant::now();
2664        let fast = linear_merge(&h, chunks.clone());
2665        let linear = t.elapsed();
2666        let t = std::time::Instant::now();
2667        let slow = quadratic_merge(&h, chunks);
2668        let quadratic = t.elapsed();
2669        assert_eq!(fast, slow);
2670        println!(
2671            "linear {linear:?}, quadratic {quadratic:?}, {} chunks",
2672            fast.len()
2673        );
2674    }
2675
2676    /// A table from first-class cells `(text, row, col, row_span,
2677    /// column_header)`, its grid repeating a spanning cell's text.
2678    fn cell_table(
2679        num_rows: usize,
2680        num_cols: usize,
2681        cells: &[(&str, usize, usize, usize, bool)],
2682    ) -> Table {
2683        let mut rows = vec![vec![String::new(); num_cols]; num_rows];
2684        for &(text, r, c, span, _) in cells {
2685            for row in rows.iter_mut().skip(r).take(span) {
2686                row[c] = text.into();
2687            }
2688        }
2689        Table {
2690            rows,
2691            cells: Some(
2692                cells
2693                    .iter()
2694                    .map(|&(text, r, c, span, ched)| crate::TableCell {
2695                        text: text.into(),
2696                        bbox: None,
2697                        start_row: r,
2698                        start_col: c,
2699                        row_span: span,
2700                        col_span: 1,
2701                        column_header: ched,
2702                        row_header: false,
2703                        row_section: false,
2704                    })
2705                    .collect(),
2706            ),
2707            ..Default::default()
2708        }
2709    }
2710
2711    /// #778 (docling-core#767, 2.102): the Markdown table and the triplet
2712    /// chunk agree on the header rows — upstream's parametrized
2713    /// `test_table_header_rows_in_markdown_and_dataframe`, plus the issue's
2714    /// two tables. Expected texts are docling-core 2.102.0's (compact
2715    /// Markdown, `HierarchicalChunker` chunk text).
2716    #[test]
2717    fn markdown_and_triplets_share_the_header_rows() {
2718        type Case<'a> = (
2719            &'a str,
2720            usize,
2721            usize,
2722            Vec<(&'a str, usize, usize, usize, bool)>,
2723            &'a str,
2724            &'a str,
2725        );
2726        let cases: Vec<Case> = vec![
2727            (
2728                "rows under a row-spanning header stay in the body",
2729                2,
2730                2,
2731                vec![("Price", 0, 0, 1, true), ("Category", 0, 1, 2, true), ("10.00", 1, 0, 1, false)],
2732                "| Price | Category |\n| - | - |\n| 10.00 | Category |",
2733                "10.00, Category = Category",
2734            ),
2735            (
2736                "a row header flagged as column header stays in the body",
2737                3,
2738                3,
2739                vec![
2740                    ("Year", 0, 0, 1, true),
2741                    ("Month", 0, 1, 1, true),
2742                    ("Revenue", 0, 2, 1, true),
2743                    ("2025", 1, 0, 2, true),
2744                    ("January", 1, 1, 1, false),
2745                    ("$134", 1, 2, 1, false),
2746                    ("February", 2, 1, 1, false),
2747                    ("$150", 2, 2, 1, false),
2748                ],
2749                "| Year | Month | Revenue |\n| - | - | - |\n| 2025 | January | $134 |\n| 2025 | February | $150 |",
2750                "2025, Month = January. 2025, Revenue = $134. 2025, Month = February. 2025, Revenue = $150",
2751            ),
2752            (
2753                "stacked header with an unmarked row label",
2754                3,
2755                3,
2756                vec![
2757                    ("", 0, 0, 1, true),
2758                    ("% of Total", 0, 1, 1, true),
2759                    ("% of Total", 0, 2, 1, true),
2760                    ("class label", 1, 0, 1, false),
2761                    ("Train", 1, 1, 1, true),
2762                    ("Test", 1, 2, 1, true),
2763                    ("Caption", 2, 0, 1, false),
2764                    ("2.5", 2, 1, 1, false),
2765                    ("2.4", 2, 2, 1, false),
2766                ],
2767                "| class label | % of Total - Train | % of Total - Test |\n| - | - | - |\n| Caption | 2.5 | 2.4 |",
2768                "Caption, % of Total.Train = 2.5. Caption, % of Total.Test = 2.4",
2769            ),
2770            (
2771                "a partially flagged first row stays the header",
2772                2,
2773                2,
2774                vec![("Name", 0, 0, 1, true), ("Value", 0, 1, 1, false), ("A", 1, 0, 1, false), ("1", 1, 1, 1, false)],
2775                "| Name | Value |\n| - | - |\n| A | 1 |",
2776                "A, Value = 1",
2777            ),
2778            (
2779                "no flags: Markdown promotes row 0, triplets do not",
2780                2,
2781                2,
2782                vec![("Name", 0, 0, 1, false), ("Value", 0, 1, 1, false), ("A", 1, 0, 1, false), ("1", 1, 1, 1, false)],
2783                "| Name | Value |\n| - | - |\n| A | 1 |",
2784                "Name, 1 = Value. A, 1 = 1",
2785            ),
2786            (
2787                "row headers flagged as column headers stay in the body",
2788                2,
2789                2,
2790                vec![("2025", 0, 0, 1, true), ("$134", 0, 1, 1, false), ("2026", 1, 0, 1, true), ("$150", 1, 1, 1, false)],
2791                "|  |  |\n| - | - |\n| 2025 | $134 |\n| 2026 | $150 |",
2792                "2025, 1 = $134. 2026, 1 = $150",
2793            ),
2794            (
2795                "a form with flagged first-column labels is all data",
2796                3,
2797                2,
2798                vec![
2799                    ("Name", 0, 0, 1, true),
2800                    ("Bob", 0, 1, 1, false),
2801                    ("Age", 1, 0, 1, true),
2802                    ("42", 1, 1, 1, false),
2803                    ("City", 2, 0, 1, true),
2804                    ("Paris", 2, 1, 1, false),
2805                ],
2806                "|  |  |\n| - | - |\n| Name | Bob |\n| Age | 42 |\n| City | Paris |",
2807                "Name, 1 = Bob. Age, 1 = 42. City, 1 = Paris",
2808            ),
2809            (
2810                "a partly flagged row 0 above a stacked header row",
2811                3,
2812                3,
2813                vec![
2814                    ("Region", 0, 0, 1, true),
2815                    ("2025", 0, 1, 1, false),
2816                    ("", 0, 2, 1, false),
2817                    ("", 1, 0, 1, false),
2818                    ("Q1", 1, 1, 1, true),
2819                    ("Q2", 1, 2, 1, true),
2820                    ("North", 2, 0, 1, false),
2821                    ("1", 2, 1, 1, false),
2822                    ("2", 2, 2, 1, false),
2823                ],
2824                "| Region | 2025 - Q1 | Q2 |\n| - | - | - |\n| North | 1 | 2 |",
2825                "North, 2025.Q1 = 1. North, Q2 = 2",
2826            ),
2827        ];
2828        for (name, rows, cols, cells, md, triplets) in cases {
2829            let t = cell_table(rows, cols, &cells);
2830            assert_eq!(
2831                crate::markdown::render_table(&t, true),
2832                md,
2833                "{name}: markdown"
2834            );
2835            assert_eq!(triplet_table_text(&t), triplets, "{name}: triplets");
2836        }
2837    }
2838
2839    /// #777 (docling-core#857, 2.102): a rich header cell spanning two
2840    /// columns repeats in both — upstream's `col_span_rich_table_doc`. Its
2841    /// blocks sit on the anchor only and the covered position's flat text is
2842    /// blank, so LaTeX and the triplets must resolve the anchor themselves.
2843    #[test]
2844    fn a_column_spanning_rich_cell_repeats_in_every_column() {
2845        let mut t = cell_table(
2846            2,
2847            3,
2848            &[
2849                ("", 0, 0, 1, true),
2850                ("Partner", 0, 1, 1, true),
2851                ("Status", 1, 0, 1, false),
2852                ("Done", 1, 1, 1, false),
2853                ("Open", 1, 2, 1, false),
2854            ],
2855        );
2856        if let Some(cells) = t.cells.as_mut() {
2857            cells[1].col_span = 2;
2858        }
2859        let mut blocks = vec![vec![Vec::new(); 3]; 2];
2860        blocks[0][1] = vec![Node::Paragraph {
2861            text: "Partner".into(),
2862        }];
2863        t.cell_blocks = Some(blocks);
2864        assert_eq!(
2865            t.rows[0][2], "",
2866            "the covered position carries no text of its own"
2867        );
2868        assert_eq!(
2869            triplet_table_text(&t),
2870            "Status, Partner = Done. Status, Partner = Open"
2871        );
2872        let latex = crate::latex::render_table(&t);
2873        assert!(
2874            latex.contains(" & Partner & Partner \\\\ \\hline\nStatus & Done & Open \\\\ \\hline"),
2875            "{latex}"
2876        );
2877        // Markdown reads the flat text, which the backends now fill.
2878        t.rows[0][2] = "Partner".into();
2879        assert_eq!(
2880            crate::markdown::render_table(&t, true),
2881            "|  | Partner | Partner |\n| - | - | - |\n| Status | Done | Open |"
2882        );
2883    }
2884
2885    #[test]
2886    fn hybrid_merges_small_peers_and_splits_large() {
2887        let doc = doc_with(vec![
2888            Node::Heading {
2889                level: 2,
2890                text: "S".into(),
2891            },
2892            Node::Paragraph { text: "a b".into() },
2893            Node::Paragraph { text: "c d".into() },
2894        ]);
2895        let chunks = HybridChunker::new(WordTok(16)).chunk(&doc);
2896        assert_eq!(chunks.len(), 1, "peers under one heading merge");
2897        assert_eq!(chunks[0].text, "a b\nc d");
2898
2899        let long = "w ".repeat(40).trim().to_string();
2900        let doc = doc_with(vec![Node::Paragraph { text: long }]);
2901        let chunks = HybridChunker::new(WordTok(16)).chunk(&doc);
2902        assert!(chunks.len() > 1, "oversized paragraph splits");
2903        for c in &chunks {
2904            assert!(WordTok(16).count_tokens(&contextualize(c)) <= 16);
2905        }
2906    }
2907
2908    #[test]
2909    fn semchunk_prefers_newlines_then_sentences() {
2910        let tok = WordTok(4);
2911        let out = semchunk("one two three. four five six\nseven eight", 4, &tok);
2912        assert!(out.iter().all(|c| tok.count_tokens(c) <= 4), "{out:?}");
2913    }
2914}