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; `footnotes` its `footnote` text items (children of
85 /// the table, docling's `TableItem.footnotes`, docling-core#675).
86 Table {
87 table: Table,
88 rich_cells: Vec<(usize, usize, usize)>,
89 captions: Vec<usize>,
90 footnotes: Vec<usize>,
91 },
92 /// A `PictureItem`, its caption text items and optional payload.
93 /// `classification` is a `PictureClassificationLabel` value written as
94 /// the picture's `meta.classification` (an HTML `<stamp>` / `<signature>`).
95 Picture {
96 captions: Vec<usize>,
97 image: Option<PictureImage>,
98 classification: Option<String>,
99 /// Further predictions after `classification`, in order: the other
100 /// plot types of a PPTX combination chart (docling#4773).
101 extra_classes: Vec<String>,
102 /// The picture-OCR enrichment's text (#645), serialized like the flat
103 /// node's: `meta.description` + the `description` annotation.
104 description: Option<crate::PictureDescription>,
105 /// The prediction's `confidence`, when the backend writes one: the
106 /// DocLang deserializer stamps `1.0`; the office and HTML backends
107 /// leave it out (`None`).
108 confidence: Option<f64>,
109 /// A native chart's data grid (docling's `meta.tabular_chart.chart_data`,
110 /// the series reconstructed as a `TableData`), for a DOCX chart drawing.
111 chart: Option<Table>,
112 /// The `ImageRef.dpi` docling writes for `image` when the backend
113 /// read one from the file (python-pptx's `Image.dpi`: PIL's `dpi`
114 /// info, rounded, 72 when absent or out of 1–2048); `None` → 72,
115 /// which is what upstream's other office backends pass.
116 dpi: Option<u32>,
117 },
118 /// A form key-value region (`field_regions` / `field_items`).
119 FieldRegion { items: Vec<FieldItem> },
120 /// A `KeyValueItem` (`key_value_items`): docling's `GraphData` of key and
121 /// value cells and their links, written verbatim.
122 KeyValueGraph {
123 cells: Vec<crate::GraphCell>,
124 links: Vec<crate::GraphLink>,
125 },
126}
127
128/// docling's `ProvenanceItem` for a tree item, written verbatim: the
129/// backend's own geometry in the page's units — a PPTX shape's EMU box,
130/// whose `pages` entry is the slide size in EMU — rather than the 0–511
131/// DocLang grid the flat [`Node::Located`](crate::Node::Located) carries
132/// (which cannot round-trip those integers).
133#[derive(Debug, Clone, PartialEq)]
134pub struct TreeProv {
135 /// 1-based page (slide) number.
136 pub page_no: usize,
137 /// `[l, t, r, b]`, exactly as docling computed them.
138 pub bbox: [f64; 4],
139 /// docling's `coord_origin` tag. The office backends tag their
140 /// top-left-based boxes `TOPLEFT` (the PPTX backend since docling#4294 —
141 /// it used to tag them `BOTTOMLEFT`, which read the tuple as `(l, b, r,
142 /// t)` and swapped the vertical edges); a backend that really works in a
143 /// bottom-left space sets this.
144 pub bottom_left: bool,
145 /// `[0, len(text)]` in characters for a text item, `[0, 0]` for a table
146 /// or picture.
147 pub charspan: [usize; 2],
148}
149
150/// docling's `TrackSource` — where in a time-based track (a WebVTT cue) a
151/// text item came from. Written as the item's `source: [{"kind": "track", …}]`.
152#[derive(Debug, Clone, PartialEq)]
153pub struct TreeTrack {
154 /// The cue's start offset in seconds (docling's `WebVTTTimestamp.seconds`:
155 /// `h*3600 + m*60 + s + millis/1000.0`, so the float is bit-identical).
156 pub start_time: f64,
157 /// The cue's end offset in seconds.
158 pub end_time: f64,
159 /// The cue identifier line, when the cue has one.
160 pub identifier: Option<String>,
161 /// The `<v …>` voice annotation the text sits in, when any.
162 pub voice: Option<String>,
163}
164
165/// One item of an [`ItemTree`].
166#[derive(Debug, Clone, PartialEq)]
167pub struct TreeItem {
168 /// The parent item's index; `None` = the document body.
169 pub parent: Option<usize>,
170 /// Child item indices, in docling's `children` order.
171 pub children: Vec<usize>,
172 /// The content layer; `None` = `body`.
173 pub layer: Option<ContentLayer>,
174 pub kind: TreeKind,
175 /// The item's `prov` entry, when the backend has page geometry for it
176 /// (`None` → `prov: []`, what the HTML and DOCX backends write).
177 pub prov: Option<TreeProv>,
178 /// docling's `DocItem.comments`: the `comment_section` groups (or note
179 /// text items) annotating this item, as item indices — written after
180 /// `prov` when non-empty.
181 pub comments: Vec<usize>,
182 /// docling's `DocItem.source`: the track segment a text item was taken
183 /// from (WebVTT cues) — written after `prov` when set.
184 pub source: Option<TreeTrack>,
185 /// Removed by [`ItemTree::delete`] (docling's `delete_items`): the slot
186 /// stays so every other index keeps its meaning, but the item is not
187 /// numbered or written.
188 pub deleted: bool,
189 /// docling's `FloatingItem.footnotes` for a picture or code item (a
190 /// DocLang float group's `<footnote>`s), as item indices — written as the
191 /// item's `footnotes` refs; a table keeps its own in
192 /// [`TreeKind::Table`]'s `footnotes`. Unrelated to [`Self::notes`], which
193 /// are note calls in a text.
194 pub footnotes: Vec<usize>,
195 /// Footnotes / endnotes referenced from inside this text item (#538): the
196 /// note call's position (chars into the item's text) and the note's text.
197 /// docling keeps notes as unlinked furniture `footnote` items, so the
198 /// JSON never shows this; the Pandoc AST writes each as a `Note` there.
199 pub notes: Vec<TreeNote>,
200 /// This furniture `footnote` item is the body of a note some text item
201 /// calls (it travels in that item's [`Self::notes`]); the Pandoc AST then
202 /// leaves it out as a standalone block.
203 pub note_body: bool,
204 /// Link destinations at this item (#849): the identifiers a document's
205 /// internal links (`hyperlink: "#id"`) point at — a DOCX bookmark in
206 /// a heading, say. docling's model has no slot for them, so the JSON
207 /// shows them only on the Pandoc path (`_anchors`), where a heading's
208 /// first one is its `Header` id and the rest empty `Span .anchor`s.
209 pub anchors: Vec<String>,
210 /// The generated numbering `text` opens with, when the backend put one
211 /// there (#850: a DOCX heading numbered through `w:numPr` is docling's
212 /// `1.2 Title`): `"1.2"` — the authored text follows it after one
213 /// space. docling's JSON keeps the numbered text; the Pandoc AST writes
214 /// the authored text alone (`_number` on that path), since Pandoc
215 /// numbers sections itself (`--number-sections`) and its docx reader
216 /// never writes the number into the `Header`.
217 pub number: Option<String>,
218 /// The tracked change this run carries under
219 /// [`TrackChanges::All`](crate::TrackChanges::All) (#851): the Pandoc
220 /// AST wraps the run in `Span .insertion` / `.deletion` (`_revision`
221 /// on that path); docling's JSON has no field for it.
222 pub revision: Option<crate::Revision>,
223 /// A picture's `meta.code` — docling's `CodeMetaField` (`text`,
224 /// `language`): the LaTeX backend keeps a `tikzpicture`'s source there
225 /// when no engine renders it (`("…", "Tikz")`).
226 pub code_meta: Option<(String, String)>,
227 /// The source block this item was made from (#903): an index into
228 /// [`ItemTree::blocks`], set by a backend that enumerates its source's
229 /// blocks (HTML). `None` when the backend does not, or for an item no
230 /// single block produced.
231 pub block: Option<usize>,
232}
233
234/// A block of the source document (#903, #904): the original element an
235/// item was made from — or one that produced no item, with the reason —
236/// so a caller can tie converted items back to the source, tell two
237/// identical texts apart, and read a block's text on its own terms, free of
238/// any serializer's separators.
239///
240/// The HTML backend enumerates, in document order, every element that
241/// produced an item, every non-inline element with text of its own (text
242/// nodes reached through inline elements only — a `<span>`'s text belongs
243/// to the block around it), and every empty `<p>`, heading, `<li>`, `<dt>`,
244/// `<dd>`, `<td>`/`<th>`, `<pre>` or `<caption>`. Pure containers (a layout
245/// `<div>` with nothing but blocks inside) are not blocks. Every text node
246/// of the source thus belongs to exactly one block.
247#[derive(Debug, Clone, PartialEq, Eq)]
248pub struct SourceBlock {
249 /// The element's tag name (`p`, `div`, `li`, `table`, `img`, …).
250 pub tag: String,
251 /// Its `id` attribute, when it has one.
252 pub id: Option<String>,
253 /// Its `class` attribute, as written.
254 pub class: Option<String>,
255 /// Every attribute of the element, by name (#910): `id` and `class`
256 /// among them, and whatever else the source put there — `style`,
257 /// `aria-hidden`, a RIS element's `typ`.
258 pub attrs: Vec<(String, String)>,
259 /// The element's path from the document root — each step the tag and
260 /// the 1-based position among the parent's same-tag element children,
261 /// `html/body/div[3]/p[1]` — stable for the document and unique to the
262 /// element, with or without an `id`.
263 pub path: String,
264 /// The block's own text: its text nodes (and those of the inline
265 /// elements inside it, not of nested blocks) in source order, whitespace
266 /// runs collapsed to one space, trimmed. Independent of what the items
267 /// made of it hold — a hidden block's text is here too.
268 pub text: String,
269 /// The items made from this block, in creation order — the top-level
270 /// ones (an inline group, not the runs inside it; a list group, not
271 /// its items, which have their `<li>` blocks). Empty when it produced
272 /// none: see `omitted`.
273 pub items: Vec<usize>,
274 /// Why no item was made from this block; `None` when `items` is not
275 /// empty.
276 pub omitted: Option<BlockOmission>,
277 /// The inline elements inside the block (#911) — a `<span
278 /// class="sr-only">`, a `<b>`, an `<a>` — each with its range in `text`,
279 /// in document order, nested ones after the ones they sit in.
280 pub inlines: Vec<SourceInline>,
281}
282
283impl SourceBlock {
284 /// The block's text without the inline elements `exclude` selects
285 /// (#911): their ranges cut out, whitespace normalized again. A
286 /// screen-reader alternative (`.sr-only`) left out, say — the caller
287 /// chooses, nothing is inferred from a class.
288 pub fn text_excluding(&self, exclude: impl Fn(&SourceInline) -> bool) -> String {
289 let mut cut: Vec<(usize, usize)> = self
290 .inlines
291 .iter()
292 .filter(|i| exclude(i))
293 .map(|i| (i.start, i.end))
294 .collect();
295 if cut.is_empty() {
296 return self.text.clone();
297 }
298 cut.sort_unstable();
299 let mut out = String::with_capacity(self.text.len());
300 let mut pos = 0;
301 for (start, end) in cut {
302 if start > pos {
303 out.push_str(&self.text[pos..start]);
304 out.push(' ');
305 }
306 pos = pos.max(end);
307 }
308 out.push_str(&self.text[pos.min(self.text.len())..]);
309 out.split_whitespace().collect::<Vec<_>>().join(" ")
310 }
311}
312
313/// An inline element inside a [`SourceBlock`] (#911): where its text sits
314/// in the block's, so a caller can select or leave out the text of one
315/// element — not a whole block — by what the source says about it.
316#[derive(Debug, Clone, PartialEq, Eq)]
317pub struct SourceInline {
318 /// The element's tag name (`span`, `b`, `a`, …).
319 pub tag: String,
320 /// Every attribute, by name.
321 pub attrs: Vec<(String, String)>,
322 /// Its path from the document root, as [`SourceBlock::path`].
323 pub path: String,
324 /// The byte range of its text in [`SourceBlock::text`] — always on
325 /// char boundaries, so `&text[start..end]` is the element's normalized
326 /// text; empty for an element with no text.
327 pub start: usize,
328 pub end: usize,
329}
330
331impl SourceInline {
332 /// The value of attribute `name`.
333 pub fn attr(&self, name: &str) -> Option<&str> {
334 self.attrs
335 .iter()
336 .find(|(k, _)| k == name)
337 .map(|(_, v)| v.as_str())
338 }
339
340 /// Its `id` attribute.
341 pub fn id(&self) -> Option<&str> {
342 self.attr("id")
343 }
344
345 /// Its `class` attribute, as written.
346 pub fn class(&self) -> Option<&str> {
347 self.attr("class")
348 }
349
350 /// Whether `class` is one of the element's classes.
351 pub fn has_class(&self, class: &str) -> bool {
352 self.class()
353 .is_some_and(|c| c.split_whitespace().any(|x| x == class))
354 }
355}
356
357/// Builds a [`SourceBlock`]'s normalized text while recording the inline
358/// elements' ranges in it (#911) — for a backend walking its source: text
359/// nodes through [`push_text`](Self::push_text), a line break as
360/// whitespace, an inline element between [`open_inline`](Self::open_inline)
361/// and [`close_inline`](Self::close_inline). Whitespace runs collapse to one
362/// space, the text is trimmed, and a range never starts with the space
363/// that separates it from what precedes.
364#[derive(Debug, Default)]
365pub struct SourceTextBuilder {
366 text: String,
367 /// Whitespace seen since the last non-space char, not yet written.
368 pending: bool,
369 inlines: Vec<SourceInline>,
370 /// The inlines open right now, as indices into `inlines`.
371 open: Vec<usize>,
372}
373
374impl SourceTextBuilder {
375 pub fn new() -> Self {
376 Self::default()
377 }
378
379 /// A text node (or any text) of the block.
380 pub fn push_text(&mut self, raw: &str) {
381 for c in raw.chars() {
382 if c.is_whitespace() {
383 self.pending = true;
384 } else {
385 self.flush_space();
386 self.text.push(c);
387 }
388 }
389 }
390
391 fn flush_space(&mut self) {
392 if self.pending {
393 // One space, however many elements' whitespace fell between two
394 // words (an empty spacing `<span>` between two others).
395 if !self.text.is_empty() && !self.text.ends_with(' ') {
396 self.text.push(' ');
397 }
398 self.pending = false;
399 }
400 }
401
402 /// An inline element starts here.
403 pub fn open_inline(&mut self, tag: &str, attrs: Vec<(String, String)>, path: String) {
404 self.flush_space();
405 let at = self.text.len();
406 self.open.push(self.inlines.len());
407 self.inlines.push(SourceInline {
408 tag: tag.to_string(),
409 attrs,
410 path,
411 start: at,
412 end: at,
413 });
414 }
415
416 /// The innermost open inline element ends here.
417 pub fn close_inline(&mut self) {
418 if let Some(i) = self.open.pop() {
419 self.inlines[i].end = self.text.len();
420 }
421 }
422
423 /// The text and the inline ranges; the text has no trailing space.
424 pub fn finish(mut self) -> (String, Vec<SourceInline>) {
425 while let Some(i) = self.open.pop() {
426 self.inlines[i].end = self.text.len();
427 }
428 if self.text.ends_with(' ') {
429 self.text.pop();
430 let len = self.text.len();
431 for i in &mut self.inlines {
432 i.start = i.start.min(len);
433 i.end = i.end.min(len);
434 }
435 }
436 (self.text, self.inlines)
437 }
438}
439
440/// An element of the source that is not a block but carries an `id` or a
441/// `class` (#910): a container — the `<div id="art_23">` an article's
442/// paragraphs sit in — so an excerpt selected by a container's identity
443/// resolves to a path and, through [`ItemTree::blocks_under`], to the blocks
444/// inside it. A block's own identity is on the block.
445#[derive(Debug, Clone, PartialEq, Eq)]
446pub struct SourceElement {
447 /// The element's tag name.
448 pub tag: String,
449 /// Its `id` attribute, when it has one.
450 pub id: Option<String>,
451 /// Its `class` attribute, as written.
452 pub class: Option<String>,
453 /// Every attribute, by name.
454 pub attrs: Vec<(String, String)>,
455 /// Its path from the document root, as [`SourceBlock::path`].
456 pub path: String,
457}
458
459/// Why a [`SourceBlock`] produced no item.
460#[derive(Debug, Clone, Copy, PartialEq, Eq)]
461pub enum BlockOmission {
462 /// No text of its own once normalized (an empty `<p>`, a `<li>` whose
463 /// content is nested blocks).
464 Empty,
465 /// Hidden or non-content (`display: none`, `hidden`, `<script>`,
466 /// `<style>`, `<noscript>`), or inside such an element.
467 Hidden,
468 /// In a table whose cells were flattened: the text is in the grid of
469 /// the table item (the index) rather than an item of its own.
470 InTable(usize),
471 /// Its text went into the items of an enclosing block (the index into
472 /// [`ItemTree::blocks`]): a `<p>` inside a `<li>` is the list item's
473 /// text.
474 Merged(usize),
475 /// The walk produced nothing the backend can attribute.
476 Unmapped,
477}
478
479/// A note call inside a text item ([`TreeItem::notes`]).
480#[derive(Debug, Clone, PartialEq, Eq)]
481pub struct TreeNote {
482 /// The call's position, in chars into the item's `text`.
483 pub offset: usize,
484 /// The note's plain text.
485 pub text: String,
486}
487
488impl ItemTree {
489 /// Where each note call of one paragraph lands (#538): `full_text` is the
490 /// paragraph's text, `offsets` the calls' positions in it (chars), and
491 /// the paragraph's items are those created from `first_new` on. Each text
492 /// item is a trimmed slice of the paragraph (a formatting run, a link, or
493 /// the whole heading / list item), matched in order; a call inside an
494 /// item lands there, one between items ends the earlier (or starts the
495 /// first). When no item matches, the call ends the paragraph's last text
496 /// item; with no text item at all it is `None`.
497 pub fn place_note_calls(
498 &self,
499 first_new: usize,
500 full_text: &str,
501 offsets: &[usize],
502 ) -> Vec<Option<(usize, usize)>> {
503 let texts: Vec<(usize, &str)> = (first_new..self.items.len())
504 .filter(|&i| !self.items[i].deleted)
505 .filter_map(|i| match &self.items[i].kind {
506 TreeKind::Text { text, .. } | TreeKind::Code { text, .. } => {
507 Some((i, text.as_str()))
508 }
509 _ => None,
510 })
511 .collect();
512 // Each found item's (id, start, end) in chars of `full_text`.
513 let mut spans: Vec<(usize, usize, usize)> = Vec::new();
514 let mut cursor = 0usize; // bytes
515 for &(item, text) in &texts {
516 if text.is_empty() {
517 continue;
518 }
519 if let Some(pos) = full_text[cursor..].find(text) {
520 let start_b = cursor + pos;
521 let start = full_text[..start_b].chars().count();
522 spans.push((item, start, start + text.chars().count()));
523 cursor = start_b + text.len();
524 }
525 }
526 offsets
527 .iter()
528 .map(|&offset| {
529 spans
530 .iter()
531 .find(|&&(_, start, end)| offset >= start && offset <= end)
532 .map(|&(item, start, _)| (item, offset - start))
533 .or_else(
534 || match spans.iter().rev().find(|&&(_, _, end)| end <= offset) {
535 Some(&(item, start, end)) => Some((item, end - start)),
536 None => spans.first().map(|&(item, _, _)| (item, 0)),
537 },
538 )
539 .or_else(|| {
540 texts
541 .last()
542 .map(|&(item, text)| (item, text.chars().count()))
543 })
544 })
545 .collect()
546 }
547}
548
549/// docling's item tree in creation order (see the [module docs](self)).
550#[derive(Debug, Clone, PartialEq, Default)]
551pub struct ItemTree {
552 /// Every item, indexed by creation order — which is how docling numbers
553 /// `#/texts/N`, `#/groups/N`, … within each bucket.
554 pub items: Vec<TreeItem>,
555 /// The body's `children`, as item indices.
556 pub body: Vec<usize>,
557 /// The source's blocks (#903), in document order, when the backend
558 /// enumerates them (HTML); each item's [`TreeItem::block`] points into
559 /// this. Empty otherwise.
560 pub blocks: Vec<SourceBlock>,
561 /// The source's containers that carry an `id` or a `class` (#910), in
562 /// document order; see [`SourceElement`]. Empty when `blocks` is.
563 pub containers: Vec<SourceElement>,
564 /// The runs of this tree's `inline` groups carry their own boundary
565 /// whitespace — docling-core's inline whitespace contract (schema 1.11.0,
566 /// [`crate::inline`]): a backend that keeps each run's spaces, as
567 /// docling's do since docling#3891, sets it. Unset, the runs are the
568 /// trimmed runs the old `" "` join expected, and the export re-injects
569 /// that join into them ([`Self::separate_legacy_inline_runs`]) so the
570 /// output reads as it did.
571 pub inline_whitespace: bool,
572 /// The DocLang export serializes the flat nodes rather than this tree,
573 /// which every other tree gets its DocLang from: the tree reproduces a
574 /// loss of docling's the nodes avoid (USPTO's tables, emptied when
575 /// docling's table regex misses them), and the DocLang follows the
576 /// Markdown there.
577 pub doclang_nodes: bool,
578}
579
580impl ItemTree {
581 /// Append an item under `parent` (`None` = body) on `layer`, registering
582 /// it as its parent's last child — docling's `add_*` calls do exactly that.
583 pub fn add(
584 &mut self,
585 parent: Option<usize>,
586 layer: Option<ContentLayer>,
587 kind: TreeKind,
588 ) -> usize {
589 let id = self.items.len();
590 self.items.push(TreeItem {
591 parent,
592 children: Vec::new(),
593 layer,
594 kind,
595 prov: None,
596 comments: Vec::new(),
597 source: None,
598 deleted: false,
599 footnotes: Vec::new(),
600 notes: Vec::new(),
601 note_body: false,
602 anchors: Vec::new(),
603 number: None,
604 revision: None,
605 code_meta: None,
606 block: None,
607 });
608 match parent {
609 Some(p) => self.items[p].children.push(id),
610 None => self.body.push(id),
611 }
612 id
613 }
614
615 /// [`add`](Self::add) with the item's provenance — docling's
616 /// `add_text(…, prov=prov)`.
617 pub fn add_with_prov(
618 &mut self,
619 parent: Option<usize>,
620 layer: Option<ContentLayer>,
621 kind: TreeKind,
622 prov: TreeProv,
623 ) -> usize {
624 let id = self.add(parent, layer, kind);
625 self.items[id].prov = Some(prov);
626 id
627 }
628
629 /// The text of the given source blocks (#904), one line each: each
630 /// block's own normalized [`SourceBlock::text`], joined with a single
631 /// `\n` — no serializer decoration, no trailing separator, nothing of
632 /// the blocks around them. Indices out of range are skipped.
633 pub fn source_text(&self, blocks: impl IntoIterator<Item = usize>) -> String {
634 let mut out = String::new();
635 for b in blocks {
636 let Some(block) = self.blocks.get(b) else {
637 continue;
638 };
639 if !out.is_empty() {
640 out.push('\n');
641 }
642 out.push_str(&block.text);
643 }
644 out
645 }
646
647 /// [`source_text`](Self::source_text) without the inline elements
648 /// `exclude` selects in each block ([`SourceBlock::text_excluding`]).
649 pub fn source_text_excluding(
650 &self,
651 blocks: impl IntoIterator<Item = usize>,
652 exclude: impl Fn(&SourceInline) -> bool,
653 ) -> String {
654 let mut out = String::new();
655 for b in blocks {
656 let Some(block) = self.blocks.get(b) else {
657 continue;
658 };
659 if !out.is_empty() {
660 out.push('\n');
661 }
662 out.push_str(&block.text_excluding(&exclude));
663 }
664 out
665 }
666
667 /// The blocks under `path` (#910), in document order: those whose
668 /// [`SourceBlock::path`] is `path` or starts with `path/` — the block
669 /// itself, or everything inside a container.
670 pub fn blocks_under(&self, path: &str) -> Vec<usize> {
671 let prefix = format!("{path}/");
672 self.blocks
673 .iter()
674 .enumerate()
675 .filter(|(_, b)| b.path == path || b.path.starts_with(&prefix))
676 .map(|(i, _)| i)
677 .collect()
678 }
679
680 /// The path of the element with `id` (#910): a block's or a container's,
681 /// the first in document order when the source repeats an id.
682 pub fn path_of_id(&self, id: &str) -> Option<&str> {
683 let block = self
684 .blocks
685 .iter()
686 .find(|b| b.id.as_deref() == Some(id))
687 .map(|b| b.path.as_str());
688 let container = self
689 .containers
690 .iter()
691 .find(|c| c.id.as_deref() == Some(id))
692 .map(|c| c.path.as_str());
693 match (block, container) {
694 (Some(b), Some(c)) => Some(if b.len() <= c.len() && b < c { b } else { c }),
695 (b, c) => b.or(c),
696 }
697 }
698
699 /// Append every item of `other` after this tree's, renumbering its
700 /// indices (parents, children, comments, table/picture caption and
701 /// rich-cell refs) and adding its body children to this body — so a
702 /// backend can build independent fragments in parallel (one per PPTX
703 /// slide) and still hand the export one tree in creation order, exactly
704 /// as if it had been built sequentially.
705 pub fn append(&mut self, other: ItemTree) {
706 let off = self.items.len();
707 let shift = |i: usize| i + off;
708 for mut item in other.items {
709 item.parent = item.parent.map(shift);
710 for c in item
711 .children
712 .iter_mut()
713 .chain(item.comments.iter_mut())
714 .chain(item.footnotes.iter_mut())
715 {
716 *c = shift(*c);
717 }
718 match &mut item.kind {
719 TreeKind::Table {
720 rich_cells,
721 captions,
722 footnotes,
723 ..
724 } => {
725 for (_, _, g) in rich_cells.iter_mut() {
726 *g = shift(*g);
727 }
728 for c in captions.iter_mut().chain(footnotes.iter_mut()) {
729 *c = shift(*c);
730 }
731 }
732 TreeKind::Picture { captions, .. } | TreeKind::Code { captions, .. } => {
733 for c in captions.iter_mut() {
734 *c = shift(*c);
735 }
736 }
737 _ => {}
738 }
739 self.items.push(item);
740 }
741 self.body.extend(other.body.into_iter().map(shift));
742 let block_off = self.blocks.len();
743 for mut b in other.blocks {
744 for i in b.items.iter_mut() {
745 *i = shift(*i);
746 }
747 if let Some(BlockOmission::InTable(t)) = b.omitted.as_mut() {
748 *t = shift(*t);
749 }
750 if let Some(BlockOmission::Merged(m)) = b.omitted.as_mut() {
751 *m += block_off;
752 }
753 self.blocks.push(b);
754 }
755 for item in &mut self.items[off..] {
756 if let Some(b) = item.block.as_mut() {
757 *b += block_off;
758 }
759 }
760 self.containers.extend(other.containers);
761 }
762
763 /// Move `id` under `new_parent`, dropping it from its current parent's
764 /// children and appending it to the new one's — docling's
765 /// `group_cell_elements` re-parenting of a rich cell's items.
766 pub fn reparent(&mut self, id: usize, new_parent: Option<usize>) {
767 let old = self.items[id].parent;
768 let siblings = match old {
769 Some(p) => &mut self.items[p].children,
770 None => &mut self.body,
771 };
772 siblings.retain(|&c| c != id);
773 self.items[id].parent = new_parent;
774 match new_parent {
775 Some(p) => self.items[p].children.push(id),
776 None => self.body.push(id),
777 }
778 }
779
780 /// Re-number the items in traversal order — a pre-order walk of the body
781 /// through every layer, which is how docling's
782 /// `DoclingDocument.concatenate` (and `_normalize_references`) re-creates
783 /// a document's items: a group created after the content it was later
784 /// wrapped around comes before that content afterwards. Items the walk
785 /// does not reach (deleted ones) are dropped. Returns each old id's new
786 /// id.
787 pub fn renumber_in_traversal_order(&mut self) -> Vec<Option<usize>> {
788 let mut order = Vec::with_capacity(self.items.len());
789 let mut stack: Vec<usize> = self.body.iter().rev().copied().collect();
790 while let Some(id) = stack.pop() {
791 if self.items[id].deleted {
792 continue;
793 }
794 order.push(id);
795 stack.extend(self.items[id].children.iter().rev());
796 }
797 let mut new_of: Vec<Option<usize>> = vec![None; self.items.len()];
798 for (new, &old) in order.iter().enumerate() {
799 new_of[old] = Some(new);
800 }
801 let remap = |ids: &mut Vec<usize>| {
802 *ids = ids.iter().filter_map(|&i| new_of[i]).collect();
803 };
804 let mut old_items: Vec<Option<TreeItem>> = std::mem::take(&mut self.items)
805 .into_iter()
806 .map(Some)
807 .collect();
808 for &old in &order {
809 let mut item = old_items[old].take().expect("each item visited once");
810 item.parent = item.parent.and_then(|p| new_of[p]);
811 remap(&mut item.children);
812 remap(&mut item.comments);
813 remap(&mut item.footnotes);
814 match &mut item.kind {
815 TreeKind::Table {
816 rich_cells,
817 captions,
818 footnotes,
819 ..
820 } => {
821 remap(footnotes);
822 rich_cells.retain_mut(|(_, _, g)| match new_of[*g] {
823 Some(n) => {
824 *g = n;
825 true
826 }
827 None => false,
828 });
829 remap(captions);
830 }
831 TreeKind::Picture { captions, .. } | TreeKind::Code { captions, .. } => {
832 remap(captions)
833 }
834 _ => {}
835 }
836 self.items.push(item);
837 }
838 remap(&mut self.body);
839 for b in &mut self.blocks {
840 remap(&mut b.items);
841 if let Some(BlockOmission::InTable(t)) = b.omitted {
842 b.omitted = Some(match new_of[t] {
843 Some(n) => BlockOmission::InTable(n),
844 None => BlockOmission::Unmapped,
845 });
846 }
847 }
848 new_of
849 }
850
851 /// Remove `id` from the tree — docling's `delete_items`, which the DOCX
852 /// backend uses to drop the empty text item a blank spacer paragraph left
853 /// between two items of a resumed list. The item leaves its parent's
854 /// children and is neither numbered nor written; its slot stays so the
855 /// indices held elsewhere stay valid.
856 pub fn delete(&mut self, id: usize) {
857 match self.items[id].parent {
858 Some(p) => self.items[p].children.retain(|&c| c != id),
859 None => self.body.retain(|&c| c != id),
860 }
861 self.items[id].deleted = true;
862 }
863
864 /// docling-core's `_migrate_legacy_inline_separators` (#997) over the
865 /// tree: every `inline` group's runs get the `" "` the pre-1.11 join put
866 /// between them ([`crate::inline::separate_legacy_runs`]) — on a plain
867 /// neighbour, never inside a code or formula run, a standalone `" "` text
868 /// run when both neighbours are delimited. The JSON export applies it to
869 /// a tree whose backend has not set [`Self::inline_whitespace`], so a
870 /// trimmed-run backend still reads `left bold right` under the faithful
871 /// join, as docling-core reads a document saved before the contract.
872 /// `text` changes, `orig` keeps the run's own text.
873 pub fn separate_legacy_inline_runs(&mut self) {
874 fn renders_text(t: &ItemTree, id: usize, depth: usize) -> bool {
875 let item = &t.items[id];
876 if item.deleted || depth > 64 {
877 return false;
878 }
879 let own = match &item.kind {
880 TreeKind::Text { text, .. } | TreeKind::Code { text, .. } => !text.is_empty(),
881 TreeKind::Group { .. } => false,
882 // docling-core resolves only `#/texts/` and `#/groups/`.
883 _ => return false,
884 };
885 own || item.children.iter().any(|&c| renders_text(t, c, depth + 1))
886 }
887 let groups: Vec<usize> = (0..self.items.len())
888 .filter(|&g| {
889 !self.items[g].deleted
890 && matches!(&self.items[g].kind, TreeKind::Group { label, .. } if label == "inline")
891 })
892 .collect();
893 for g in groups {
894 let children: Vec<usize> = self.items[g]
895 .children
896 .iter()
897 .copied()
898 .filter(|&c| !self.items[c].deleted)
899 .collect();
900 let flags: Vec<(bool, bool, bool)> = children
901 .iter()
902 .map(|&c| {
903 let item = &self.items[c];
904 let (plain, empty_plain) = match &item.kind {
905 TreeKind::Text { label, text, .. } => (
906 label != "formula" && label != "code",
907 label == "text" && text.is_empty() && item.children.is_empty(),
908 ),
909 _ => (false, false),
910 };
911 (renders_text(self, c, 0), plain, empty_plain)
912 })
913 .collect();
914 // Detach the texts so each run can be borrowed mutably at once.
915 let mut texts: Vec<String> = children
916 .iter()
917 .map(|&c| match &self.items[c].kind {
918 TreeKind::Text { text, .. } | TreeKind::Code { text, .. } => text.clone(),
919 _ => String::new(),
920 })
921 .collect();
922 let originals = texts.clone();
923 let standalone = {
924 let mut runs: Vec<crate::inline::LegacyRun<'_>> = texts
925 .iter_mut()
926 .zip(&flags)
927 .map(
928 |(text, &(renders_text, plain, empty_plain))| crate::inline::LegacyRun {
929 text,
930 renders_text,
931 plain,
932 empty_plain,
933 },
934 )
935 .collect();
936 crate::inline::separate_legacy_runs(&mut runs)
937 };
938 for ((&c, new), old) in children.iter().zip(texts).zip(originals) {
939 if new == old {
940 continue;
941 }
942 // docling-core rewrites `text` and leaves `orig` as it was.
943 if let TreeKind::Text { text, orig, .. } | TreeKind::Code { text, orig, .. } =
944 &mut self.items[c].kind
945 {
946 orig.get_or_insert(old);
947 *text = new;
948 }
949 }
950 for at in standalone.into_iter().rev() {
951 let (left, right) = (children[at - 1], children[at]);
952 // The left run's location when both sit on one page, so a
953 // page filter keeps the separator exactly when it keeps both.
954 let prov = match (&self.items[left].prov, &self.items[right].prov) {
955 (Some(l), Some(r)) if l.page_no == r.page_no => Some(TreeProv {
956 charspan: [0, 1],
957 ..l.clone()
958 }),
959 _ => None,
960 };
961 let layer = self.items[g].layer;
962 let id = self.add(
963 Some(g),
964 layer,
965 TreeKind::Text {
966 label: "text".into(),
967 text: " ".into(),
968 orig: None,
969 formatting: None,
970 hyperlink: None,
971 level: None,
972 list: None,
973 },
974 );
975 self.items[id].prov = prov;
976 let kids = &mut self.items[g].children;
977 kids.pop();
978 let pos = kids.iter().position(|&k| k == right).unwrap_or(kids.len());
979 kids.insert(pos, id);
980 }
981 }
982 }
983
984 /// docling-core's `DoclingDocument.validate_misplaced_list_items` (a
985 /// model validator, so it runs whenever docling-core serializes or loads
986 /// a document): every `list_item` whose parent is not a `list` group is
987 /// re-homed into a new one. A pre-order walk of the body (groups
988 /// included) collects them; consecutive misplaced items directly on the
989 /// body share one group, any other misplaced item gets its own. Working
990 /// from the last run back, each run gets a `ListGroup` (name `group`)
991 /// inserted where its first item stood, the items are deleted and
992 /// re-added under the group as fresh items, so they move to the end of
993 /// the text numbering (#527: the DOCX backend leaves such items in rich
994 /// table cells). A no-op for a well-formed tree.
995 ///
996 /// One deliberate divergence (#586): docling-core deletes each item *with
997 /// its children* and re-adds it from its text alone, so a mixed-format
998 /// item — an empty `list_item` over an `inline` group of text runs —
999 /// comes back empty and its text is gone from the JSON (and from the
1000 /// Markdown/HTML docling serializes after that validator ran; the JSON
1001 /// docling saves *before* exporting still has it). Here the children
1002 /// follow the item into the group: the structure docling-core requires,
1003 /// the content the document had.
1004 pub fn wrap_misplaced_list_items(&mut self) {
1005 let is_list_item = |t: &Self, id: usize| matches!(&t.items[id].kind, TreeKind::Text { label, .. } if label == "list_item");
1006 let in_list_group = |t: &Self, id: usize| {
1007 t.items[id].parent.is_some_and(
1008 |p| matches!(&t.items[p].kind, TreeKind::Group { label, .. } if label == "list"),
1009 )
1010 };
1011 let mut runs: Vec<Vec<usize>> = Vec::new();
1012 // `None` = the body itself, which the walk yields first.
1013 let mut prev: Option<usize> = None;
1014 let mut stack: Vec<usize> = self.body.iter().rev().copied().collect();
1015 while let Some(id) = stack.pop() {
1016 if self.items[id].deleted {
1017 continue;
1018 }
1019 if is_list_item(self, id) && !in_list_group(self, id) {
1020 let continues =
1021 prev.is_some_and(|p| is_list_item(self, p) && self.items[p].parent.is_none());
1022 match runs.last_mut() {
1023 Some(run) if continues => run.push(id),
1024 _ => runs.push(vec![id]),
1025 }
1026 }
1027 prev = Some(id);
1028 stack.extend(self.items[id].children.iter().rev().copied());
1029 }
1030 for run in runs.into_iter().rev() {
1031 let parent = self.items[run[0]].parent;
1032 let group = self.add(
1033 parent,
1034 None,
1035 TreeKind::Group {
1036 label: "list".into(),
1037 name: "group".into(),
1038 },
1039 );
1040 let siblings = match parent {
1041 Some(p) => &mut self.items[p].children,
1042 None => &mut self.body,
1043 };
1044 siblings.pop();
1045 let at = siblings
1046 .iter()
1047 .position(|&c| c == run[0])
1048 .unwrap_or(siblings.len());
1049 siblings.insert(at, group);
1050 for &li in &run {
1051 // Not `delete_subtree`: the children move to the copy (#586).
1052 self.delete(li);
1053 }
1054 // `add_list_item` keeps the text, marker, formatting, hyperlink
1055 // and first provenance — not comments or a source. The children
1056 // (the inline group of a mixed-format item) are carried over.
1057 for &li in &run {
1058 let children = std::mem::take(&mut self.items[li].children);
1059 let copy = TreeItem {
1060 parent: Some(group),
1061 children: children.clone(),
1062 comments: Vec::new(),
1063 source: None,
1064 deleted: false,
1065 ..self.items[li].clone()
1066 };
1067 let id = self.items.len();
1068 self.items.push(copy);
1069 for c in children {
1070 self.items[c].parent = Some(id);
1071 }
1072 self.items[group].children.push(id);
1073 }
1074 }
1075 }
1076
1077 /// The last live text-bucket item (docling's `doc.texts[-1]`).
1078 pub fn last_text(&self) -> Option<usize> {
1079 self.items.iter().rposition(|it| {
1080 !it.deleted && matches!(it.kind, TreeKind::Text { .. } | TreeKind::Code { .. })
1081 })
1082 }
1083
1084 /// How many items of a bucket precede `id` — its `#/{bucket}/N` index.
1085 pub fn bucket_index(&self, id: usize) -> usize {
1086 let same = |k: &TreeKind| {
1087 std::mem::discriminant(k) == std::mem::discriminant(&self.items[id].kind)
1088 || matches!(
1089 (k, &self.items[id].kind),
1090 (TreeKind::Text { .. }, TreeKind::Code { .. })
1091 | (TreeKind::Code { .. }, TreeKind::Text { .. })
1092 )
1093 };
1094 self.items[..id]
1095 .iter()
1096 .filter(|it| !it.deleted && same(&it.kind))
1097 .count()
1098 }
1099
1100 /// The number of tables created so far (docling's `len(doc.tables)`).
1101 pub fn table_count(&self) -> usize {
1102 self.items
1103 .iter()
1104 .filter(|it| !it.deleted && matches!(it.kind, TreeKind::Table { .. }))
1105 .count()
1106 }
1107}
1108
1109#[cfg(test)]
1110mod tests {
1111 use super::*;
1112
1113 fn text(t: &str) -> TreeKind {
1114 TreeKind::Text {
1115 label: "text".into(),
1116 text: t.into(),
1117 orig: None,
1118 formatting: None,
1119 hyperlink: None,
1120 level: None,
1121 list: None,
1122 }
1123 }
1124
1125 /// `add` registers the item as its parent's (or the body's) last child;
1126 /// `reparent` moves it — a rich cell's items leave the heading they were
1127 /// created under for the table's group.
1128 #[test]
1129 fn add_and_reparent_keep_docling_children_order() {
1130 let mut t = ItemTree::default();
1131 let title = t.add(None, None, text("Title"));
1132 let a = t.add(Some(title), None, text("a"));
1133 let b = t.add(Some(title), None, text("b"));
1134 let table = t.add(
1135 Some(title),
1136 None,
1137 TreeKind::Table {
1138 footnotes: Vec::new(),
1139 table: Table::default(),
1140 rich_cells: Vec::new(),
1141 captions: Vec::new(),
1142 },
1143 );
1144 let group = t.add(
1145 Some(table),
1146 None,
1147 TreeKind::Group {
1148 label: "unspecified".into(),
1149 name: "rich_cell_group_1_0_0".into(),
1150 },
1151 );
1152 assert_eq!(t.body, vec![title]);
1153 assert_eq!(t.items[title].children, vec![a, b, table]);
1154 t.reparent(a, Some(group));
1155 assert_eq!(t.items[title].children, vec![b, table]);
1156 assert_eq!(t.items[group].children, vec![a]);
1157 assert_eq!(t.items[a].parent, Some(group));
1158 assert_eq!(t.table_count(), 1);
1159 // Text and code share the `texts` bucket.
1160 let code = t.add(
1161 None,
1162 None,
1163 TreeKind::Code {
1164 text: "x".into(),
1165 orig: None,
1166 language: None,
1167 formatting: None,
1168 hyperlink: None,
1169 captions: Vec::new(),
1170 },
1171 );
1172 assert_eq!(t.bucket_index(code), 3, "title, a, b precede it in `texts`");
1173 assert_eq!(t.bucket_index(group), 0);
1174 assert_eq!(t.body, vec![title, code]);
1175 }
1176
1177 /// `append` renumbers a fragment built on its own (a slide converted in
1178 /// parallel) so the merged tree reads as if built in one pass: parents,
1179 /// children, comment back-refs and caption refs all shift together.
1180 #[test]
1181 fn append_renumbers_a_fragment_into_creation_order() {
1182 let mut whole = ItemTree::default();
1183 let slide0 = whole.add(
1184 None,
1185 None,
1186 TreeKind::Group {
1187 label: "chapter".into(),
1188 name: "slide-0".into(),
1189 },
1190 );
1191 whole.add(Some(slide0), None, text("first"));
1192
1193 let mut frag = ItemTree::default();
1194 let slide1 = frag.add(
1195 None,
1196 None,
1197 TreeKind::Group {
1198 label: "chapter".into(),
1199 name: "slide-1".into(),
1200 },
1201 );
1202 let cap = frag.add_with_prov(
1203 Some(slide1),
1204 None,
1205 TreeKind::Text {
1206 label: "caption".into(),
1207 text: "Title".into(),
1208 orig: None,
1209 formatting: None,
1210 hyperlink: None,
1211 level: None,
1212 list: None,
1213 },
1214 TreeProv {
1215 page_no: 2,
1216 bbox: [1.0, 2.0, 3.0, 4.0],
1217 bottom_left: true,
1218 charspan: [0, 5],
1219 },
1220 );
1221 let pic = frag.add(
1222 Some(slide1),
1223 None,
1224 TreeKind::Picture {
1225 captions: vec![cap],
1226 image: None,
1227 extra_classes: Vec::new(),
1228 classification: Some("bar_chart".into()),
1229 description: None,
1230 confidence: None,
1231 chart: None,
1232 dpi: None,
1233 },
1234 );
1235 let note = frag.add(
1236 None,
1237 Some(ContentLayer::Notes),
1238 TreeKind::Group {
1239 label: "comment_section".into(),
1240 name: "comment-slide2-1".into(),
1241 },
1242 );
1243 frag.items[pic].comments.push(note);
1244
1245 whole.append(frag);
1246 assert_eq!(whole.body, vec![slide0, 2, 5]);
1247 assert_eq!(whole.items[2].children, vec![3, 4]);
1248 assert_eq!(whole.items[3].parent, Some(2));
1249 assert_eq!(whole.items[3].prov.as_ref().map(|p| p.page_no), Some(2));
1250 assert!(
1251 matches!(&whole.items[4].kind, TreeKind::Picture { captions, .. } if captions == &[3])
1252 );
1253 assert_eq!(whole.items[4].comments, vec![5]);
1254 assert_eq!(whole.items[5].parent, None);
1255 assert_eq!(
1256 whole.bucket_index(4),
1257 0,
1258 "the fragment's picture is #/pictures/0"
1259 );
1260 assert_eq!(
1261 whole.bucket_index(5),
1262 2,
1263 "slide-0, slide-1 precede it in `groups`"
1264 );
1265 }
1266
1267 /// `renumber_in_traversal_order`: docling's `concatenate` re-creates the
1268 /// items as a pre-order walk meets them, so a group created after the
1269 /// content it was wrapped around (a rich cell's group) comes first, and a
1270 /// deleted item disappears; every cross-reference follows.
1271 #[test]
1272 fn renumbering_follows_the_traversal() {
1273 let mut t = ItemTree::default();
1274 let a = t.add(None, None, text("a"));
1275 let table = t.add(
1276 None,
1277 None,
1278 TreeKind::Table {
1279 footnotes: Vec::new(),
1280 table: Table::default(),
1281 rich_cells: Vec::new(),
1282 captions: Vec::new(),
1283 },
1284 );
1285 let cell_text = t.add(None, None, text("cell"));
1286 let group = t.add(
1287 Some(table),
1288 None,
1289 TreeKind::Group {
1290 label: "unspecified".into(),
1291 name: "rich_cell_group_1_0_0".into(),
1292 },
1293 );
1294 t.reparent(cell_text, Some(group));
1295 if let TreeKind::Table { rich_cells, .. } = &mut t.items[table].kind {
1296 rich_cells.push((0, 0, group));
1297 }
1298 let gone = t.add(None, None, text("gone"));
1299 t.delete(gone);
1300 let z = t.add(None, None, text("z"));
1301
1302 let new_of = t.renumber_in_traversal_order();
1303 assert_eq!(
1304 new_of,
1305 vec![Some(0), Some(1), Some(3), Some(2), None, Some(4)]
1306 );
1307 assert_eq!(t.items.len(), 5);
1308 assert_eq!(t.body, vec![0, 1, 4]);
1309 assert_eq!(t.items[1].children, vec![2], "the group follows its table");
1310 assert_eq!(t.items[2].parent, Some(1));
1311 assert_eq!(
1312 t.items[3].parent,
1313 Some(2),
1314 "the cell text follows its group"
1315 );
1316 assert!(matches!(&t.items[3].kind, TreeKind::Text { text, .. } if text == "cell"));
1317 assert!(
1318 matches!(&t.items[1].kind, TreeKind::Table { rich_cells, .. } if rich_cells == &[(0, 0, 2)])
1319 );
1320 let _ = (a, z);
1321 }
1322
1323 /// #586: a misplaced `list_item` keeps its children when it is re-homed.
1324 /// docling-core's `validate_misplaced_list_items` re-adds the item from
1325 /// its text alone, so a mixed-format item (empty `list_item` over an
1326 /// `inline` group of runs) lost every run — a DOCX table cell whose list
1327 /// paragraph followed a `numId 0` spacer came out as an empty bullet in
1328 /// the JSON and the HTML. The group goes where the item stood, the copy
1329 /// is numbered last, the inline group and its texts move under it.
1330 #[test]
1331 fn wrapping_a_misplaced_list_item_keeps_its_runs() {
1332 let mut t = ItemTree::default();
1333 let cell = t.add(
1334 None,
1335 None,
1336 TreeKind::Group {
1337 label: "unspecified".into(),
1338 name: "rich_cell_group_1_0_1".into(),
1339 },
1340 );
1341 let before = t.add(Some(cell), None, text("before"));
1342 let item = t.add(
1343 Some(cell),
1344 None,
1345 TreeKind::Text {
1346 label: "list_item".into(),
1347 text: String::new(),
1348 orig: None,
1349 formatting: None,
1350 hyperlink: None,
1351 level: None,
1352 list: Some(ListMeta {
1353 enumerated: false,
1354 marker: String::new(),
1355 }),
1356 },
1357 );
1358 let inline = t.add(
1359 Some(item),
1360 None,
1361 TreeKind::Group {
1362 label: "inline".into(),
1363 name: "group".into(),
1364 },
1365 );
1366 let run_a = t.add(Some(inline), None, text("Second item text"));
1367 let run_b = t.add(Some(inline), None, text("[Optional]"));
1368 let after = t.add(Some(cell), None, text("after"));
1369
1370 t.wrap_misplaced_list_items();
1371
1372 let group = t.items[cell].children[1];
1373 assert_eq!(t.items[cell].children, vec![before, group, after]);
1374 assert!(
1375 matches!(&t.items[group].kind, TreeKind::Group { label, name } if label == "list" && name == "group")
1376 );
1377 assert!(t.items[item].deleted, "the original item is deleted");
1378 let copy = t.items[group].children[0];
1379 assert_ne!(copy, item);
1380 assert!(
1381 copy > after,
1382 "the copy is numbered after every existing item"
1383 );
1384 assert_eq!(t.items[copy].children, vec![inline]);
1385 assert_eq!(t.items[inline].parent, Some(copy));
1386 assert_eq!(t.items[inline].children, vec![run_a, run_b]);
1387 for id in [inline, run_a, run_b] {
1388 assert!(!t.items[id].deleted, "item {id} must survive the re-homing");
1389 }
1390 }
1391}