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