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