Skip to main content

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}