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 },
74 /// A `GroupItem`: `label` is docling's `GroupLabel` value (`inline`,
75 /// `list`, `section`, `unspecified`, …), `name` its name (`group`, `list`,
76 /// `ordered list`, `header-2`, `rich_cell_group_1_0_3`, …).
77 Group { label: String, name: String },
78 /// A `TableItem`. `rich_cells` marks the cells docling serialized as a
79 /// `RichTableCell`: `(row, col)` grid anchor → the group item (a child of
80 /// the table) that holds the cell's content. `captions` are caption text
81 /// items in the tree.
82 Table {
83 table: Table,
84 rich_cells: Vec<(usize, usize, usize)>,
85 captions: Vec<usize>,
86 },
87 /// A `PictureItem`, its caption text items and optional payload.
88 /// `classification` is a `PictureClassificationLabel` value written as
89 /// the picture's `meta.classification` (an HTML `<stamp>` / `<signature>`).
90 Picture {
91 captions: Vec<usize>,
92 image: Option<PictureImage>,
93 classification: Option<String>,
94 /// A native chart's data grid (docling's `meta.tabular_chart.chart_data`,
95 /// the series reconstructed as a `TableData`), for a DOCX chart drawing.
96 chart: Option<Table>,
97 /// The `ImageRef.dpi` docling writes for `image` when the backend
98 /// read one from the file (python-pptx's `Image.dpi`: PIL's `dpi`
99 /// info, rounded, 72 when absent or out of 1–2048); `None` → 72,
100 /// which is what upstream's other office backends pass.
101 dpi: Option<u32>,
102 },
103 /// A form key-value region (`field_regions` / `field_items`).
104 FieldRegion { items: Vec<FieldItem> },
105}
106
107/// docling's `ProvenanceItem` for a tree item, written verbatim: the
108/// backend's own geometry in the page's units — a PPTX shape's EMU box,
109/// whose `pages` entry is the slide size in EMU — rather than the 0–511
110/// DocLang grid the flat [`Node::Located`](crate::Node::Located) carries
111/// (which cannot round-trip those integers).
112#[derive(Debug, Clone, PartialEq)]
113pub struct TreeProv {
114 /// 1-based page (slide) number.
115 pub page_no: usize,
116 /// `[l, t, r, b]`, exactly as docling computed them.
117 pub bbox: [f64; 4],
118 /// docling's `coord_origin` tag. `MsPowerpointDocumentBackend` builds a
119 /// shape's box with `BoundingBox.from_tuple(…, BOTTOMLEFT)` — which reads
120 /// the tuple as `(l, b, r, t)`, so the shape's top EMU lands in `b` — a
121 /// quirk the JSON keeps; a speaker note's zero box is `TOPLEFT`
122 /// (`BoundingBox`'s default).
123 pub bottom_left: bool,
124 /// `[0, len(text)]` in characters for a text item, `[0, 0]` for a table
125 /// or picture.
126 pub charspan: [usize; 2],
127}
128
129/// docling's `TrackSource` — where in a time-based track (a WebVTT cue) a
130/// text item came from. Written as the item's `source: [{"kind": "track", …}]`.
131#[derive(Debug, Clone, PartialEq)]
132pub struct TreeTrack {
133 /// The cue's start offset in seconds (docling's `WebVTTTimestamp.seconds`:
134 /// `h*3600 + m*60 + s + millis/1000.0`, so the float is bit-identical).
135 pub start_time: f64,
136 /// The cue's end offset in seconds.
137 pub end_time: f64,
138 /// The cue identifier line, when the cue has one.
139 pub identifier: Option<String>,
140 /// The `<v …>` voice annotation the text sits in, when any.
141 pub voice: Option<String>,
142}
143
144/// One item of an [`ItemTree`].
145#[derive(Debug, Clone, PartialEq)]
146pub struct TreeItem {
147 /// The parent item's index; `None` = the document body.
148 pub parent: Option<usize>,
149 /// Child item indices, in docling's `children` order.
150 pub children: Vec<usize>,
151 /// The content layer; `None` = `body`.
152 pub layer: Option<ContentLayer>,
153 pub kind: TreeKind,
154 /// The item's `prov` entry, when the backend has page geometry for it
155 /// (`None` → `prov: []`, what the HTML and DOCX backends write).
156 pub prov: Option<TreeProv>,
157 /// docling's `DocItem.comments`: the `comment_section` groups (or note
158 /// text items) annotating this item, as item indices — written after
159 /// `prov` when non-empty.
160 pub comments: Vec<usize>,
161 /// docling's `DocItem.source`: the track segment a text item was taken
162 /// from (WebVTT cues) — written after `prov` when set.
163 pub source: Option<TreeTrack>,
164 /// Removed by [`ItemTree::delete`] (docling's `delete_items`): the slot
165 /// stays so every other index keeps its meaning, but the item is not
166 /// numbered or written.
167 pub deleted: bool,
168}
169
170/// docling's item tree in creation order (see the [module docs](self)).
171#[derive(Debug, Clone, PartialEq, Default)]
172pub struct ItemTree {
173 /// Every item, indexed by creation order — which is how docling numbers
174 /// `#/texts/N`, `#/groups/N`, … within each bucket.
175 pub items: Vec<TreeItem>,
176 /// The body's `children`, as item indices.
177 pub body: Vec<usize>,
178}
179
180impl ItemTree {
181 /// Append an item under `parent` (`None` = body) on `layer`, registering
182 /// it as its parent's last child — docling's `add_*` calls do exactly that.
183 pub fn add(
184 &mut self,
185 parent: Option<usize>,
186 layer: Option<ContentLayer>,
187 kind: TreeKind,
188 ) -> usize {
189 let id = self.items.len();
190 self.items.push(TreeItem {
191 parent,
192 children: Vec::new(),
193 layer,
194 kind,
195 prov: None,
196 comments: Vec::new(),
197 source: None,
198 deleted: false,
199 });
200 match parent {
201 Some(p) => self.items[p].children.push(id),
202 None => self.body.push(id),
203 }
204 id
205 }
206
207 /// [`add`](Self::add) with the item's provenance — docling's
208 /// `add_text(…, prov=prov)`.
209 pub fn add_with_prov(
210 &mut self,
211 parent: Option<usize>,
212 layer: Option<ContentLayer>,
213 kind: TreeKind,
214 prov: TreeProv,
215 ) -> usize {
216 let id = self.add(parent, layer, kind);
217 self.items[id].prov = Some(prov);
218 id
219 }
220
221 /// Append every item of `other` after this tree's, renumbering its
222 /// indices (parents, children, comments, table/picture caption and
223 /// rich-cell refs) and adding its body children to this body — so a
224 /// backend can build independent fragments in parallel (one per PPTX
225 /// slide) and still hand the export one tree in creation order, exactly
226 /// as if it had been built sequentially.
227 pub fn append(&mut self, other: ItemTree) {
228 let off = self.items.len();
229 let shift = |i: usize| i + off;
230 for mut item in other.items {
231 item.parent = item.parent.map(shift);
232 for c in item.children.iter_mut().chain(item.comments.iter_mut()) {
233 *c = shift(*c);
234 }
235 match &mut item.kind {
236 TreeKind::Table {
237 rich_cells,
238 captions,
239 ..
240 } => {
241 for (_, _, g) in rich_cells.iter_mut() {
242 *g = shift(*g);
243 }
244 for c in captions.iter_mut() {
245 *c = shift(*c);
246 }
247 }
248 TreeKind::Picture { captions, .. } => {
249 for c in captions.iter_mut() {
250 *c = shift(*c);
251 }
252 }
253 _ => {}
254 }
255 self.items.push(item);
256 }
257 self.body.extend(other.body.into_iter().map(shift));
258 }
259
260 /// Move `id` under `new_parent`, dropping it from its current parent's
261 /// children and appending it to the new one's — docling's
262 /// `group_cell_elements` re-parenting of a rich cell's items.
263 pub fn reparent(&mut self, id: usize, new_parent: Option<usize>) {
264 let old = self.items[id].parent;
265 let siblings = match old {
266 Some(p) => &mut self.items[p].children,
267 None => &mut self.body,
268 };
269 siblings.retain(|&c| c != id);
270 self.items[id].parent = new_parent;
271 match new_parent {
272 Some(p) => self.items[p].children.push(id),
273 None => self.body.push(id),
274 }
275 }
276
277 /// Remove `id` from the tree — docling's `delete_items`, which the DOCX
278 /// backend uses to drop the empty text item a blank spacer paragraph left
279 /// between two items of a resumed list. The item leaves its parent's
280 /// children and is neither numbered nor written; its slot stays so the
281 /// indices held elsewhere stay valid.
282 pub fn delete(&mut self, id: usize) {
283 match self.items[id].parent {
284 Some(p) => self.items[p].children.retain(|&c| c != id),
285 None => self.body.retain(|&c| c != id),
286 }
287 self.items[id].deleted = true;
288 }
289
290 /// The last live text-bucket item (docling's `doc.texts[-1]`).
291 pub fn last_text(&self) -> Option<usize> {
292 self.items.iter().rposition(|it| {
293 !it.deleted && matches!(it.kind, TreeKind::Text { .. } | TreeKind::Code { .. })
294 })
295 }
296
297 /// How many items of a bucket precede `id` — its `#/{bucket}/N` index.
298 pub fn bucket_index(&self, id: usize) -> usize {
299 let same = |k: &TreeKind| {
300 std::mem::discriminant(k) == std::mem::discriminant(&self.items[id].kind)
301 || matches!(
302 (k, &self.items[id].kind),
303 (TreeKind::Text { .. }, TreeKind::Code { .. })
304 | (TreeKind::Code { .. }, TreeKind::Text { .. })
305 )
306 };
307 self.items[..id]
308 .iter()
309 .filter(|it| !it.deleted && same(&it.kind))
310 .count()
311 }
312
313 /// The number of tables created so far (docling's `len(doc.tables)`).
314 pub fn table_count(&self) -> usize {
315 self.items
316 .iter()
317 .filter(|it| !it.deleted && matches!(it.kind, TreeKind::Table { .. }))
318 .count()
319 }
320}
321
322#[cfg(test)]
323mod tests {
324 use super::*;
325
326 fn text(t: &str) -> TreeKind {
327 TreeKind::Text {
328 label: "text".into(),
329 text: t.into(),
330 orig: None,
331 formatting: None,
332 hyperlink: None,
333 level: None,
334 list: None,
335 }
336 }
337
338 /// `add` registers the item as its parent's (or the body's) last child;
339 /// `reparent` moves it — a rich cell's items leave the heading they were
340 /// created under for the table's group.
341 #[test]
342 fn add_and_reparent_keep_docling_children_order() {
343 let mut t = ItemTree::default();
344 let title = t.add(None, None, text("Title"));
345 let a = t.add(Some(title), None, text("a"));
346 let b = t.add(Some(title), None, text("b"));
347 let table = t.add(
348 Some(title),
349 None,
350 TreeKind::Table {
351 table: Table::default(),
352 rich_cells: Vec::new(),
353 captions: Vec::new(),
354 },
355 );
356 let group = t.add(
357 Some(table),
358 None,
359 TreeKind::Group {
360 label: "unspecified".into(),
361 name: "rich_cell_group_1_0_0".into(),
362 },
363 );
364 assert_eq!(t.body, vec![title]);
365 assert_eq!(t.items[title].children, vec![a, b, table]);
366 t.reparent(a, Some(group));
367 assert_eq!(t.items[title].children, vec![b, table]);
368 assert_eq!(t.items[group].children, vec![a]);
369 assert_eq!(t.items[a].parent, Some(group));
370 assert_eq!(t.table_count(), 1);
371 // Text and code share the `texts` bucket.
372 let code = t.add(
373 None,
374 None,
375 TreeKind::Code {
376 text: "x".into(),
377 orig: None,
378 language: None,
379 formatting: None,
380 hyperlink: None,
381 },
382 );
383 assert_eq!(t.bucket_index(code), 3, "title, a, b precede it in `texts`");
384 assert_eq!(t.bucket_index(group), 0);
385 assert_eq!(t.body, vec![title, code]);
386 }
387
388 /// `append` renumbers a fragment built on its own (a slide converted in
389 /// parallel) so the merged tree reads as if built in one pass: parents,
390 /// children, comment back-refs and caption refs all shift together.
391 #[test]
392 fn append_renumbers_a_fragment_into_creation_order() {
393 let mut whole = ItemTree::default();
394 let slide0 = whole.add(
395 None,
396 None,
397 TreeKind::Group {
398 label: "chapter".into(),
399 name: "slide-0".into(),
400 },
401 );
402 whole.add(Some(slide0), None, text("first"));
403
404 let mut frag = ItemTree::default();
405 let slide1 = frag.add(
406 None,
407 None,
408 TreeKind::Group {
409 label: "chapter".into(),
410 name: "slide-1".into(),
411 },
412 );
413 let cap = frag.add_with_prov(
414 Some(slide1),
415 None,
416 TreeKind::Text {
417 label: "caption".into(),
418 text: "Title".into(),
419 orig: None,
420 formatting: None,
421 hyperlink: None,
422 level: None,
423 list: None,
424 },
425 TreeProv {
426 page_no: 2,
427 bbox: [1.0, 2.0, 3.0, 4.0],
428 bottom_left: true,
429 charspan: [0, 5],
430 },
431 );
432 let pic = frag.add(
433 Some(slide1),
434 None,
435 TreeKind::Picture {
436 captions: vec![cap],
437 image: None,
438 classification: Some("bar_chart".into()),
439 chart: None,
440 dpi: None,
441 },
442 );
443 let note = frag.add(
444 None,
445 Some(ContentLayer::Notes),
446 TreeKind::Group {
447 label: "comment_section".into(),
448 name: "comment-slide2-1".into(),
449 },
450 );
451 frag.items[pic].comments.push(note);
452
453 whole.append(frag);
454 assert_eq!(whole.body, vec![slide0, 2, 5]);
455 assert_eq!(whole.items[2].children, vec![3, 4]);
456 assert_eq!(whole.items[3].parent, Some(2));
457 assert_eq!(whole.items[3].prov.as_ref().map(|p| p.page_no), Some(2));
458 assert!(
459 matches!(&whole.items[4].kind, TreeKind::Picture { captions, .. } if captions == &[3])
460 );
461 assert_eq!(whole.items[4].comments, vec![5]);
462 assert_eq!(whole.items[5].parent, None);
463 assert_eq!(
464 whole.bucket_index(4),
465 0,
466 "the fragment's picture is #/pictures/0"
467 );
468 assert_eq!(
469 whole.bucket_index(5),
470 2,
471 "slide-0, slide-1 precede it in `groups`"
472 );
473 }
474}