docling_core/tree.rs
1//! docling's **item tree**, for a backend that knows the exact shape upstream
2//! gives a document and wants the JSON export to reproduce it.
3//!
4//! [`DoclingDocument::nodes`](crate::DoclingDocument::nodes) is a flat,
5//! reading-order stream tuned for Markdown / DocLang / LaTeX; the JSON export
6//! rebuilds docling's parent/child structure from it with generic rules (runs
7//! of list items become list groups, a heading is a flat sibling of the text
8//! that follows it). Upstream's backends do not all agree on that structure:
9//! the HTML backend nests everything after a heading *under* the heading,
10//! splits a paragraph of mixed formatting into an `inline` group of one text
11//! item per formatting run, parents a rich table cell's content to a group
12//! under the table, keeps site chrome on the `furniture` layer… and numbers
13//! every item in the order it *creates* them. A backend that ports those
14//! rules call-for-call (HTML's `html_tree.rs`, DOCX's `docx_tree.rs`) records
15//! the result here — an arena of items in
16//! creation order, each with its parent and children — and the JSON export
17//! ([`DoclingDocument::export_to_json`](crate::DoclingDocument::export_to_json))
18//! serializes this tree instead of deriving one from the nodes. Every other
19//! serializer keeps reading the flat nodes, so their output is unaffected.
20
21use crate::{ContentLayer, FieldItem, PictureImage, Script, Table};
22
23/// docling-core's `Formatting`: the inline styles an item carries in JSON.
24#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
25pub struct Formatting {
26 pub bold: bool,
27 pub italic: bool,
28 pub underline: bool,
29 pub strikethrough: bool,
30 pub script: Script,
31}
32
33/// A `list_item`'s docling fields.
34#[derive(Debug, Clone, PartialEq, Eq, Default)]
35pub struct ListMeta {
36 pub enumerated: bool,
37 /// docling's `marker` — the HTML backend writes `""` unless an ordered
38 /// list carries an explicit `start`, then `"{n}."`.
39 pub marker: String,
40}
41
42/// What an item in the tree is. Mirrors the docling-core item classes the
43/// JSON `texts` / `groups` / `tables` / `pictures` / `field_regions` buckets
44/// hold.
45#[derive(Debug, Clone, PartialEq)]
46pub enum TreeKind {
47 /// A `TextItem` / `TitleItem` / `SectionHeaderItem` / `ListItem`, told
48 /// apart by `label` (`text`, `title`, `section_header`, `list_item`,
49 /// `caption`, `checkbox_selected`, `checkbox_unselected`, …).
50 Text {
51 label: String,
52 text: String,
53 /// docling's `orig` when it differs from `text` (the heading text
54 /// before unicode cleanup, say); `None` = same as `text`.
55 orig: Option<String>,
56 formatting: Option<Formatting>,
57 hyperlink: Option<String>,
58 /// `section_header` only: docling's heading level.
59 level: Option<u8>,
60 /// `list_item` only.
61 list: Option<ListMeta>,
62 },
63 /// A `CodeItem`.
64 Code {
65 text: String,
66 orig: Option<String>,
67 /// The language hint (a highlighter class token such as `python`),
68 /// mapped onto docling's `CodeLanguageLabel` at export; `None` →
69 /// `unknown`.
70 language: Option<String>,
71 formatting: Option<Formatting>,
72 hyperlink: Option<String>,
73 /// Caption text items in the tree — docling's `add_code(caption=…)`
74 /// (an AsciiDoc block title in front of a literal block).
75 captions: Vec<usize>,
76 },
77 /// A `GroupItem`: `label` is docling's `GroupLabel` value (`inline`,
78 /// `list`, `section`, `unspecified`, …), `name` its name (`group`, `list`,
79 /// `ordered list`, `header-2`, `rich_cell_group_1_0_3`, …).
80 Group { label: String, name: String },
81 /// A `TableItem`. `rich_cells` marks the cells docling serialized as a
82 /// `RichTableCell`: `(row, col)` grid anchor → the group item (a child of
83 /// the table) that holds the cell's content. `captions` are caption text
84 /// items in the tree.
85 Table {
86 table: Table,
87 rich_cells: Vec<(usize, usize, usize)>,
88 captions: Vec<usize>,
89 },
90 /// A `PictureItem`, its caption text items and optional payload.
91 /// `classification` is a `PictureClassificationLabel` value written as
92 /// the picture's `meta.classification` (an HTML `<stamp>` / `<signature>`).
93 Picture {
94 captions: Vec<usize>,
95 image: Option<PictureImage>,
96 classification: Option<String>,
97 /// Further predictions after `classification`, in order: the other
98 /// plot types of a PPTX combination chart (docling#4773).
99 extra_classes: Vec<String>,
100 /// The picture-OCR enrichment's text (#645), serialized like the flat
101 /// node's: `meta.description` + the `description` annotation.
102 description: Option<crate::PictureDescription>,
103 /// The prediction's `confidence`, when the backend writes one: the
104 /// DocLang deserializer stamps `1.0`; the office and HTML backends
105 /// leave it out (`None`).
106 confidence: Option<f64>,
107 /// A native chart's data grid (docling's `meta.tabular_chart.chart_data`,
108 /// the series reconstructed as a `TableData`), for a DOCX chart drawing.
109 chart: Option<Table>,
110 /// The `ImageRef.dpi` docling writes for `image` when the backend
111 /// read one from the file (python-pptx's `Image.dpi`: PIL's `dpi`
112 /// info, rounded, 72 when absent or out of 1–2048); `None` → 72,
113 /// which is what upstream's other office backends pass.
114 dpi: Option<u32>,
115 },
116 /// A form key-value region (`field_regions` / `field_items`).
117 FieldRegion { items: Vec<FieldItem> },
118 /// A `KeyValueItem` (`key_value_items`): docling's `GraphData` of key and
119 /// value cells and their links, written verbatim.
120 KeyValueGraph {
121 cells: Vec<crate::GraphCell>,
122 links: Vec<crate::GraphLink>,
123 },
124}
125
126/// docling's `ProvenanceItem` for a tree item, written verbatim: the
127/// backend's own geometry in the page's units — a PPTX shape's EMU box,
128/// whose `pages` entry is the slide size in EMU — rather than the 0–511
129/// DocLang grid the flat [`Node::Located`](crate::Node::Located) carries
130/// (which cannot round-trip those integers).
131#[derive(Debug, Clone, PartialEq)]
132pub struct TreeProv {
133 /// 1-based page (slide) number.
134 pub page_no: usize,
135 /// `[l, t, r, b]`, exactly as docling computed them.
136 pub bbox: [f64; 4],
137 /// docling's `coord_origin` tag. The office backends tag their
138 /// top-left-based boxes `TOPLEFT` (the PPTX backend since docling#4294 —
139 /// it used to tag them `BOTTOMLEFT`, which read the tuple as `(l, b, r,
140 /// t)` and swapped the vertical edges); a backend that really works in a
141 /// bottom-left space sets this.
142 pub bottom_left: bool,
143 /// `[0, len(text)]` in characters for a text item, `[0, 0]` for a table
144 /// or picture.
145 pub charspan: [usize; 2],
146}
147
148/// docling's `TrackSource` — where in a time-based track (a WebVTT cue) a
149/// text item came from. Written as the item's `source: [{"kind": "track", …}]`.
150#[derive(Debug, Clone, PartialEq)]
151pub struct TreeTrack {
152 /// The cue's start offset in seconds (docling's `WebVTTTimestamp.seconds`:
153 /// `h*3600 + m*60 + s + millis/1000.0`, so the float is bit-identical).
154 pub start_time: f64,
155 /// The cue's end offset in seconds.
156 pub end_time: f64,
157 /// The cue identifier line, when the cue has one.
158 pub identifier: Option<String>,
159 /// The `<v …>` voice annotation the text sits in, when any.
160 pub voice: Option<String>,
161}
162
163/// One item of an [`ItemTree`].
164#[derive(Debug, Clone, PartialEq)]
165pub struct TreeItem {
166 /// The parent item's index; `None` = the document body.
167 pub parent: Option<usize>,
168 /// Child item indices, in docling's `children` order.
169 pub children: Vec<usize>,
170 /// The content layer; `None` = `body`.
171 pub layer: Option<ContentLayer>,
172 pub kind: TreeKind,
173 /// The item's `prov` entry, when the backend has page geometry for it
174 /// (`None` → `prov: []`, what the HTML and DOCX backends write).
175 pub prov: Option<TreeProv>,
176 /// docling's `DocItem.comments`: the `comment_section` groups (or note
177 /// text items) annotating this item, as item indices — written after
178 /// `prov` when non-empty.
179 pub comments: Vec<usize>,
180 /// docling's `DocItem.source`: the track segment a text item was taken
181 /// from (WebVTT cues) — written after `prov` when set.
182 pub source: Option<TreeTrack>,
183 /// Removed by [`ItemTree::delete`] (docling's `delete_items`): the slot
184 /// stays so every other index keeps its meaning, but the item is not
185 /// numbered or written.
186 pub deleted: bool,
187 /// Footnotes / endnotes referenced from inside this text item (#538): the
188 /// note call's position (chars into the item's text) and the note's text.
189 /// docling keeps notes as unlinked furniture `footnote` items, so the
190 /// JSON never shows this; the Pandoc AST writes each as a `Note` there.
191 pub notes: Vec<TreeNote>,
192 /// This furniture `footnote` item is the body of a note some text item
193 /// calls (it travels in that item's [`Self::notes`]); the Pandoc AST then
194 /// leaves it out as a standalone block.
195 pub note_body: bool,
196 /// Link destinations at this item (#849): the identifiers a document's
197 /// internal links (`hyperlink: "#id"`) point at — a DOCX bookmark in
198 /// a heading, say. docling's model has no slot for them, so the JSON
199 /// shows them only on the Pandoc path (`_anchors`), where a heading's
200 /// first one is its `Header` id and the rest empty `Span .anchor`s.
201 pub anchors: Vec<String>,
202 /// The generated numbering `text` opens with, when the backend put one
203 /// there (#850: a DOCX heading numbered through `w:numPr` is docling's
204 /// `1.2 Title`): `"1.2"` — the authored text follows it after one
205 /// space. docling's JSON keeps the numbered text; the Pandoc AST writes
206 /// the authored text alone (`_number` on that path), since Pandoc
207 /// numbers sections itself (`--number-sections`) and its docx reader
208 /// never writes the number into the `Header`.
209 pub number: Option<String>,
210 /// The tracked change this run carries under
211 /// [`TrackChanges::All`](crate::TrackChanges::All) (#851): the Pandoc
212 /// AST wraps the run in `Span .insertion` / `.deletion` (`_revision`
213 /// on that path); docling's JSON has no field for it.
214 pub revision: Option<crate::Revision>,
215 /// A picture's `meta.code` — docling's `CodeMetaField` (`text`,
216 /// `language`): the LaTeX backend keeps a `tikzpicture`'s source there
217 /// when no engine renders it (`("…", "Tikz")`).
218 pub code_meta: Option<(String, String)>,
219 /// The source block this item was made from (#903): an index into
220 /// [`ItemTree::blocks`], set by a backend that enumerates its source's
221 /// blocks (HTML). `None` when the backend does not, or for an item no
222 /// single block produced.
223 pub block: Option<usize>,
224}
225
226/// A block of the source document (#903, #904): the original element an
227/// item was made from — or one that produced no item, with the reason —
228/// so a caller can tie converted items back to the source, tell two
229/// identical texts apart, and read a block's text on its own terms, free of
230/// any serializer's separators.
231///
232/// The HTML backend enumerates, in document order, every element that
233/// produced an item, every non-inline element with text of its own (text
234/// nodes reached through inline elements only — a `<span>`'s text belongs
235/// to the block around it), and every empty `<p>`, heading, `<li>`, `<dt>`,
236/// `<dd>`, `<td>`/`<th>`, `<pre>` or `<caption>`. Pure containers (a layout
237/// `<div>` with nothing but blocks inside) are not blocks. Every text node
238/// of the source thus belongs to exactly one block.
239#[derive(Debug, Clone, PartialEq, Eq)]
240pub struct SourceBlock {
241 /// The element's tag name (`p`, `div`, `li`, `table`, `img`, …).
242 pub tag: String,
243 /// Its `id` attribute, when it has one.
244 pub id: Option<String>,
245 /// Its `class` attribute, as written.
246 pub class: Option<String>,
247 /// The element's path from the document root — each step the tag and
248 /// the 1-based position among the parent's same-tag element children,
249 /// `html/body/div[3]/p[1]` — stable for the document and unique to the
250 /// element, with or without an `id`.
251 pub path: String,
252 /// The block's own text: its text nodes (and those of the inline
253 /// elements inside it, not of nested blocks) in source order, whitespace
254 /// runs collapsed to one space, trimmed. Independent of what the items
255 /// made of it hold — a hidden block's text is here too.
256 pub text: String,
257 /// The items made from this block, in creation order — the top-level
258 /// ones (an inline group, not the runs inside it; a list group, not
259 /// its items, which have their `<li>` blocks). Empty when it produced
260 /// none: see `omitted`.
261 pub items: Vec<usize>,
262 /// Why no item was made from this block; `None` when `items` is not
263 /// empty.
264 pub omitted: Option<BlockOmission>,
265}
266
267/// Why a [`SourceBlock`] produced no item.
268#[derive(Debug, Clone, Copy, PartialEq, Eq)]
269pub enum BlockOmission {
270 /// No text of its own once normalized (an empty `<p>`, a `<li>` whose
271 /// content is nested blocks).
272 Empty,
273 /// Hidden or non-content (`display: none`, `hidden`, `<script>`,
274 /// `<style>`, `<noscript>`), or inside such an element.
275 Hidden,
276 /// In a table whose cells were flattened: the text is in the grid of
277 /// the table item (the index) rather than an item of its own.
278 InTable(usize),
279 /// Its text went into the items of an enclosing block (the index into
280 /// [`ItemTree::blocks`]): a `<p>` inside a `<li>` is the list item's
281 /// text.
282 Merged(usize),
283 /// The walk produced nothing the backend can attribute.
284 Unmapped,
285}
286
287/// A note call inside a text item ([`TreeItem::notes`]).
288#[derive(Debug, Clone, PartialEq, Eq)]
289pub struct TreeNote {
290 /// The call's position, in chars into the item's `text`.
291 pub offset: usize,
292 /// The note's plain text.
293 pub text: String,
294}
295
296impl ItemTree {
297 /// Where each note call of one paragraph lands (#538): `full_text` is the
298 /// paragraph's text, `offsets` the calls' positions in it (chars), and
299 /// the paragraph's items are those created from `first_new` on. Each text
300 /// item is a trimmed slice of the paragraph (a formatting run, a link, or
301 /// the whole heading / list item), matched in order; a call inside an
302 /// item lands there, one between items ends the earlier (or starts the
303 /// first). When no item matches, the call ends the paragraph's last text
304 /// item; with no text item at all it is `None`.
305 pub fn place_note_calls(
306 &self,
307 first_new: usize,
308 full_text: &str,
309 offsets: &[usize],
310 ) -> Vec<Option<(usize, usize)>> {
311 let texts: Vec<(usize, &str)> = (first_new..self.items.len())
312 .filter(|&i| !self.items[i].deleted)
313 .filter_map(|i| match &self.items[i].kind {
314 TreeKind::Text { text, .. } | TreeKind::Code { text, .. } => {
315 Some((i, text.as_str()))
316 }
317 _ => None,
318 })
319 .collect();
320 // Each found item's (id, start, end) in chars of `full_text`.
321 let mut spans: Vec<(usize, usize, usize)> = Vec::new();
322 let mut cursor = 0usize; // bytes
323 for &(item, text) in &texts {
324 if text.is_empty() {
325 continue;
326 }
327 if let Some(pos) = full_text[cursor..].find(text) {
328 let start_b = cursor + pos;
329 let start = full_text[..start_b].chars().count();
330 spans.push((item, start, start + text.chars().count()));
331 cursor = start_b + text.len();
332 }
333 }
334 offsets
335 .iter()
336 .map(|&offset| {
337 spans
338 .iter()
339 .find(|&&(_, start, end)| offset >= start && offset <= end)
340 .map(|&(item, start, _)| (item, offset - start))
341 .or_else(
342 || match spans.iter().rev().find(|&&(_, _, end)| end <= offset) {
343 Some(&(item, start, end)) => Some((item, end - start)),
344 None => spans.first().map(|&(item, _, _)| (item, 0)),
345 },
346 )
347 .or_else(|| {
348 texts
349 .last()
350 .map(|&(item, text)| (item, text.chars().count()))
351 })
352 })
353 .collect()
354 }
355}
356
357/// docling's item tree in creation order (see the [module docs](self)).
358#[derive(Debug, Clone, PartialEq, Default)]
359pub struct ItemTree {
360 /// Every item, indexed by creation order — which is how docling numbers
361 /// `#/texts/N`, `#/groups/N`, … within each bucket.
362 pub items: Vec<TreeItem>,
363 /// The body's `children`, as item indices.
364 pub body: Vec<usize>,
365 /// The DocLang export serializes this tree too (#884) — docling-core's
366 /// `DocLangDocSerializer` ported over the tree (`doclang_tree.rs`) —
367 /// instead of the flat nodes, which cannot carry a footnote's label, a
368 /// caption's or a cell's inline formulas, or text docling never wrote
369 /// as Markdown. Set by a backend whose tree is upstream's exact
370 /// structure (LaTeX); a tree the port does not cover falls back to the
371 /// nodes.
372 pub doclang: bool,
373 /// The source's blocks (#903), in document order, when the backend
374 /// enumerates them (HTML); each item's [`TreeItem::block`] points into
375 /// this. Empty otherwise.
376 pub blocks: Vec<SourceBlock>,
377}
378
379impl ItemTree {
380 /// Append an item under `parent` (`None` = body) on `layer`, registering
381 /// it as its parent's last child — docling's `add_*` calls do exactly that.
382 pub fn add(
383 &mut self,
384 parent: Option<usize>,
385 layer: Option<ContentLayer>,
386 kind: TreeKind,
387 ) -> usize {
388 let id = self.items.len();
389 self.items.push(TreeItem {
390 parent,
391 children: Vec::new(),
392 layer,
393 kind,
394 prov: None,
395 comments: Vec::new(),
396 source: None,
397 deleted: false,
398 notes: Vec::new(),
399 note_body: false,
400 anchors: Vec::new(),
401 number: None,
402 revision: None,
403 code_meta: None,
404 block: None,
405 });
406 match parent {
407 Some(p) => self.items[p].children.push(id),
408 None => self.body.push(id),
409 }
410 id
411 }
412
413 /// [`add`](Self::add) with the item's provenance — docling's
414 /// `add_text(…, prov=prov)`.
415 pub fn add_with_prov(
416 &mut self,
417 parent: Option<usize>,
418 layer: Option<ContentLayer>,
419 kind: TreeKind,
420 prov: TreeProv,
421 ) -> usize {
422 let id = self.add(parent, layer, kind);
423 self.items[id].prov = Some(prov);
424 id
425 }
426
427 /// The text of the given source blocks (#904), one line each: each
428 /// block's own normalized [`SourceBlock::text`], joined with a single
429 /// `\n` — no serializer decoration, no trailing separator, nothing of
430 /// the blocks around them. Indices out of range are skipped.
431 pub fn source_text(&self, blocks: impl IntoIterator<Item = usize>) -> String {
432 let mut out = String::new();
433 for b in blocks {
434 let Some(block) = self.blocks.get(b) else {
435 continue;
436 };
437 if !out.is_empty() {
438 out.push('\n');
439 }
440 out.push_str(&block.text);
441 }
442 out
443 }
444
445 /// Append every item of `other` after this tree's, renumbering its
446 /// indices (parents, children, comments, table/picture caption and
447 /// rich-cell refs) and adding its body children to this body — so a
448 /// backend can build independent fragments in parallel (one per PPTX
449 /// slide) and still hand the export one tree in creation order, exactly
450 /// as if it had been built sequentially.
451 pub fn append(&mut self, other: ItemTree) {
452 let off = self.items.len();
453 let shift = |i: usize| i + off;
454 for mut item in other.items {
455 item.parent = item.parent.map(shift);
456 for c in item.children.iter_mut().chain(item.comments.iter_mut()) {
457 *c = shift(*c);
458 }
459 match &mut item.kind {
460 TreeKind::Table {
461 rich_cells,
462 captions,
463 ..
464 } => {
465 for (_, _, g) in rich_cells.iter_mut() {
466 *g = shift(*g);
467 }
468 for c in captions.iter_mut() {
469 *c = shift(*c);
470 }
471 }
472 TreeKind::Picture { captions, .. } | TreeKind::Code { captions, .. } => {
473 for c in captions.iter_mut() {
474 *c = shift(*c);
475 }
476 }
477 _ => {}
478 }
479 self.items.push(item);
480 }
481 self.body.extend(other.body.into_iter().map(shift));
482 let block_off = self.blocks.len();
483 for mut b in other.blocks {
484 for i in b.items.iter_mut() {
485 *i = shift(*i);
486 }
487 if let Some(BlockOmission::InTable(t)) = b.omitted.as_mut() {
488 *t = shift(*t);
489 }
490 if let Some(BlockOmission::Merged(m)) = b.omitted.as_mut() {
491 *m += block_off;
492 }
493 self.blocks.push(b);
494 }
495 for item in &mut self.items[off..] {
496 if let Some(b) = item.block.as_mut() {
497 *b += block_off;
498 }
499 }
500 }
501
502 /// Move `id` under `new_parent`, dropping it from its current parent's
503 /// children and appending it to the new one's — docling's
504 /// `group_cell_elements` re-parenting of a rich cell's items.
505 pub fn reparent(&mut self, id: usize, new_parent: Option<usize>) {
506 let old = self.items[id].parent;
507 let siblings = match old {
508 Some(p) => &mut self.items[p].children,
509 None => &mut self.body,
510 };
511 siblings.retain(|&c| c != id);
512 self.items[id].parent = new_parent;
513 match new_parent {
514 Some(p) => self.items[p].children.push(id),
515 None => self.body.push(id),
516 }
517 }
518
519 /// Re-number the items in traversal order — a pre-order walk of the body
520 /// through every layer, which is how docling's
521 /// `DoclingDocument.concatenate` (and `_normalize_references`) re-creates
522 /// a document's items: a group created after the content it was later
523 /// wrapped around comes before that content afterwards. Items the walk
524 /// does not reach (deleted ones) are dropped. Returns each old id's new
525 /// id.
526 pub fn renumber_in_traversal_order(&mut self) -> Vec<Option<usize>> {
527 let mut order = Vec::with_capacity(self.items.len());
528 let mut stack: Vec<usize> = self.body.iter().rev().copied().collect();
529 while let Some(id) = stack.pop() {
530 if self.items[id].deleted {
531 continue;
532 }
533 order.push(id);
534 stack.extend(self.items[id].children.iter().rev());
535 }
536 let mut new_of: Vec<Option<usize>> = vec![None; self.items.len()];
537 for (new, &old) in order.iter().enumerate() {
538 new_of[old] = Some(new);
539 }
540 let remap = |ids: &mut Vec<usize>| {
541 *ids = ids.iter().filter_map(|&i| new_of[i]).collect();
542 };
543 let mut old_items: Vec<Option<TreeItem>> = std::mem::take(&mut self.items)
544 .into_iter()
545 .map(Some)
546 .collect();
547 for &old in &order {
548 let mut item = old_items[old].take().expect("each item visited once");
549 item.parent = item.parent.and_then(|p| new_of[p]);
550 remap(&mut item.children);
551 remap(&mut item.comments);
552 match &mut item.kind {
553 TreeKind::Table {
554 rich_cells,
555 captions,
556 ..
557 } => {
558 rich_cells.retain_mut(|(_, _, g)| match new_of[*g] {
559 Some(n) => {
560 *g = n;
561 true
562 }
563 None => false,
564 });
565 remap(captions);
566 }
567 TreeKind::Picture { captions, .. } | TreeKind::Code { captions, .. } => {
568 remap(captions)
569 }
570 _ => {}
571 }
572 self.items.push(item);
573 }
574 remap(&mut self.body);
575 for b in &mut self.blocks {
576 remap(&mut b.items);
577 if let Some(BlockOmission::InTable(t)) = b.omitted {
578 b.omitted = Some(match new_of[t] {
579 Some(n) => BlockOmission::InTable(n),
580 None => BlockOmission::Unmapped,
581 });
582 }
583 }
584 new_of
585 }
586
587 /// Remove `id` from the tree — docling's `delete_items`, which the DOCX
588 /// backend uses to drop the empty text item a blank spacer paragraph left
589 /// between two items of a resumed list. The item leaves its parent's
590 /// children and is neither numbered nor written; its slot stays so the
591 /// indices held elsewhere stay valid.
592 pub fn delete(&mut self, id: usize) {
593 match self.items[id].parent {
594 Some(p) => self.items[p].children.retain(|&c| c != id),
595 None => self.body.retain(|&c| c != id),
596 }
597 self.items[id].deleted = true;
598 }
599
600 /// docling-core's `DoclingDocument.validate_misplaced_list_items` (a
601 /// model validator, so it runs whenever docling-core serializes or loads
602 /// a document): every `list_item` whose parent is not a `list` group is
603 /// re-homed into a new one. A pre-order walk of the body (groups
604 /// included) collects them; consecutive misplaced items directly on the
605 /// body share one group, any other misplaced item gets its own. Working
606 /// from the last run back, each run gets a `ListGroup` (name `group`)
607 /// inserted where its first item stood, the items are deleted and
608 /// re-added under the group as fresh items, so they move to the end of
609 /// the text numbering (#527: the DOCX backend leaves such items in rich
610 /// table cells). A no-op for a well-formed tree.
611 ///
612 /// One deliberate divergence (#586): docling-core deletes each item *with
613 /// its children* and re-adds it from its text alone, so a mixed-format
614 /// item — an empty `list_item` over an `inline` group of text runs —
615 /// comes back empty and its text is gone from the JSON (and from the
616 /// Markdown/HTML docling serializes after that validator ran; the JSON
617 /// docling saves *before* exporting still has it). Here the children
618 /// follow the item into the group: the structure docling-core requires,
619 /// the content the document had.
620 pub fn wrap_misplaced_list_items(&mut self) {
621 let is_list_item = |t: &Self, id: usize| matches!(&t.items[id].kind, TreeKind::Text { label, .. } if label == "list_item");
622 let in_list_group = |t: &Self, id: usize| {
623 t.items[id].parent.is_some_and(
624 |p| matches!(&t.items[p].kind, TreeKind::Group { label, .. } if label == "list"),
625 )
626 };
627 let mut runs: Vec<Vec<usize>> = Vec::new();
628 // `None` = the body itself, which the walk yields first.
629 let mut prev: Option<usize> = None;
630 let mut stack: Vec<usize> = self.body.iter().rev().copied().collect();
631 while let Some(id) = stack.pop() {
632 if self.items[id].deleted {
633 continue;
634 }
635 if is_list_item(self, id) && !in_list_group(self, id) {
636 let continues =
637 prev.is_some_and(|p| is_list_item(self, p) && self.items[p].parent.is_none());
638 match runs.last_mut() {
639 Some(run) if continues => run.push(id),
640 _ => runs.push(vec![id]),
641 }
642 }
643 prev = Some(id);
644 stack.extend(self.items[id].children.iter().rev().copied());
645 }
646 for run in runs.into_iter().rev() {
647 let parent = self.items[run[0]].parent;
648 let group = self.add(
649 parent,
650 None,
651 TreeKind::Group {
652 label: "list".into(),
653 name: "group".into(),
654 },
655 );
656 let siblings = match parent {
657 Some(p) => &mut self.items[p].children,
658 None => &mut self.body,
659 };
660 siblings.pop();
661 let at = siblings
662 .iter()
663 .position(|&c| c == run[0])
664 .unwrap_or(siblings.len());
665 siblings.insert(at, group);
666 for &li in &run {
667 // Not `delete_subtree`: the children move to the copy (#586).
668 self.delete(li);
669 }
670 // `add_list_item` keeps the text, marker, formatting, hyperlink
671 // and first provenance — not comments or a source. The children
672 // (the inline group of a mixed-format item) are carried over.
673 for &li in &run {
674 let children = std::mem::take(&mut self.items[li].children);
675 let copy = TreeItem {
676 parent: Some(group),
677 children: children.clone(),
678 comments: Vec::new(),
679 source: None,
680 deleted: false,
681 ..self.items[li].clone()
682 };
683 let id = self.items.len();
684 self.items.push(copy);
685 for c in children {
686 self.items[c].parent = Some(id);
687 }
688 self.items[group].children.push(id);
689 }
690 }
691 }
692
693 /// The last live text-bucket item (docling's `doc.texts[-1]`).
694 pub fn last_text(&self) -> Option<usize> {
695 self.items.iter().rposition(|it| {
696 !it.deleted && matches!(it.kind, TreeKind::Text { .. } | TreeKind::Code { .. })
697 })
698 }
699
700 /// How many items of a bucket precede `id` — its `#/{bucket}/N` index.
701 pub fn bucket_index(&self, id: usize) -> usize {
702 let same = |k: &TreeKind| {
703 std::mem::discriminant(k) == std::mem::discriminant(&self.items[id].kind)
704 || matches!(
705 (k, &self.items[id].kind),
706 (TreeKind::Text { .. }, TreeKind::Code { .. })
707 | (TreeKind::Code { .. }, TreeKind::Text { .. })
708 )
709 };
710 self.items[..id]
711 .iter()
712 .filter(|it| !it.deleted && same(&it.kind))
713 .count()
714 }
715
716 /// The number of tables created so far (docling's `len(doc.tables)`).
717 pub fn table_count(&self) -> usize {
718 self.items
719 .iter()
720 .filter(|it| !it.deleted && matches!(it.kind, TreeKind::Table { .. }))
721 .count()
722 }
723}
724
725#[cfg(test)]
726mod tests {
727 use super::*;
728
729 fn text(t: &str) -> TreeKind {
730 TreeKind::Text {
731 label: "text".into(),
732 text: t.into(),
733 orig: None,
734 formatting: None,
735 hyperlink: None,
736 level: None,
737 list: None,
738 }
739 }
740
741 /// `add` registers the item as its parent's (or the body's) last child;
742 /// `reparent` moves it — a rich cell's items leave the heading they were
743 /// created under for the table's group.
744 #[test]
745 fn add_and_reparent_keep_docling_children_order() {
746 let mut t = ItemTree::default();
747 let title = t.add(None, None, text("Title"));
748 let a = t.add(Some(title), None, text("a"));
749 let b = t.add(Some(title), None, text("b"));
750 let table = t.add(
751 Some(title),
752 None,
753 TreeKind::Table {
754 table: Table::default(),
755 rich_cells: Vec::new(),
756 captions: Vec::new(),
757 },
758 );
759 let group = t.add(
760 Some(table),
761 None,
762 TreeKind::Group {
763 label: "unspecified".into(),
764 name: "rich_cell_group_1_0_0".into(),
765 },
766 );
767 assert_eq!(t.body, vec![title]);
768 assert_eq!(t.items[title].children, vec![a, b, table]);
769 t.reparent(a, Some(group));
770 assert_eq!(t.items[title].children, vec![b, table]);
771 assert_eq!(t.items[group].children, vec![a]);
772 assert_eq!(t.items[a].parent, Some(group));
773 assert_eq!(t.table_count(), 1);
774 // Text and code share the `texts` bucket.
775 let code = t.add(
776 None,
777 None,
778 TreeKind::Code {
779 text: "x".into(),
780 orig: None,
781 language: None,
782 formatting: None,
783 hyperlink: None,
784 captions: Vec::new(),
785 },
786 );
787 assert_eq!(t.bucket_index(code), 3, "title, a, b precede it in `texts`");
788 assert_eq!(t.bucket_index(group), 0);
789 assert_eq!(t.body, vec![title, code]);
790 }
791
792 /// `append` renumbers a fragment built on its own (a slide converted in
793 /// parallel) so the merged tree reads as if built in one pass: parents,
794 /// children, comment back-refs and caption refs all shift together.
795 #[test]
796 fn append_renumbers_a_fragment_into_creation_order() {
797 let mut whole = ItemTree::default();
798 let slide0 = whole.add(
799 None,
800 None,
801 TreeKind::Group {
802 label: "chapter".into(),
803 name: "slide-0".into(),
804 },
805 );
806 whole.add(Some(slide0), None, text("first"));
807
808 let mut frag = ItemTree::default();
809 let slide1 = frag.add(
810 None,
811 None,
812 TreeKind::Group {
813 label: "chapter".into(),
814 name: "slide-1".into(),
815 },
816 );
817 let cap = frag.add_with_prov(
818 Some(slide1),
819 None,
820 TreeKind::Text {
821 label: "caption".into(),
822 text: "Title".into(),
823 orig: None,
824 formatting: None,
825 hyperlink: None,
826 level: None,
827 list: None,
828 },
829 TreeProv {
830 page_no: 2,
831 bbox: [1.0, 2.0, 3.0, 4.0],
832 bottom_left: true,
833 charspan: [0, 5],
834 },
835 );
836 let pic = frag.add(
837 Some(slide1),
838 None,
839 TreeKind::Picture {
840 captions: vec![cap],
841 image: None,
842 extra_classes: Vec::new(),
843 classification: Some("bar_chart".into()),
844 description: None,
845 confidence: None,
846 chart: None,
847 dpi: None,
848 },
849 );
850 let note = frag.add(
851 None,
852 Some(ContentLayer::Notes),
853 TreeKind::Group {
854 label: "comment_section".into(),
855 name: "comment-slide2-1".into(),
856 },
857 );
858 frag.items[pic].comments.push(note);
859
860 whole.append(frag);
861 assert_eq!(whole.body, vec![slide0, 2, 5]);
862 assert_eq!(whole.items[2].children, vec![3, 4]);
863 assert_eq!(whole.items[3].parent, Some(2));
864 assert_eq!(whole.items[3].prov.as_ref().map(|p| p.page_no), Some(2));
865 assert!(
866 matches!(&whole.items[4].kind, TreeKind::Picture { captions, .. } if captions == &[3])
867 );
868 assert_eq!(whole.items[4].comments, vec![5]);
869 assert_eq!(whole.items[5].parent, None);
870 assert_eq!(
871 whole.bucket_index(4),
872 0,
873 "the fragment's picture is #/pictures/0"
874 );
875 assert_eq!(
876 whole.bucket_index(5),
877 2,
878 "slide-0, slide-1 precede it in `groups`"
879 );
880 }
881
882 /// `renumber_in_traversal_order`: docling's `concatenate` re-creates the
883 /// items as a pre-order walk meets them, so a group created after the
884 /// content it was wrapped around (a rich cell's group) comes first, and a
885 /// deleted item disappears; every cross-reference follows.
886 #[test]
887 fn renumbering_follows_the_traversal() {
888 let mut t = ItemTree::default();
889 let a = t.add(None, None, text("a"));
890 let table = t.add(
891 None,
892 None,
893 TreeKind::Table {
894 table: Table::default(),
895 rich_cells: Vec::new(),
896 captions: Vec::new(),
897 },
898 );
899 let cell_text = t.add(None, None, text("cell"));
900 let group = t.add(
901 Some(table),
902 None,
903 TreeKind::Group {
904 label: "unspecified".into(),
905 name: "rich_cell_group_1_0_0".into(),
906 },
907 );
908 t.reparent(cell_text, Some(group));
909 if let TreeKind::Table { rich_cells, .. } = &mut t.items[table].kind {
910 rich_cells.push((0, 0, group));
911 }
912 let gone = t.add(None, None, text("gone"));
913 t.delete(gone);
914 let z = t.add(None, None, text("z"));
915
916 let new_of = t.renumber_in_traversal_order();
917 assert_eq!(
918 new_of,
919 vec![Some(0), Some(1), Some(3), Some(2), None, Some(4)]
920 );
921 assert_eq!(t.items.len(), 5);
922 assert_eq!(t.body, vec![0, 1, 4]);
923 assert_eq!(t.items[1].children, vec![2], "the group follows its table");
924 assert_eq!(t.items[2].parent, Some(1));
925 assert_eq!(
926 t.items[3].parent,
927 Some(2),
928 "the cell text follows its group"
929 );
930 assert!(matches!(&t.items[3].kind, TreeKind::Text { text, .. } if text == "cell"));
931 assert!(
932 matches!(&t.items[1].kind, TreeKind::Table { rich_cells, .. } if rich_cells == &[(0, 0, 2)])
933 );
934 let _ = (a, z);
935 }
936
937 /// #586: a misplaced `list_item` keeps its children when it is re-homed.
938 /// docling-core's `validate_misplaced_list_items` re-adds the item from
939 /// its text alone, so a mixed-format item (empty `list_item` over an
940 /// `inline` group of runs) lost every run — a DOCX table cell whose list
941 /// paragraph followed a `numId 0` spacer came out as an empty bullet in
942 /// the JSON and the HTML. The group goes where the item stood, the copy
943 /// is numbered last, the inline group and its texts move under it.
944 #[test]
945 fn wrapping_a_misplaced_list_item_keeps_its_runs() {
946 let mut t = ItemTree::default();
947 let cell = t.add(
948 None,
949 None,
950 TreeKind::Group {
951 label: "unspecified".into(),
952 name: "rich_cell_group_1_0_1".into(),
953 },
954 );
955 let before = t.add(Some(cell), None, text("before"));
956 let item = t.add(
957 Some(cell),
958 None,
959 TreeKind::Text {
960 label: "list_item".into(),
961 text: String::new(),
962 orig: None,
963 formatting: None,
964 hyperlink: None,
965 level: None,
966 list: Some(ListMeta {
967 enumerated: false,
968 marker: String::new(),
969 }),
970 },
971 );
972 let inline = t.add(
973 Some(item),
974 None,
975 TreeKind::Group {
976 label: "inline".into(),
977 name: "group".into(),
978 },
979 );
980 let run_a = t.add(Some(inline), None, text("Second item text"));
981 let run_b = t.add(Some(inline), None, text("[Optional]"));
982 let after = t.add(Some(cell), None, text("after"));
983
984 t.wrap_misplaced_list_items();
985
986 let group = t.items[cell].children[1];
987 assert_eq!(t.items[cell].children, vec![before, group, after]);
988 assert!(
989 matches!(&t.items[group].kind, TreeKind::Group { label, name } if label == "list" && name == "group")
990 );
991 assert!(t.items[item].deleted, "the original item is deleted");
992 let copy = t.items[group].children[0];
993 assert_ne!(copy, item);
994 assert!(
995 copy > after,
996 "the copy is numbered after every existing item"
997 );
998 assert_eq!(t.items[copy].children, vec![inline]);
999 assert_eq!(t.items[inline].parent, Some(copy));
1000 assert_eq!(t.items[inline].children, vec![run_a, run_b]);
1001 for id in [inline, run_a, run_b] {
1002 assert!(!t.items[id].deleted, "item {id} must survive the re-homing");
1003 }
1004 }
1005}