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