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 /// Further predictions after `classification`, in order: the other
95 /// plot types of a PPTX combination chart (docling#4773).
96 extra_classes: Vec<String>,
97 /// The picture-OCR enrichment's text (#645), serialized like the flat
98 /// node's: `meta.description` + the `description` annotation.
99 description: Option<crate::PictureDescription>,
100 /// The prediction's `confidence`, when the backend writes one: the
101 /// DocLang deserializer stamps `1.0`; the office and HTML backends
102 /// leave it out (`None`).
103 confidence: Option<f64>,
104 /// A native chart's data grid (docling's `meta.tabular_chart.chart_data`,
105 /// the series reconstructed as a `TableData`), for a DOCX chart drawing.
106 chart: Option<Table>,
107 /// The `ImageRef.dpi` docling writes for `image` when the backend
108 /// read one from the file (python-pptx's `Image.dpi`: PIL's `dpi`
109 /// info, rounded, 72 when absent or out of 1–2048); `None` → 72,
110 /// which is what upstream's other office backends pass.
111 dpi: Option<u32>,
112 },
113 /// A form key-value region (`field_regions` / `field_items`).
114 FieldRegion { items: Vec<FieldItem> },
115 /// A `KeyValueItem` (`key_value_items`): docling's `GraphData` of key and
116 /// value cells and their links, written verbatim.
117 KeyValueGraph {
118 cells: Vec<crate::GraphCell>,
119 links: Vec<crate::GraphLink>,
120 },
121}
122
123/// docling's `ProvenanceItem` for a tree item, written verbatim: the
124/// backend's own geometry in the page's units — a PPTX shape's EMU box,
125/// whose `pages` entry is the slide size in EMU — rather than the 0–511
126/// DocLang grid the flat [`Node::Located`](crate::Node::Located) carries
127/// (which cannot round-trip those integers).
128#[derive(Debug, Clone, PartialEq)]
129pub struct TreeProv {
130 /// 1-based page (slide) number.
131 pub page_no: usize,
132 /// `[l, t, r, b]`, exactly as docling computed them.
133 pub bbox: [f64; 4],
134 /// docling's `coord_origin` tag. The office backends tag their
135 /// top-left-based boxes `TOPLEFT` (the PPTX backend since docling#4294 —
136 /// it used to tag them `BOTTOMLEFT`, which read the tuple as `(l, b, r,
137 /// t)` and swapped the vertical edges); a backend that really works in a
138 /// bottom-left space sets this.
139 pub bottom_left: bool,
140 /// `[0, len(text)]` in characters for a text item, `[0, 0]` for a table
141 /// or picture.
142 pub charspan: [usize; 2],
143}
144
145/// docling's `TrackSource` — where in a time-based track (a WebVTT cue) a
146/// text item came from. Written as the item's `source: [{"kind": "track", …}]`.
147#[derive(Debug, Clone, PartialEq)]
148pub struct TreeTrack {
149 /// The cue's start offset in seconds (docling's `WebVTTTimestamp.seconds`:
150 /// `h*3600 + m*60 + s + millis/1000.0`, so the float is bit-identical).
151 pub start_time: f64,
152 /// The cue's end offset in seconds.
153 pub end_time: f64,
154 /// The cue identifier line, when the cue has one.
155 pub identifier: Option<String>,
156 /// The `<v …>` voice annotation the text sits in, when any.
157 pub voice: Option<String>,
158}
159
160/// One item of an [`ItemTree`].
161#[derive(Debug, Clone, PartialEq)]
162pub struct TreeItem {
163 /// The parent item's index; `None` = the document body.
164 pub parent: Option<usize>,
165 /// Child item indices, in docling's `children` order.
166 pub children: Vec<usize>,
167 /// The content layer; `None` = `body`.
168 pub layer: Option<ContentLayer>,
169 pub kind: TreeKind,
170 /// The item's `prov` entry, when the backend has page geometry for it
171 /// (`None` → `prov: []`, what the HTML and DOCX backends write).
172 pub prov: Option<TreeProv>,
173 /// docling's `DocItem.comments`: the `comment_section` groups (or note
174 /// text items) annotating this item, as item indices — written after
175 /// `prov` when non-empty.
176 pub comments: Vec<usize>,
177 /// docling's `DocItem.source`: the track segment a text item was taken
178 /// from (WebVTT cues) — written after `prov` when set.
179 pub source: Option<TreeTrack>,
180 /// Removed by [`ItemTree::delete`] (docling's `delete_items`): the slot
181 /// stays so every other index keeps its meaning, but the item is not
182 /// numbered or written.
183 pub deleted: bool,
184 /// Footnotes / endnotes referenced from inside this text item (#538): the
185 /// note call's position (chars into the item's text) and the note's text.
186 /// docling keeps notes as unlinked furniture `footnote` items, so the
187 /// JSON never shows this; the Pandoc AST writes each as a `Note` there.
188 pub notes: Vec<TreeNote>,
189 /// This furniture `footnote` item is the body of a note some text item
190 /// calls (it travels in that item's [`Self::notes`]); the Pandoc AST then
191 /// leaves it out as a standalone block.
192 pub note_body: bool,
193}
194
195/// A note call inside a text item ([`TreeItem::notes`]).
196#[derive(Debug, Clone, PartialEq, Eq)]
197pub struct TreeNote {
198 /// The call's position, in chars into the item's `text`.
199 pub offset: usize,
200 /// The note's plain text.
201 pub text: String,
202}
203
204impl ItemTree {
205 /// Where each note call of one paragraph lands (#538): `full_text` is the
206 /// paragraph's text, `offsets` the calls' positions in it (chars), and
207 /// the paragraph's items are those created from `first_new` on. Each text
208 /// item is a trimmed slice of the paragraph (a formatting run, a link, or
209 /// the whole heading / list item), matched in order; a call inside an
210 /// item lands there, one between items ends the earlier (or starts the
211 /// first). When no item matches, the call ends the paragraph's last text
212 /// item; with no text item at all it is `None`.
213 pub fn place_note_calls(
214 &self,
215 first_new: usize,
216 full_text: &str,
217 offsets: &[usize],
218 ) -> Vec<Option<(usize, usize)>> {
219 let texts: Vec<(usize, &str)> = (first_new..self.items.len())
220 .filter(|&i| !self.items[i].deleted)
221 .filter_map(|i| match &self.items[i].kind {
222 TreeKind::Text { text, .. } | TreeKind::Code { text, .. } => {
223 Some((i, text.as_str()))
224 }
225 _ => None,
226 })
227 .collect();
228 // Each found item's (id, start, end) in chars of `full_text`.
229 let mut spans: Vec<(usize, usize, usize)> = Vec::new();
230 let mut cursor = 0usize; // bytes
231 for &(item, text) in &texts {
232 if text.is_empty() {
233 continue;
234 }
235 if let Some(pos) = full_text[cursor..].find(text) {
236 let start_b = cursor + pos;
237 let start = full_text[..start_b].chars().count();
238 spans.push((item, start, start + text.chars().count()));
239 cursor = start_b + text.len();
240 }
241 }
242 offsets
243 .iter()
244 .map(|&offset| {
245 spans
246 .iter()
247 .find(|&&(_, start, end)| offset >= start && offset <= end)
248 .map(|&(item, start, _)| (item, offset - start))
249 .or_else(
250 || match spans.iter().rev().find(|&&(_, _, end)| end <= offset) {
251 Some(&(item, start, end)) => Some((item, end - start)),
252 None => spans.first().map(|&(item, _, _)| (item, 0)),
253 },
254 )
255 .or_else(|| {
256 texts
257 .last()
258 .map(|&(item, text)| (item, text.chars().count()))
259 })
260 })
261 .collect()
262 }
263}
264
265/// docling's item tree in creation order (see the [module docs](self)).
266#[derive(Debug, Clone, PartialEq, Default)]
267pub struct ItemTree {
268 /// Every item, indexed by creation order — which is how docling numbers
269 /// `#/texts/N`, `#/groups/N`, … within each bucket.
270 pub items: Vec<TreeItem>,
271 /// The body's `children`, as item indices.
272 pub body: Vec<usize>,
273}
274
275impl ItemTree {
276 /// Append an item under `parent` (`None` = body) on `layer`, registering
277 /// it as its parent's last child — docling's `add_*` calls do exactly that.
278 pub fn add(
279 &mut self,
280 parent: Option<usize>,
281 layer: Option<ContentLayer>,
282 kind: TreeKind,
283 ) -> usize {
284 let id = self.items.len();
285 self.items.push(TreeItem {
286 parent,
287 children: Vec::new(),
288 layer,
289 kind,
290 prov: None,
291 comments: Vec::new(),
292 source: None,
293 deleted: false,
294 notes: Vec::new(),
295 note_body: false,
296 });
297 match parent {
298 Some(p) => self.items[p].children.push(id),
299 None => self.body.push(id),
300 }
301 id
302 }
303
304 /// [`add`](Self::add) with the item's provenance — docling's
305 /// `add_text(…, prov=prov)`.
306 pub fn add_with_prov(
307 &mut self,
308 parent: Option<usize>,
309 layer: Option<ContentLayer>,
310 kind: TreeKind,
311 prov: TreeProv,
312 ) -> usize {
313 let id = self.add(parent, layer, kind);
314 self.items[id].prov = Some(prov);
315 id
316 }
317
318 /// Append every item of `other` after this tree's, renumbering its
319 /// indices (parents, children, comments, table/picture caption and
320 /// rich-cell refs) and adding its body children to this body — so a
321 /// backend can build independent fragments in parallel (one per PPTX
322 /// slide) and still hand the export one tree in creation order, exactly
323 /// as if it had been built sequentially.
324 pub fn append(&mut self, other: ItemTree) {
325 let off = self.items.len();
326 let shift = |i: usize| i + off;
327 for mut item in other.items {
328 item.parent = item.parent.map(shift);
329 for c in item.children.iter_mut().chain(item.comments.iter_mut()) {
330 *c = shift(*c);
331 }
332 match &mut item.kind {
333 TreeKind::Table {
334 rich_cells,
335 captions,
336 ..
337 } => {
338 for (_, _, g) in rich_cells.iter_mut() {
339 *g = shift(*g);
340 }
341 for c in captions.iter_mut() {
342 *c = shift(*c);
343 }
344 }
345 TreeKind::Picture { captions, .. } => {
346 for c in captions.iter_mut() {
347 *c = shift(*c);
348 }
349 }
350 _ => {}
351 }
352 self.items.push(item);
353 }
354 self.body.extend(other.body.into_iter().map(shift));
355 }
356
357 /// Move `id` under `new_parent`, dropping it from its current parent's
358 /// children and appending it to the new one's — docling's
359 /// `group_cell_elements` re-parenting of a rich cell's items.
360 pub fn reparent(&mut self, id: usize, new_parent: Option<usize>) {
361 let old = self.items[id].parent;
362 let siblings = match old {
363 Some(p) => &mut self.items[p].children,
364 None => &mut self.body,
365 };
366 siblings.retain(|&c| c != id);
367 self.items[id].parent = new_parent;
368 match new_parent {
369 Some(p) => self.items[p].children.push(id),
370 None => self.body.push(id),
371 }
372 }
373
374 /// Re-number the items in traversal order — a pre-order walk of the body
375 /// through every layer, which is how docling's
376 /// `DoclingDocument.concatenate` (and `_normalize_references`) re-creates
377 /// a document's items: a group created after the content it was later
378 /// wrapped around comes before that content afterwards. Items the walk
379 /// does not reach (deleted ones) are dropped. Returns each old id's new
380 /// id.
381 pub fn renumber_in_traversal_order(&mut self) -> Vec<Option<usize>> {
382 let mut order = Vec::with_capacity(self.items.len());
383 let mut stack: Vec<usize> = self.body.iter().rev().copied().collect();
384 while let Some(id) = stack.pop() {
385 if self.items[id].deleted {
386 continue;
387 }
388 order.push(id);
389 stack.extend(self.items[id].children.iter().rev());
390 }
391 let mut new_of: Vec<Option<usize>> = vec![None; self.items.len()];
392 for (new, &old) in order.iter().enumerate() {
393 new_of[old] = Some(new);
394 }
395 let remap = |ids: &mut Vec<usize>| {
396 *ids = ids.iter().filter_map(|&i| new_of[i]).collect();
397 };
398 let mut old_items: Vec<Option<TreeItem>> = std::mem::take(&mut self.items)
399 .into_iter()
400 .map(Some)
401 .collect();
402 for &old in &order {
403 let mut item = old_items[old].take().expect("each item visited once");
404 item.parent = item.parent.and_then(|p| new_of[p]);
405 remap(&mut item.children);
406 remap(&mut item.comments);
407 match &mut item.kind {
408 TreeKind::Table {
409 rich_cells,
410 captions,
411 ..
412 } => {
413 rich_cells.retain_mut(|(_, _, g)| match new_of[*g] {
414 Some(n) => {
415 *g = n;
416 true
417 }
418 None => false,
419 });
420 remap(captions);
421 }
422 TreeKind::Picture { captions, .. } => remap(captions),
423 _ => {}
424 }
425 self.items.push(item);
426 }
427 remap(&mut self.body);
428 new_of
429 }
430
431 /// Remove `id` from the tree — docling's `delete_items`, which the DOCX
432 /// backend uses to drop the empty text item a blank spacer paragraph left
433 /// between two items of a resumed list. The item leaves its parent's
434 /// children and is neither numbered nor written; its slot stays so the
435 /// indices held elsewhere stay valid.
436 pub fn delete(&mut self, id: usize) {
437 match self.items[id].parent {
438 Some(p) => self.items[p].children.retain(|&c| c != id),
439 None => self.body.retain(|&c| c != id),
440 }
441 self.items[id].deleted = true;
442 }
443
444 /// docling-core's `DoclingDocument.validate_misplaced_list_items` (a
445 /// model validator, so it runs whenever docling-core serializes or loads
446 /// a document): every `list_item` whose parent is not a `list` group is
447 /// re-homed into a new one. A pre-order walk of the body (groups
448 /// included) collects them; consecutive misplaced items directly on the
449 /// body share one group, any other misplaced item gets its own. Working
450 /// from the last run back, each run gets a `ListGroup` (name `group`)
451 /// inserted where its first item stood, the items are deleted and
452 /// re-added under the group as fresh items, so they move to the end of
453 /// the text numbering (#527: the DOCX backend leaves such items in rich
454 /// table cells). A no-op for a well-formed tree.
455 ///
456 /// One deliberate divergence (#586): docling-core deletes each item *with
457 /// its children* and re-adds it from its text alone, so a mixed-format
458 /// item — an empty `list_item` over an `inline` group of text runs —
459 /// comes back empty and its text is gone from the JSON (and from the
460 /// Markdown/HTML docling serializes after that validator ran; the JSON
461 /// docling saves *before* exporting still has it). Here the children
462 /// follow the item into the group: the structure docling-core requires,
463 /// the content the document had.
464 pub fn wrap_misplaced_list_items(&mut self) {
465 let is_list_item = |t: &Self, id: usize| matches!(&t.items[id].kind, TreeKind::Text { label, .. } if label == "list_item");
466 let in_list_group = |t: &Self, id: usize| {
467 t.items[id].parent.is_some_and(
468 |p| matches!(&t.items[p].kind, TreeKind::Group { label, .. } if label == "list"),
469 )
470 };
471 let mut runs: Vec<Vec<usize>> = Vec::new();
472 // `None` = the body itself, which the walk yields first.
473 let mut prev: Option<usize> = None;
474 let mut stack: Vec<usize> = self.body.iter().rev().copied().collect();
475 while let Some(id) = stack.pop() {
476 if self.items[id].deleted {
477 continue;
478 }
479 if is_list_item(self, id) && !in_list_group(self, id) {
480 let continues =
481 prev.is_some_and(|p| is_list_item(self, p) && self.items[p].parent.is_none());
482 match runs.last_mut() {
483 Some(run) if continues => run.push(id),
484 _ => runs.push(vec![id]),
485 }
486 }
487 prev = Some(id);
488 stack.extend(self.items[id].children.iter().rev().copied());
489 }
490 for run in runs.into_iter().rev() {
491 let parent = self.items[run[0]].parent;
492 let group = self.add(
493 parent,
494 None,
495 TreeKind::Group {
496 label: "list".into(),
497 name: "group".into(),
498 },
499 );
500 let siblings = match parent {
501 Some(p) => &mut self.items[p].children,
502 None => &mut self.body,
503 };
504 siblings.pop();
505 let at = siblings
506 .iter()
507 .position(|&c| c == run[0])
508 .unwrap_or(siblings.len());
509 siblings.insert(at, group);
510 for &li in &run {
511 // Not `delete_subtree`: the children move to the copy (#586).
512 self.delete(li);
513 }
514 // `add_list_item` keeps the text, marker, formatting, hyperlink
515 // and first provenance — not comments or a source. The children
516 // (the inline group of a mixed-format item) are carried over.
517 for &li in &run {
518 let children = std::mem::take(&mut self.items[li].children);
519 let copy = TreeItem {
520 parent: Some(group),
521 children: children.clone(),
522 comments: Vec::new(),
523 source: None,
524 deleted: false,
525 ..self.items[li].clone()
526 };
527 let id = self.items.len();
528 self.items.push(copy);
529 for c in children {
530 self.items[c].parent = Some(id);
531 }
532 self.items[group].children.push(id);
533 }
534 }
535 }
536
537 /// The last live text-bucket item (docling's `doc.texts[-1]`).
538 pub fn last_text(&self) -> Option<usize> {
539 self.items.iter().rposition(|it| {
540 !it.deleted && matches!(it.kind, TreeKind::Text { .. } | TreeKind::Code { .. })
541 })
542 }
543
544 /// How many items of a bucket precede `id` — its `#/{bucket}/N` index.
545 pub fn bucket_index(&self, id: usize) -> usize {
546 let same = |k: &TreeKind| {
547 std::mem::discriminant(k) == std::mem::discriminant(&self.items[id].kind)
548 || matches!(
549 (k, &self.items[id].kind),
550 (TreeKind::Text { .. }, TreeKind::Code { .. })
551 | (TreeKind::Code { .. }, TreeKind::Text { .. })
552 )
553 };
554 self.items[..id]
555 .iter()
556 .filter(|it| !it.deleted && same(&it.kind))
557 .count()
558 }
559
560 /// The number of tables created so far (docling's `len(doc.tables)`).
561 pub fn table_count(&self) -> usize {
562 self.items
563 .iter()
564 .filter(|it| !it.deleted && matches!(it.kind, TreeKind::Table { .. }))
565 .count()
566 }
567}
568
569#[cfg(test)]
570mod tests {
571 use super::*;
572
573 fn text(t: &str) -> TreeKind {
574 TreeKind::Text {
575 label: "text".into(),
576 text: t.into(),
577 orig: None,
578 formatting: None,
579 hyperlink: None,
580 level: None,
581 list: None,
582 }
583 }
584
585 /// `add` registers the item as its parent's (or the body's) last child;
586 /// `reparent` moves it — a rich cell's items leave the heading they were
587 /// created under for the table's group.
588 #[test]
589 fn add_and_reparent_keep_docling_children_order() {
590 let mut t = ItemTree::default();
591 let title = t.add(None, None, text("Title"));
592 let a = t.add(Some(title), None, text("a"));
593 let b = t.add(Some(title), None, text("b"));
594 let table = t.add(
595 Some(title),
596 None,
597 TreeKind::Table {
598 table: Table::default(),
599 rich_cells: Vec::new(),
600 captions: Vec::new(),
601 },
602 );
603 let group = t.add(
604 Some(table),
605 None,
606 TreeKind::Group {
607 label: "unspecified".into(),
608 name: "rich_cell_group_1_0_0".into(),
609 },
610 );
611 assert_eq!(t.body, vec![title]);
612 assert_eq!(t.items[title].children, vec![a, b, table]);
613 t.reparent(a, Some(group));
614 assert_eq!(t.items[title].children, vec![b, table]);
615 assert_eq!(t.items[group].children, vec![a]);
616 assert_eq!(t.items[a].parent, Some(group));
617 assert_eq!(t.table_count(), 1);
618 // Text and code share the `texts` bucket.
619 let code = t.add(
620 None,
621 None,
622 TreeKind::Code {
623 text: "x".into(),
624 orig: None,
625 language: None,
626 formatting: None,
627 hyperlink: None,
628 },
629 );
630 assert_eq!(t.bucket_index(code), 3, "title, a, b precede it in `texts`");
631 assert_eq!(t.bucket_index(group), 0);
632 assert_eq!(t.body, vec![title, code]);
633 }
634
635 /// `append` renumbers a fragment built on its own (a slide converted in
636 /// parallel) so the merged tree reads as if built in one pass: parents,
637 /// children, comment back-refs and caption refs all shift together.
638 #[test]
639 fn append_renumbers_a_fragment_into_creation_order() {
640 let mut whole = ItemTree::default();
641 let slide0 = whole.add(
642 None,
643 None,
644 TreeKind::Group {
645 label: "chapter".into(),
646 name: "slide-0".into(),
647 },
648 );
649 whole.add(Some(slide0), None, text("first"));
650
651 let mut frag = ItemTree::default();
652 let slide1 = frag.add(
653 None,
654 None,
655 TreeKind::Group {
656 label: "chapter".into(),
657 name: "slide-1".into(),
658 },
659 );
660 let cap = frag.add_with_prov(
661 Some(slide1),
662 None,
663 TreeKind::Text {
664 label: "caption".into(),
665 text: "Title".into(),
666 orig: None,
667 formatting: None,
668 hyperlink: None,
669 level: None,
670 list: None,
671 },
672 TreeProv {
673 page_no: 2,
674 bbox: [1.0, 2.0, 3.0, 4.0],
675 bottom_left: true,
676 charspan: [0, 5],
677 },
678 );
679 let pic = frag.add(
680 Some(slide1),
681 None,
682 TreeKind::Picture {
683 captions: vec![cap],
684 image: None,
685 extra_classes: Vec::new(),
686 classification: Some("bar_chart".into()),
687 description: None,
688 confidence: None,
689 chart: None,
690 dpi: None,
691 },
692 );
693 let note = frag.add(
694 None,
695 Some(ContentLayer::Notes),
696 TreeKind::Group {
697 label: "comment_section".into(),
698 name: "comment-slide2-1".into(),
699 },
700 );
701 frag.items[pic].comments.push(note);
702
703 whole.append(frag);
704 assert_eq!(whole.body, vec![slide0, 2, 5]);
705 assert_eq!(whole.items[2].children, vec![3, 4]);
706 assert_eq!(whole.items[3].parent, Some(2));
707 assert_eq!(whole.items[3].prov.as_ref().map(|p| p.page_no), Some(2));
708 assert!(
709 matches!(&whole.items[4].kind, TreeKind::Picture { captions, .. } if captions == &[3])
710 );
711 assert_eq!(whole.items[4].comments, vec![5]);
712 assert_eq!(whole.items[5].parent, None);
713 assert_eq!(
714 whole.bucket_index(4),
715 0,
716 "the fragment's picture is #/pictures/0"
717 );
718 assert_eq!(
719 whole.bucket_index(5),
720 2,
721 "slide-0, slide-1 precede it in `groups`"
722 );
723 }
724
725 /// `renumber_in_traversal_order`: docling's `concatenate` re-creates the
726 /// items as a pre-order walk meets them, so a group created after the
727 /// content it was wrapped around (a rich cell's group) comes first, and a
728 /// deleted item disappears; every cross-reference follows.
729 #[test]
730 fn renumbering_follows_the_traversal() {
731 let mut t = ItemTree::default();
732 let a = t.add(None, None, text("a"));
733 let table = t.add(
734 None,
735 None,
736 TreeKind::Table {
737 table: Table::default(),
738 rich_cells: Vec::new(),
739 captions: Vec::new(),
740 },
741 );
742 let cell_text = t.add(None, None, text("cell"));
743 let group = t.add(
744 Some(table),
745 None,
746 TreeKind::Group {
747 label: "unspecified".into(),
748 name: "rich_cell_group_1_0_0".into(),
749 },
750 );
751 t.reparent(cell_text, Some(group));
752 if let TreeKind::Table { rich_cells, .. } = &mut t.items[table].kind {
753 rich_cells.push((0, 0, group));
754 }
755 let gone = t.add(None, None, text("gone"));
756 t.delete(gone);
757 let z = t.add(None, None, text("z"));
758
759 let new_of = t.renumber_in_traversal_order();
760 assert_eq!(
761 new_of,
762 vec![Some(0), Some(1), Some(3), Some(2), None, Some(4)]
763 );
764 assert_eq!(t.items.len(), 5);
765 assert_eq!(t.body, vec![0, 1, 4]);
766 assert_eq!(t.items[1].children, vec![2], "the group follows its table");
767 assert_eq!(t.items[2].parent, Some(1));
768 assert_eq!(
769 t.items[3].parent,
770 Some(2),
771 "the cell text follows its group"
772 );
773 assert!(matches!(&t.items[3].kind, TreeKind::Text { text, .. } if text == "cell"));
774 assert!(
775 matches!(&t.items[1].kind, TreeKind::Table { rich_cells, .. } if rich_cells == &[(0, 0, 2)])
776 );
777 let _ = (a, z);
778 }
779
780 /// #586: a misplaced `list_item` keeps its children when it is re-homed.
781 /// docling-core's `validate_misplaced_list_items` re-adds the item from
782 /// its text alone, so a mixed-format item (empty `list_item` over an
783 /// `inline` group of runs) lost every run — a DOCX table cell whose list
784 /// paragraph followed a `numId 0` spacer came out as an empty bullet in
785 /// the JSON and the HTML. The group goes where the item stood, the copy
786 /// is numbered last, the inline group and its texts move under it.
787 #[test]
788 fn wrapping_a_misplaced_list_item_keeps_its_runs() {
789 let mut t = ItemTree::default();
790 let cell = t.add(
791 None,
792 None,
793 TreeKind::Group {
794 label: "unspecified".into(),
795 name: "rich_cell_group_1_0_1".into(),
796 },
797 );
798 let before = t.add(Some(cell), None, text("before"));
799 let item = t.add(
800 Some(cell),
801 None,
802 TreeKind::Text {
803 label: "list_item".into(),
804 text: String::new(),
805 orig: None,
806 formatting: None,
807 hyperlink: None,
808 level: None,
809 list: Some(ListMeta {
810 enumerated: false,
811 marker: String::new(),
812 }),
813 },
814 );
815 let inline = t.add(
816 Some(item),
817 None,
818 TreeKind::Group {
819 label: "inline".into(),
820 name: "group".into(),
821 },
822 );
823 let run_a = t.add(Some(inline), None, text("Second item text"));
824 let run_b = t.add(Some(inline), None, text("[Optional]"));
825 let after = t.add(Some(cell), None, text("after"));
826
827 t.wrap_misplaced_list_items();
828
829 let group = t.items[cell].children[1];
830 assert_eq!(t.items[cell].children, vec![before, group, after]);
831 assert!(
832 matches!(&t.items[group].kind, TreeKind::Group { label, name } if label == "list" && name == "group")
833 );
834 assert!(t.items[item].deleted, "the original item is deleted");
835 let copy = t.items[group].children[0];
836 assert_ne!(copy, item);
837 assert!(
838 copy > after,
839 "the copy is numbered after every existing item"
840 );
841 assert_eq!(t.items[copy].children, vec![inline]);
842 assert_eq!(t.items[inline].parent, Some(copy));
843 assert_eq!(t.items[inline].children, vec![run_a, run_b]);
844 for id in [inline, run_a, run_b] {
845 assert!(!t.items[id].deleted, "item {id} must survive the re-homing");
846 }
847 }
848}