Skip to main content

docling_core/
chunker.rs

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