use std::cmp::Ordering;
use std::hash::{Hash, Hasher};
use std::path::PathBuf;
use crate::error::{EngineError, OptionsError, Result};
use crate::lists::{self, Marker};
use crate::table_trace::{LearnedTrace, TableOrigin};
use crate::tables;
use crate::text::{is_hyphen_wrap_candidate, HorizontalRule, TextBlock, TextSpan};
const PARAGRAPH_LEADING_TOLERANCE: f64 = 1.35;
const MAX_LEADING_EM: f64 = 1.8;
const HANG_MAX_LEADING_EM: f64 = 2.2;
const MIN_BASELINE_STEP_EM: f64 = 0.25;
const COLUMN_OVERLAP_FRACTION: f64 = 0.35;
const SIZE_TOLERANCE: f64 = 0.10;
const SHORT_LINE_EM: f64 = 2.5;
const SAME_BASELINE: f64 = 1e-6;
const ROW_PITCH_FRACTION: f64 = 0.75;
const ROW_PITCH_JUMP: f64 = 1.4;
const ROW_PITCH_CLUSTER: usize = 2;
const CELL_LEFT_EM: f64 = 0.5;
const INDENT_MIN_EM: f64 = 0.8;
const INDENT_MATCH_EM: f64 = 0.35;
const TABULAR_GAP_EM: f64 = 3.0;
const INITIAL_MAX_CHARS: usize = 2;
const INITIAL_SIZE_RATIO: f64 = 1.8;
const RAISED_SIZE: f64 = 0.9;
const RAISED_RISE: f64 = 0.1;
const MAX_ORDINAL_CHARS: usize = 3;
const MARKER_GAP_EM: f64 = 0.4;
const MARKER_MAX_CHARS: usize = 2;
const NARROW_X0_EM: f64 = 0.5;
const NARROW_PITCH_MULT: f64 = 1.2;
const NARROW_SIZE_PT: f64 = 0.5;
pub(crate) const SOLID_PITCH_EM: f64 = 1.16;
#[derive(Debug, Clone, Copy, PartialEq, Default)]
pub struct GridDoubt {
pub thin_rows: usize,
pub fill: f64,
pub retried_from: usize,
pub full_rows: usize,
pub columns: usize,
}
impl Block {
pub fn new(kind: BlockKind, page: usize, bbox: [f64; 4], text: String, index: usize) -> Self {
Self {
kind,
page,
bbox,
text,
spans: Vec::new(),
index,
continues_previous: false,
confidence: None,
grid: None,
table_origin: TableOrigin::Other,
trace_learned: None,
}
}
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum BlockKind {
Paragraph,
Heading {
level: u8,
},
ListItem {
level: u8,
ordinal: Option<u32>,
},
TableCell {
row: u16,
column: u16,
row_span: u16,
column_span: u16,
header: bool,
},
Header,
Footer,
Caption,
Figure,
}
#[non_exhaustive]
#[derive(Debug, Clone)]
pub struct Block {
pub kind: BlockKind,
pub page: usize,
pub bbox: [f64; 4],
pub text: String,
pub spans: Vec<TextSpan>,
pub index: usize,
pub continues_previous: bool,
pub confidence: Option<f64>,
pub grid: Option<GridDoubt>,
pub(crate) table_origin: TableOrigin,
pub(crate) trace_learned: Option<LearnedTrace>,
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum PageSeparators {
#[default]
Comment,
None,
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum Quality {
#[default]
Fast,
Balanced,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct TatrOptions {
pub model_dir: Option<PathBuf>,
pub ort_dylib: Option<PathBuf>,
pub intra_threads: usize,
pub sessions_per_model: usize,
pub detector_regions_only: bool,
#[doc(hidden)]
pub test_hook: Option<TatrTestHook>,
}
impl Default for TatrOptions {
fn default() -> Self {
Self {
model_dir: None,
ort_dylib: None,
intra_threads: 4,
sessions_per_model: 1,
detector_regions_only: false,
test_hook: None,
}
}
}
impl TatrOptions {
#[cfg(feature = "ort-tables")]
pub(crate) fn runtime_config(&self) -> pdf_ocr::runtime::RuntimeConfig {
let mut config = pdf_ocr::runtime::RuntimeConfig::new()
.with_intra_threads(self.intra_threads)
.with_sessions_per_model(self.sessions_per_model);
if let Some(dir) = &self.model_dir {
config = config.with_model_dir(dir.clone());
}
if let Some(lib) = &self.ort_dylib {
config = config.with_ort_dylib(lib.clone());
}
config
}
}
#[doc(hidden)]
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum TatrTestHook {
Cells(Vec<TatrTestCell>),
Declined,
Failed,
}
#[doc(hidden)]
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct TatrTestCell {
pub rows: Vec<usize>,
pub columns: Vec<usize>,
pub header: bool,
pub words: Vec<usize>,
}
#[doc(hidden)]
impl TatrTestCell {
pub fn new(rows: Vec<usize>, columns: Vec<usize>, header: bool, words: Vec<usize>) -> Self {
Self {
rows,
columns,
header,
words,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct HeadingOverride {
pub text: String,
pub level: Option<u8>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct ExtractOptions {
pub first_page: usize,
pub page_count: Option<usize>,
pub pages: Option<Vec<usize>>,
pub learned: bool,
pub use_tags: bool,
pub document_font_names: bool,
pub include_headers: bool,
pub include_footers: bool,
pub page_separators: PageSeparators,
pub code: bool,
pub heading_overrides: Vec<HeadingOverride>,
pub include_hidden: bool,
pub raw_order: bool,
pub ocr: OcrMode,
pub ocr_language: String,
pub ocr_dpi: u32,
pub clip_margins: Option<ClipMargins>,
pub quality: Quality,
pub model_dir: Option<PathBuf>,
pub keep_furniture: bool,
pub word_boxes: bool,
tatr: Option<TatrOptions>,
pub include_figures: bool,
pub embed_figures: bool,
pub figure_image_dir: Option<PathBuf>,
pub drop_text_over_images: bool,
pub table_strategy: TableStrategy,
pub table_render_mode: TableRenderMode,
pub cell_path_words: bool,
pub actual_text: bool,
}
#[derive(Debug, Clone, Copy)]
pub struct ClipMargins([f64; 4]);
impl ClipMargins {
pub fn new(
left: f64,
top: f64,
right: f64,
bottom: f64,
) -> std::result::Result<Self, OptionsError> {
for (side, value) in [
("left", left),
("top", top),
("right", right),
("bottom", bottom),
] {
if !value.is_finite() || value < 0.0 {
return Err(OptionsError::InvalidClipMargins { side, value });
}
}
Ok(Self([left + 0.0, top + 0.0, right + 0.0, bottom + 0.0]))
}
pub fn as_array(&self) -> [f64; 4] {
self.0
}
}
impl PartialEq for ClipMargins {
fn eq(&self, other: &Self) -> bool {
self.0.map(f64::to_bits) == other.0.map(f64::to_bits)
}
}
impl Eq for ClipMargins {}
impl Hash for ClipMargins {
fn hash<H: Hasher>(&self, state: &mut H) {
self.0.map(f64::to_bits).hash(state);
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum OcrMode {
#[default]
Never,
Auto,
Force,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum TableStrategy {
Lines,
Text,
#[default]
Both,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum TableRenderMode {
#[default]
Auto,
Markdown,
Html,
}
impl Default for ExtractOptions {
fn default() -> Self {
Self {
first_page: 0,
page_count: None,
pages: None,
learned: true,
use_tags: false,
document_font_names: false,
include_headers: false,
include_footers: false,
page_separators: PageSeparators::Comment,
code: true,
heading_overrides: Vec::new(),
include_hidden: false,
raw_order: false,
ocr: OcrMode::Never,
ocr_language: "eng".to_string(),
ocr_dpi: 150,
clip_margins: None,
quality: Quality::Fast,
model_dir: None,
keep_furniture: false,
word_boxes: false,
tatr: None,
include_figures: true,
embed_figures: false,
figure_image_dir: None,
drop_text_over_images: false,
table_strategy: TableStrategy::Both,
table_render_mode: TableRenderMode::Auto,
cell_path_words: false,
actual_text: false,
}
}
}
impl ExtractOptions {
pub fn all() -> Self {
Self::default()
}
pub fn without_the_learned_pass(self) -> Self {
Self {
learned: false,
..self
}
}
pub fn with_tatr(self, tatr: TatrOptions) -> Self {
Self {
tatr: Some(tatr),
..self
}
}
pub(crate) fn tatr(&self) -> Option<&TatrOptions> {
self.tatr.as_ref()
}
pub fn window(first: usize, count: usize) -> Self {
Self {
first_page: first,
page_count: Some(count),
..Self::default()
}
}
#[must_use]
pub fn with_quality(mut self, quality: Quality) -> Self {
self.quality = quality;
self
}
#[must_use]
pub fn with_model_dir(mut self, dir: impl Into<PathBuf>) -> Self {
self.model_dir = Some(dir.into());
self
}
#[must_use]
pub fn with_keep_furniture(mut self, keep: bool) -> Self {
self.keep_furniture = keep;
self
}
pub(crate) fn holds(&self, page: usize) -> bool {
if let Some(pages) = &self.pages {
return pages.contains(&page);
}
if page < self.first_page {
return false;
}
match self.page_count {
None => true,
Some(count) => page - self.first_page < count,
}
}
pub(crate) fn is_whole_document(&self) -> bool {
self.first_page == 0 && self.page_count.is_none() && self.pages.is_none()
}
pub(crate) fn validate(&self, page_count: usize) -> Result<()> {
if matches!(self.quality, Quality::Balanced) {
return Err(EngineError::Io(std::io::Error::new(
std::io::ErrorKind::InvalidInput,
OptionsError::BalancedIsMarkdownOnly,
)));
}
#[cfg(not(feature = "ort-tables"))]
if self.tatr.as_ref().is_some_and(|t| t.test_hook.is_none()) {
return Err(EngineError::Io(std::io::Error::new(
std::io::ErrorKind::InvalidInput,
OptionsError::TatrNeedsOrtTables,
)));
}
let Some(pages) = &self.pages else {
return Ok(());
};
if self.first_page != 0 || self.page_count.is_some() {
return Err(EngineError::Io(std::io::Error::new(
std::io::ErrorKind::InvalidInput,
OptionsError::ConflictingPageSelection,
)));
}
if let Some(&index) = pages.iter().find(|page| **page >= page_count) {
return Err(EngineError::PageOutOfRange {
index,
count: page_count,
});
}
Ok(())
}
}
fn apply_heading_overrides(blocks: &mut [Block], overrides: &[HeadingOverride]) {
if overrides.is_empty() {
return;
}
for block in blocks.iter_mut() {
if let Some(hit) = overrides.iter().find(|o| o.text == block.text) {
match hit.level {
None => block.kind = BlockKind::Paragraph,
Some(level) => {
block.kind = BlockKind::Heading {
level: level.clamp(1, 3),
}
}
}
}
}
}
fn rebuild_block_text_and_box(block: &mut Block) {
let mut text = String::new();
for (index, span) in block.spans.iter().enumerate() {
if index > 0 && !crate::words_join::spans_join(&block.spans[index - 1], span) {
text.push(' ');
}
text.push_str(&span.text);
}
block.text = text;
let mut bbox = [
f64::INFINITY,
f64::INFINITY,
f64::NEG_INFINITY,
f64::NEG_INFINITY,
];
for span in &block.spans {
bbox[0] = bbox[0].min(span.x);
bbox[1] = bbox[1].min(span.y);
bbox[2] = bbox[2].max(span.x + span.width);
bbox[3] = bbox[3].max(span.y + span.height);
}
block.bbox = bbox;
}
fn drop_hidden_text(blocks: &mut Vec<Block>) {
use std::collections::HashSet;
let visible_pages: HashSet<usize> = blocks
.iter()
.filter(|b| b.spans.iter().any(|s| !s.is_hidden()))
.map(|b| b.page)
.collect();
let mut kept = Vec::with_capacity(blocks.len());
for mut block in blocks.drain(..) {
if visible_pages.contains(&block.page) && !block.spans.is_empty() {
let span_count = block.spans.len();
block.spans.retain(|s| !s.is_hidden() || s.is_ocr_layer);
if block.spans.is_empty() {
continue;
}
if block.spans.len() != span_count {
rebuild_block_text_and_box(&mut block);
}
}
kept.push(block);
}
*blocks = kept;
}
fn drop_hidden_text_raw(blocks: &mut Vec<Block>) {
use std::collections::HashSet;
let visible_pages: HashSet<usize> = blocks
.iter()
.filter(|b| b.spans.iter().any(|s| !s.is_hidden()))
.map(|b| b.page)
.collect();
let mut kept = Vec::with_capacity(blocks.len());
for mut block in blocks.drain(..) {
if visible_pages.contains(&block.page) && !block.spans.is_empty() {
let span_count = block.spans.len();
block.spans.retain(|s| !s.is_hidden() || s.is_ocr_layer);
if block.spans.is_empty() {
continue;
}
if block.spans.len() != span_count {
let (text, bbox) = crate::text::raw_text_and_box(&block.spans);
block.text = text;
block.bbox = bbox;
}
}
kept.push(block);
}
*blocks = kept;
}
pub(crate) fn window(blocks: Vec<Block>, options: &ExtractOptions) -> Vec<Block> {
let mut blocks = blocks;
apply_heading_overrides(&mut blocks, &options.heading_overrides);
if !options.include_hidden {
if options.raw_order {
drop_hidden_text_raw(&mut blocks);
} else {
drop_hidden_text(&mut blocks);
}
}
if options.is_whole_document() {
return blocks;
}
let mut out: Vec<Block> = Vec::new();
let mut previous_kept = false;
for mut block in blocks {
if !options.holds(block.page) {
previous_kept = false;
continue;
}
if !previous_kept {
block.continues_previous = false;
}
previous_kept = true;
out.push(block);
}
out
}
pub(crate) fn peel_table_edges(blocks: &mut Vec<Block>, runs_on_figures: bool) {
let mut i = 0;
let mut moved = false;
while i < blocks.len() {
let Some(end) = crate::markdown::table_run(blocks, i) else {
i += 1;
continue;
};
let body = |b: &Block| !matches!(b.kind, BlockKind::Header | BlockKind::Footer);
let cell = |b: &Block| matches!(b.kind, BlockKind::TableCell { .. });
let page = blocks[i].page;
let first_on_page = !blocks[..i]
.iter()
.rev()
.take_while(|b| b.page == page)
.any(body);
let last_on_page = !blocks[end..]
.iter()
.take_while(|b| b.page == page)
.any(body);
let table_ending_at = |last: usize| -> &[Block] {
let mut start = last;
while start > 0
&& cell(&blocks[start - 1])
&& blocks[start - 1].page == blocks[last].page
{
start -= 1;
}
&blocks[start..=last]
};
let table_starting_at = |first: usize| -> &[Block] {
let mut stop = first;
while stop < blocks.len()
&& cell(&blocks[stop])
&& blocks[stop].page == blocks[first].page
{
stop += 1;
}
&blocks[first..stop]
};
let continues_before = blocks[..i]
.iter()
.rposition(body)
.filter(|&k| blocks[k].page + 1 == page && cell(&blocks[k]))
.is_some_and(|k| same_columns(table_ending_at(k), &blocks[i..end]));
let continues_after = (end..blocks.len())
.find(|&k| body(&blocks[k]))
.filter(|&k| blocks[k].page == page + 1 && cell(&blocks[k]))
.is_some_and(|k| {
let (_, regridded, _) = regrid_one_column(table_starting_at(k).to_vec());
same_columns(&blocks[i..end], ®ridded)
});
let at_page_edge = (first_on_page && continues_before) || (last_on_page && continues_after);
let run: Vec<Block> = blocks.drain(i..end).collect();
let before = run.len();
let (head, run) = caption_row_or_single_row(run, at_page_edge);
let (over, run, under) = regrid_one_column(run);
let over: Vec<Block> = head.into_iter().chain(over).collect();
let (mut table, after) = split_prose_column(run);
moved |= !over.is_empty()
|| !under.is_empty()
|| !after.is_empty()
|| !table
.iter()
.any(|b| matches!(b.kind, BlockKind::TableCell { .. }));
peel_run(&mut table);
crate::learned::cell_merge::join_run_on_rows(&mut table, runs_on_figures);
let mut placed: Vec<Block> = over;
placed.extend(table);
placed.extend(after);
placed.extend(under);
let n = placed.len();
moved |= n != before;
blocks.splice(i..i, placed);
i += n.max(1);
}
if moved {
for (n, block) in blocks.iter_mut().enumerate() {
block.index = n;
}
}
}
fn caption_row_or_single_row(run: Vec<Block>, at_page_edge: bool) -> (Option<Block>, Vec<Block>) {
let place = |b: &Block| match b.kind {
BlockKind::TableCell { row, column, .. } => Some((row, column)),
_ => None,
};
let rows: std::collections::BTreeSet<u16> =
run.iter().filter_map(|b| place(b).map(|p| p.0)).collect();
let Some(&top) = rows.iter().next() else {
return (None, run);
};
let join = |cells: Vec<Block>| -> Option<Block> {
let mut cells: Vec<Block> = cells
.into_iter()
.filter(|b| !b.text.trim().is_empty())
.collect();
cells.sort_by_key(|b| place(b).map(|p| p.1));
let mut cells = cells.into_iter();
let mut out = cells.next()?;
out.kind = BlockKind::Paragraph;
out.grid = None;
out.text = out.text.trim().to_string();
for cell in cells {
out.text.push(' ');
out.text.push_str(cell.text.trim());
out.bbox = [
out.bbox[0].min(cell.bbox[0]),
out.bbox[1].min(cell.bbox[1]),
out.bbox[2].max(cell.bbox[2]),
out.bbox[3].max(cell.bbox[3]),
];
out.spans.extend(cell.spans);
}
Some(out)
};
let leaders = run.iter().any(|b| {
b.text
.chars()
.filter(|c| !c.is_whitespace())
.collect::<String>()
.contains("....")
});
if rows.len() == 1 && !leaders && !at_page_edge {
return (join(run), Vec::new());
}
let mut on_top: Vec<&Block> = run
.iter()
.filter(|b| place(b).is_some_and(|p| p.0 == top) && !b.text.trim().is_empty())
.collect();
if on_top.len() < 2 {
return (None, run);
}
on_top.sort_by_key(|b| place(b).map(|p| p.1));
if !is_numbered_caption(on_top[0].text.trim()) {
return (None, run);
}
let carried = on_top[1..]
.iter()
.all(|b| b.text.trim().chars().next().is_some_and(char::is_lowercase));
let caption_at: Vec<(u16, u16)> = if carried {
on_top.iter().filter_map(|b| place(b)).collect()
} else {
place(on_top[0]).into_iter().collect()
};
let (caption, mut rest): (Vec<Block>, Vec<Block>) = run
.into_iter()
.partition(|b| place(b).is_some_and(|p| caption_at.contains(&p)));
let row_left = rest.iter().any(|b| place(b).is_some_and(|p| p.0 == top));
if !row_left {
for b in rest.iter_mut() {
if let BlockKind::TableCell { row, .. } = &mut b.kind {
*row = row.saturating_sub(top + 1);
}
}
}
(join(caption), rest)
}
fn regrid_one_column(run: Vec<Block>) -> (Vec<Block>, Vec<Block>, Vec<Block>) {
let one_column = run.iter().all(|b| {
matches!(
b.kind,
BlockKind::TableCell {
column: 0,
column_span: 1,
..
}
)
});
if !one_column || run.len() < REGRID_MIN_ROWS {
return (Vec::new(), run, Vec::new());
}
let groups: Vec<Vec<Vec<usize>>> = run
.iter()
.map(|cell| {
let mut order: Vec<usize> = (0..cell.spans.len())
.filter(|&k| !cell.spans[k].text.trim().is_empty())
.collect();
order.sort_by(|&a, &b| cell.spans[a].x.total_cmp(&cell.spans[b].x));
let mut out: Vec<Vec<usize>> = Vec::new();
let mut right = f64::NEG_INFINITY;
for k in order {
let span = &cell.spans[k];
let gap = REGRID_GAP_EM * span.font_size.max(1.0);
match out.last_mut() {
Some(group) if span.x - right < gap => group.push(k),
_ => out.push(vec![k]),
}
right = right.max(span.x + span.width.max(0.0));
}
out
})
.collect();
let multi = groups.iter().filter(|g| g.len() >= 2).count();
if multi < REGRID_MIN_ROWS || (multi as f64) < REGRID_SHARE * run.len() as f64 {
return (Vec::new(), run, Vec::new());
}
let mut lefts: Vec<f64> = groups
.iter()
.zip(&run)
.filter(|(g, _)| g.len() >= 2)
.flat_map(|(g, cell)| {
g.iter()
.map(|group| cell.spans[group[0]].x)
.collect::<Vec<_>>()
})
.collect();
lefts.sort_by(f64::total_cmp);
let mut edges: Vec<(f64, usize)> = Vec::new(); for x in lefts {
match edges.last_mut() {
Some((left, n)) if x - *left <= REGRID_EDGE_TOLERANCE => *n += 1,
_ => edges.push((x, 1)),
}
}
let needed = ((REGRID_SHARE * multi as f64).ceil() as usize).max(REGRID_MIN_ROWS - 1);
let edges: Vec<f64> = edges
.into_iter()
.filter(|(_, n)| *n >= needed)
.map(|(x, _)| x)
.collect();
if edges.len() < 2 {
return (Vec::new(), run, Vec::new());
}
let column_at = |x: f64| -> usize {
edges
.iter()
.rposition(|&e| x >= e - REGRID_EDGE_TOLERANCE)
.unwrap_or(0)
};
let crosses = |cell: &Block, g: &[Vec<usize>]| -> bool {
if g.len() != 1 {
return false;
}
let left = g[0]
.iter()
.map(|&k| cell.spans[k].x)
.fold(f64::INFINITY, f64::min);
let right = g[0]
.iter()
.map(|&k| cell.spans[k].x + cell.spans[k].width.max(0.0))
.fold(f64::NEG_INFINITY, f64::max);
edges[1..]
.iter()
.any(|&e| left < e - REGRID_EDGE_TOLERANCE && right > e)
};
let rows = run.len();
let mut top = 0;
while top < rows && crosses(&run[top], &groups[top]) {
top += 1;
}
let mut bottom = rows;
while bottom > top && crosses(&run[bottom - 1], &groups[bottom - 1]) {
bottom -= 1;
}
let first_row = run
.get(top)
.and_then(|b| match b.kind {
BlockKind::TableCell { row, .. } => Some(row),
_ => None,
})
.unwrap_or(0);
let mut over = Vec::new();
let mut table = Vec::new();
let mut under = Vec::new();
for (k, (cell, g)) in run.into_iter().zip(groups).enumerate() {
if k < top {
over.push(cell);
continue;
}
if k >= bottom {
under.push(cell);
continue;
}
let row = match cell.kind {
BlockKind::TableCell { row, .. } => row.saturating_sub(first_row),
_ => 0,
};
for group in g {
let spans: Vec<TextSpan> = group.iter().map(|&i| cell.spans[i].clone()).collect();
let column = column_at(spans[0].x) as u16;
let mut text = String::new();
let mut right = f64::NEG_INFINITY;
for s in &spans {
if !text.is_empty() && s.x - right > REGRID_WORD_GAP_EM * s.font_size.max(1.0) {
text.push(' ');
}
text.push_str(&s.text);
right = right.max(s.x + s.width.max(0.0));
}
let text = text.trim().to_string();
let left = spans.iter().map(|s| s.x).fold(f64::INFINITY, f64::min);
let right = spans
.iter()
.map(|s| s.x + s.width.max(0.0))
.fold(f64::NEG_INFINITY, f64::max);
let mut piece = cell.clone();
piece.kind = BlockKind::TableCell {
row,
column,
row_span: 1,
column_span: 1,
header: row == 0,
};
piece.bbox = [left, cell.bbox[1], right, cell.bbox[3]];
piece.text = text;
piece.spans = spans;
table.push(piece);
}
}
table.sort_by_key(|b| match b.kind {
BlockKind::TableCell { row, column, .. } => (row, column),
_ => (u16::MAX, u16::MAX),
});
let place = |b: &Block| match b.kind {
BlockKind::TableCell { row, column, .. } => Some((row, column)),
_ => None,
};
let mut cells: Vec<Block> = Vec::new();
for piece in table {
match cells.last_mut() {
Some(last) if place(last) == place(&piece) => {
last.text.push(' ');
last.text.push_str(&piece.text);
last.bbox[0] = last.bbox[0].min(piece.bbox[0]);
last.bbox[2] = last.bbox[2].max(piece.bbox[2]);
last.spans.extend(piece.spans);
}
_ => cells.push(piece),
}
}
(join_as_paragraphs(over), cells, join_as_paragraphs(under))
}
const REGRID_WORD_GAP_EM: f64 = 0.15;
const REGRID_MIN_ROWS: usize = 4;
const REGRID_GAP_EM: f64 = 2.0;
const REGRID_SHARE: f64 = 0.5;
const REGRID_EDGE_TOLERANCE: f64 = 6.0;
fn split_prose_column(run: Vec<Block>) -> (Vec<Block>, Vec<Block>) {
let column_of = |b: &Block| match b.kind {
BlockKind::TableCell { column, .. } => Some(column),
_ => None,
};
let row_of = |b: &Block| match b.kind {
BlockKind::TableCell { row, .. } => Some(row),
_ => None,
};
let columns: Vec<u16> = run.iter().filter_map(column_of).collect();
let (Some(&first), Some(&last)) = (columns.iter().min(), columns.iter().max()) else {
return (run, Vec::new());
};
let col = last;
if first == last {
return (run, Vec::new());
}
let texts: Vec<&str> = run
.iter()
.filter(|b| column_of(b) == Some(col))
.map(|b| b.text.trim())
.filter(|t| !t.is_empty())
.collect();
if texts.len() < PROSE_COLUMN_MIN_CELLS {
return (run, Vec::new());
}
let lines = texts.iter().filter(|t| is_a_line_of_prose(t)).count();
let others_on = |row: u16| {
run.iter().any(|b| {
column_of(b).is_some_and(|c| c != col)
&& row_of(b) == Some(row)
&& !b.text.trim().is_empty()
})
};
let carried = run
.iter()
.filter(|b| column_of(b) == Some(col))
.filter(|b| {
let t = b.text.trim();
(t.chars().next().is_some_and(char::is_lowercase) || t.ends_with('-'))
&& row_of(b).is_some_and(others_on)
})
.count();
if (lines as f64) < PROSE_COLUMN_SHARE * texts.len() as f64
|| (carried as f64) < PROSE_COLUMN_FLOW * texts.len() as f64
{
return (run, Vec::new());
}
let (prose, table): (Vec<Block>, Vec<Block>) =
run.into_iter().partition(|b| column_of(b) == Some(col));
let paragraphs = join_as_paragraphs(prose);
let left: std::collections::BTreeSet<u16> = table.iter().filter_map(column_of).collect();
if left.len() < 2 {
let mut all = join_as_paragraphs(table);
all.extend(paragraphs);
return (all, Vec::new());
}
(table, paragraphs)
}
const PROSE_COLUMN_MIN_CELLS: usize = 6;
const PROSE_COLUMN_SHARE: f64 = 0.7;
const PROSE_COLUMN_FLOW: f64 = 0.4;
fn is_a_line_of_prose(text: &str) -> bool {
text.chars().count() >= 30
&& text
.split_whitespace()
.filter(|w| w.chars().filter(|c| c.is_alphabetic()).count() >= 3)
.count()
>= 5
}
fn join_as_paragraphs(lines: Vec<Block>) -> Vec<Block> {
let lines: Vec<Block> = lines
.into_iter()
.filter(|b| !b.text.trim().is_empty())
.collect();
let gaps: Vec<f64> = lines
.windows(2)
.map(|pair| pair[0].bbox[1] - pair[1].bbox[3])
.collect();
let mut sorted = gaps.clone();
sorted.sort_by(|a, b| a.total_cmp(b));
let leading = sorted.get(sorted.len() / 2).copied().unwrap_or(0.0);
let mut out: Vec<Block> = Vec::new();
let mut open = false;
for (k, line) in lines.into_iter().enumerate() {
let next = line.text.trim().to_string();
let white_under = gaps.get(k).copied().unwrap_or(f64::INFINITY);
let ends = next.ends_with(['.', '!', '?', ':'])
&& white_under > PARAGRAPH_GAP_FACTOR * leading.max(0.5);
match out.last_mut() {
Some(current) if open => {
if current.text.ends_with('-')
&& next.chars().next().is_some_and(char::is_lowercase)
{
current.text.pop();
} else {
current.text.push(' ');
}
current.text.push_str(&next);
current.bbox = [
current.bbox[0].min(line.bbox[0]),
current.bbox[1].min(line.bbox[1]),
current.bbox[2].max(line.bbox[2]),
current.bbox[3].max(line.bbox[3]),
];
current.spans.extend(line.spans);
}
_ => {
let mut block = line;
block.kind = BlockKind::Paragraph;
block.grid = None;
block.continues_previous = false;
block.text = next;
out.push(block);
}
}
open = !ends;
}
out
}
const PARAGRAPH_GAP_FACTOR: f64 = 1.5;
fn peel_run(cells: &mut [Block]) {
let at = |b: &Block| match b.kind {
BlockKind::TableCell {
row,
column,
column_span,
..
} => Some((row, column, column_span)),
_ => None,
};
let rows: Vec<u16> = cells
.iter()
.filter_map(|b| at(b).map(|(r, _, _)| r))
.collect();
let (Some(&top), Some(&bottom)) = (rows.iter().min(), rows.iter().max()) else {
return;
};
let columns = cells
.iter()
.filter_map(|b| at(b).map(|(_, c, s)| c + s.max(1)))
.max()
.unwrap_or(0);
if bottom - top < 2 || columns < 2 {
return;
}
let lone = |row: u16| -> Option<usize> {
let filled: Vec<usize> = (0..cells.len())
.filter(|&k| at(&cells[k]).is_some_and(|(r, _, _)| r == row))
.filter(|&k| !cells[k].text.trim().is_empty())
.collect();
match filled[..] {
[k] if reads_as_caption_or_note(&cells[k].text, row == bottom) => Some(k),
_ => None,
}
};
let top_cell = lone(top);
let bottom_cell = lone(bottom);
for k in [top_cell, bottom_cell].into_iter().flatten() {
cells[k].kind = BlockKind::Paragraph;
cells[k].grid = None;
}
if top_cell.is_some() {
for b in cells.iter_mut() {
if let BlockKind::TableCell { row, .. } = &mut b.kind {
*row = row.saturating_sub(top + 1);
}
}
}
}
fn is_numbered_caption(t: &str) -> bool {
let marked = t.trim_start_matches(['*', '\u{2020}']);
let mut chars = marked.chars();
let glued = matches!(
(chars.next(), chars.next()),
(Some(a), Some('T')) if a.is_ascii_lowercase()
);
let lowered = marked.to_lowercase();
let s = if glued {
&lowered[1..]
} else {
lowered.as_str()
};
let rest = s
.strip_prefix("table")
.or_else(|| s.strip_prefix("tab."))
.map(str::trim_start);
let Some(rest) = rest else {
return false;
};
if rest.chars().next().is_some_and(|c| c.is_ascii_digit()) {
return true;
}
let word: String = rest.chars().take_while(|c| c.is_alphanumeric()).collect();
let roman = !word.is_empty() && word.len() <= 5 && word.chars().all(|c| "ivxlc".contains(c));
let supplementary =
word.len() >= 2 && word.starts_with('s') && word[1..].chars().all(|c| c.is_ascii_digit());
roman || supplementary
}
fn reads_as_caption_or_note(text: &str, below: bool) -> bool {
let t = text.trim();
let words = t.split_whitespace().count();
let lower = t.to_lowercase();
let first = t.chars().next();
let caption = is_numbered_caption(t);
let real_words = t
.split_whitespace()
.filter(|w| w.chars().filter(|c| c.is_alphabetic()).count() >= 3)
.count();
let sentence = words >= 7
&& real_words >= 5
&& (t.ends_with('.') || first.is_some_and(char::is_lowercase));
let note = words >= 4
&& (["note", "abbreviation", "source", "data are", "values are"]
.iter()
.any(|w| lower.starts_with(w))
|| t.split_once(':').is_some_and(|(label, rest)| {
(1..=3).contains(&label.split_whitespace().count())
&& label.chars().all(|c| c.is_alphabetic() || c.is_whitespace())
&& rest.split_whitespace().count() >= 3
})
|| first.is_some_and(|c| "*\u{2020}\u{2021}\u{a7}\u{b6}#".contains(c))
|| (first.is_some_and(|c| c.is_ascii_lowercase())
&& t.chars().nth(1).is_some_and(char::is_whitespace)
&& t.split_whitespace()
.nth(1)
.is_some_and(|w| w.chars().filter(|c| c.is_alphabetic()).count() >= 3)));
caption || note || (below && sentence)
}
pub(crate) fn tables_across_pages(blocks: &mut [Block]) {
let body = |b: &Block| !matches!(b.kind, BlockKind::Header | BlockKind::Footer);
let cell = |b: &Block| matches!(b.kind, BlockKind::TableCell { .. });
let mut k = 1;
while k < blocks.len() {
if blocks[k].page == blocks[k - 1].page || !cell(&blocks[k]) {
k += 1;
continue;
}
let before = (0..k).rev().find(|&i| body(&blocks[i]));
let first_after = (k..blocks.len())
.take_while(|&i| blocks[i].page == blocks[k].page)
.find(|&i| body(&blocks[i]));
let (Some(last), Some(first)) = (before, first_after) else {
k += 1;
continue;
};
if first != k || !cell(&blocks[last]) || blocks[last].page + 1 != blocks[k].page {
k += 1;
continue;
}
let mut start = last;
while start > 0 && cell(&blocks[start - 1]) && blocks[start - 1].page == blocks[last].page {
start -= 1;
}
let mut end = k;
while end < blocks.len() && cell(&blocks[end]) && blocks[end].page == blocks[k].page {
end += 1;
}
if same_columns(&blocks[start..=last], &blocks[k..end]) {
blocks[k].continues_previous = true;
}
k = end.max(k + 1);
}
}
pub(crate) fn join_heading_subtitles(blocks: &mut Vec<Block>) {
let mut out: Vec<Block> = Vec::with_capacity(blocks.len());
let mut head_size = 0.0;
let mut joined = false;
for block in blocks.drain(..) {
let joins = out
.last()
.filter(|head| matches!(head.kind, BlockKind::Heading { .. }))
.is_some_and(|head| {
matches!(block.kind, BlockKind::Heading { .. } | BlockKind::Paragraph)
&& block.page == head.page
&& subtitle_joins(head, &block, head_size)
});
if joins {
if let Some(head) = out.last_mut() {
head.text.push(' ');
head.text.push_str(&block.text);
head.spans.extend(block.spans);
head.bbox = [
head.bbox[0].min(block.bbox[0]),
head.bbox[1].min(block.bbox[1]),
head.bbox[2].max(block.bbox[2]),
head.bbox[3].max(block.bbox[3]),
];
}
joined = true;
} else {
head_size = if matches!(block.kind, BlockKind::Heading { .. }) {
median_span_size(&block)
} else {
0.0
};
out.push(block);
}
}
*blocks = out;
if joined {
for (n, block) in blocks.iter_mut().enumerate() {
block.index = n;
}
}
}
const SUBTITLE_ALIGN_TOLERANCE: f64 = 1.0;
const SUBTITLE_LEADING_EM: f64 = 0.25;
const SUBTITLE_SIZE_TOLERANCE: f64 = 0.5;
const SUBTITLE_MAX_WORDS: usize = 10;
const SUBTITLE_FALLBACK_EM: f64 = 10.0;
fn subtitle_joins(head: &Block, under: &Block, head_size: f64) -> bool {
let left_aligned = (under.bbox[0] - head.bbox[0]).abs() <= SUBTITLE_ALIGN_TOLERANCE;
let head_centre = (head.bbox[0] + head.bbox[2]) / 2.0;
let under_centre = (under.bbox[0] + under.bbox[2]) / 2.0;
if !left_aligned && (under_centre - head_centre).abs() > SUBTITLE_ALIGN_TOLERANCE {
return false;
}
let em = if head_size > 0.0 {
head_size
} else {
SUBTITLE_FALLBACK_EM
};
let gap = head.bbox[1] - under.bbox[3];
if gap < 0.0 || gap > SUBTITLE_LEADING_EM * em {
return false;
}
if median_span_size(under) > head_size + SUBTITLE_SIZE_TOLERANCE {
return false;
}
if under.text.split_whitespace().count() > SUBTITLE_MAX_WORDS {
return false;
}
if ends_like_prose_or_a_label(&head.text) || ends_like_prose_or_a_label(&under.text) {
return false;
}
!opens_with_a_list_marker(&under.text)
}
fn median_span_size(block: &Block) -> f64 {
let mut sizes: Vec<f64> = block.spans.iter().map(|span| span.font_size).collect();
if sizes.is_empty() {
return 0.0;
}
sizes.sort_by(f64::total_cmp);
let mid = sizes.len() / 2;
if sizes.len() % 2 == 1 {
sizes[mid]
} else {
(sizes[mid - 1] + sizes[mid]) / 2.0
}
}
fn ends_like_prose_or_a_label(text: &str) -> bool {
matches!(text.trim_end().chars().last(), Some('.' | '!' | '?' | ':'))
}
fn opens_with_a_list_marker(text: &str) -> bool {
let rest = text.trim_start_matches(char::is_whitespace);
let rest = rest.strip_prefix('(').unwrap_or(rest);
let mut chars = rest.chars();
let Some(first) = chars.next() else {
return false;
};
if first.is_ascii_digit() {
let mut digits = 1;
for c in chars {
if c.is_ascii_digit() {
digits += 1;
if digits > 3 {
return false;
}
} else {
return c == '.' || c == ')';
}
}
return false;
}
if first.is_ascii_lowercase() {
return match (chars.next(), chars.next()) {
(Some(delimiter), Some(after)) if delimiter == '.' || delimiter == ')' => {
after.is_whitespace()
}
_ => false,
};
}
matches!(first, '•' | '●' | '▪' | '■' | '–' | '—' | '-' | '*')
&& chars.next().is_some_and(|c| c.is_whitespace())
}
pub(crate) fn join_heading_lines(blocks: &mut Vec<Block>) {
let mut out: Vec<Block> = Vec::with_capacity(blocks.len());
let mut pieces = 0usize;
let mut joined = false;
for block in blocks.drain(..) {
let joins = match out.last() {
Some(head)
if matches!(head.kind, BlockKind::Heading { .. } | BlockKind::Paragraph)
&& matches!(block.kind, BlockKind::Heading { .. } | BlockKind::Paragraph)
&& (matches!(head.kind, BlockKind::Heading { .. })
|| matches!(block.kind, BlockKind::Heading { .. }))
&& block.page == head.page
&& pieces < HEADING_LINE_MAX_PIECES =>
{
heading_line_joins(head, &block)
}
_ => false,
};
if joins {
if let Some(head) = out.last_mut() {
let level = match (head.kind, block.kind) {
(BlockKind::Heading { level }, _) => level,
(_, BlockKind::Heading { level }) => level,
_ => unreachable!("a heading join with no heading in it"),
};
head.kind = BlockKind::Heading { level };
head.text.push(' ');
head.text.push_str(&block.text);
head.spans.extend(block.spans);
head.bbox = [
head.bbox[0].min(block.bbox[0]),
head.bbox[1].min(block.bbox[1]),
head.bbox[2].max(block.bbox[2]),
head.bbox[3].max(block.bbox[3]),
];
}
pieces += 1;
joined = true;
} else {
pieces = 1;
out.push(block);
}
}
*blocks = out;
if joined {
for (n, block) in blocks.iter_mut().enumerate() {
block.index = n;
}
}
}
const HEADING_LINE_ALIGN_TOLERANCE: f64 = 1.0;
const HEADING_LINE_LEADING_EM: f64 = 0.5;
const HEADING_LINE_MIN_GAP: f64 = -0.5;
const HEADING_LINE_MAX_WORDS: usize = 20;
const HEADING_LINE_MAX_PIECES: usize = 3;
const HEADING_LINE_FALLBACK_EM: f64 = 10.0;
fn heading_line_joins(head: &Block, under: &Block) -> bool {
let (Some(over), Some(below)) = (heading_line_style(head), heading_line_style(under)) else {
return false;
};
if over != below {
return false;
}
let em = if over.0 > 0.0 {
over.0
} else {
HEADING_LINE_FALLBACK_EM
};
let gap = head.bbox[1] - under.bbox[3];
if gap < HEADING_LINE_MIN_GAP || gap > HEADING_LINE_LEADING_EM * em {
return false;
}
let left_aligned = (under.bbox[0] - head.bbox[0]).abs() <= HEADING_LINE_ALIGN_TOLERANCE;
let head_centre = (head.bbox[0] + head.bbox[2]) / 2.0;
let under_centre = (under.bbox[0] + under.bbox[2]) / 2.0;
if !left_aligned && (under_centre - head_centre).abs() > HEADING_LINE_ALIGN_TOLERANCE {
return false;
}
if ends_like_a_sentence(&head.text)
|| (matches!(under.kind, BlockKind::Paragraph)
&& ends_like_a_sentence_or_a_label(&under.text))
{
return false;
}
if opens_with_a_list_marker(&under.text) {
return false;
}
head.text.split_whitespace().count() + under.text.split_whitespace().count()
<= HEADING_LINE_MAX_WORDS
}
fn heading_line_style(block: &Block) -> Option<(f64, bool, bool)> {
if block.spans.is_empty() {
return None;
}
let size = (median_span_size(block) * 2.0).round() / 2.0;
let bold = block.spans.iter().filter(|span| span.is_bold).count() * 2 >= block.spans.len();
let italic = block.spans.iter().filter(|span| span.is_italic).count() * 2 >= block.spans.len();
Some((size, bold, italic))
}
fn ends_like_a_sentence(text: &str) -> bool {
matches!(text.trim_end().chars().last(), Some('.' | '!' | '?' | ';'))
}
fn ends_like_a_sentence_or_a_label(text: &str) -> bool {
matches!(
text.trim_end().chars().last(),
Some('.' | '!' | '?' | ';' | ':')
)
}
const PARAGRAPH_STEP_JUMP: f64 = 1.5;
const PARAGRAPH_STEP_LEFT_EM: f64 = 1.0;
const PARAGRAPH_STEP_STACKED_LINE: usize = 2;
const PARAGRAPH_STEP_ROTATION: f64 = 0.1;
const PARAGRAPH_STEP_DIGIT_SHARE: f64 = 0.5;
pub(crate) fn split_paragraphs_on_steps(blocks: &mut Vec<Block>) {
let mut out: Vec<Block> = Vec::with_capacity(blocks.len());
let mut split = false;
for block in blocks.drain(..) {
if !matches!(block.kind, BlockKind::Paragraph) {
out.push(block);
continue;
}
let pieces = split_paragraph_on_steps(&block);
if pieces.len() <= 1 {
out.push(block);
} else {
split = true;
out.extend(pieces);
}
}
*blocks = out;
if split {
for (n, block) in blocks.iter_mut().enumerate() {
block.index = n;
}
}
}
fn step_split_number_block(block: &Block) -> bool {
let mut total = 0usize;
let mut figures = 0usize;
for c in block.text.chars().filter(|c| !c.is_whitespace()) {
total += 1;
if matches!(
c,
'0'..='9' | '.' | ',' | '(' | ')' | '%' | '$' | '€' | '£' | '–' | '-'
) {
figures += 1;
}
}
total > 0 && figures as f64 >= PARAGRAPH_STEP_DIGIT_SHARE * total as f64
}
fn step_split_rotated(span: &TextSpan) -> bool {
match span.transform {
Some([a, b, c, ..]) => {
b.abs() > PARAGRAPH_STEP_ROTATION * a.abs()
|| c.abs() > PARAGRAPH_STEP_ROTATION * a.abs()
}
None => false,
}
}
fn step_split_stacked(block: &Block, lines: &[Vec<usize>]) -> bool {
let mut counts: Vec<usize> = lines
.iter()
.map(|line| line.iter().map(|i| char_count(&block.spans[*i])).sum())
.collect();
counts.sort_unstable();
!counts.is_empty() && counts[counts.len() / 2] <= PARAGRAPH_STEP_STACKED_LINE
}
fn step_split_vertical(block: &Block) -> bool {
let rotated = block.spans.iter().filter(|s| step_split_rotated(s)).count();
rotated * 2 > block.spans.len()
}
fn step_split_reassembles(parent: &Block, pieces: &[Block]) -> bool {
let plain = |text: &str| {
text.replace("- ", "")
.chars()
.filter(|c| !c.is_whitespace())
.collect::<Vec<_>>()
};
let want = plain(&parent.text);
let mut got: Vec<char> = Vec::with_capacity(want.len());
for piece in pieces {
got.extend(plain(&piece.text));
}
want == got
}
fn step_split_trace(guard: &str, block: &Block) {
if tracing() {
let head: String = block.text.chars().take(80).collect();
eprintln!("STEP-SPLIT {guard} | {head}");
}
}
fn split_paragraph_on_steps(block: &Block) -> Vec<Block> {
if step_split_number_block(block) {
step_split_trace("number-block", block);
return vec![block.clone()];
}
let mut order: Vec<usize> = (0..block.spans.len()).collect();
order.sort_by(|a, b| {
block.spans[*b]
.y
.partial_cmp(&block.spans[*a].y)
.unwrap_or(Ordering::Equal)
});
let mut lines: Vec<Vec<usize>> = Vec::new();
for i in order {
let same_line = lines.last().is_some_and(|line: &Vec<usize>| {
let first = &block.spans[line[0]];
let span = &block.spans[i];
(first.y - span.y).abs() <= first.font_size.max(span.font_size) * 0.5
});
match lines.last_mut() {
Some(line) if same_line => line.push(i),
_ => lines.push(vec![i]),
}
}
if lines.len() < 3 {
return vec![block.clone()];
}
if step_split_stacked(block, &lines) {
step_split_trace("stacked-glyphs", block);
return vec![block.clone()];
}
if step_split_vertical(block) {
step_split_trace("rotated-spans", block);
return vec![block.clone()];
}
let baseline_of = |line: &[usize]| -> f64 {
line.iter()
.map(|i| &block.spans[*i])
.max_by_key(|span| char_count(span))
.map(|span| span.y)
.unwrap_or(0.0)
};
let left_of = |line: &[usize]| -> f64 {
line.iter()
.map(|i| block.spans[*i].x)
.fold(f64::INFINITY, f64::min)
};
let mut steps: Vec<f64> = lines
.windows(2)
.map(|pair| baseline_of(&pair[0]) - baseline_of(&pair[1]))
.filter(|step| *step > 0.0)
.collect();
if steps.is_empty() {
return vec![block.clone()];
}
steps.sort_by(f64::total_cmp);
let median = steps[steps.len() / 2];
if !median.is_finite() || median <= 0.0 {
return vec![block.clone()];
}
let em = median_span_size(block);
let em = if em > 0.0 { em } else { SUBTITLE_FALLBACK_EM };
let mut cuts: Vec<bool> = vec![false; lines.len() - 1];
for (i, pair) in lines.windows(2).enumerate() {
let step = baseline_of(&pair[0]) - baseline_of(&pair[1]);
cuts[i] = step >= PARAGRAPH_STEP_JUMP * median
&& (left_of(&pair[0]) - left_of(&pair[1])).abs() <= PARAGRAPH_STEP_LEFT_EM * em;
}
if !cuts.iter().any(|cut| *cut) {
return vec![block.clone()];
}
let mut pieces: Vec<Block> = Vec::new();
let mut start = 0usize;
for (i, cut) in cuts.iter().enumerate() {
if *cut {
pieces.push(piece_of(block, &lines, start, i + 1));
start = i + 1;
}
}
pieces.push(piece_of(block, &lines, start, lines.len()));
if !step_split_reassembles(block, &pieces) {
step_split_trace("words-changed", block);
return vec![block.clone()];
}
pieces
}
fn piece_of(block: &Block, lines: &[Vec<usize>], start: usize, end: usize) -> Block {
let mut indices: Vec<usize> = lines[start..end].iter().flatten().copied().collect();
indices.sort_unstable();
let spans: Vec<TextSpan> = indices.iter().map(|i| block.spans[*i].clone()).collect();
let mut texts: Vec<String> = Vec::with_capacity(end - start);
for line in &lines[start..end] {
let mut order: Vec<usize> = line.clone();
order.sort_unstable();
let row: Vec<TextSpan> = order.iter().map(|i| block.spans[*i].clone()).collect();
texts.push(TextBlock { spans: row }.text());
}
let mut piece = Block {
kind: block.kind,
page: block.page,
bbox: [0.0; 4],
text: join_lines(&texts),
spans,
index: 0,
continues_previous: start == 0 && block.continues_previous,
confidence: block.confidence,
grid: block.grid,
table_origin: block.table_origin,
trace_learned: block.trace_learned,
};
recompute_bbox(&mut piece);
piece
}
fn column_lefts(cells: &[Block]) -> Vec<Option<f64>> {
let mut lefts: Vec<Option<f64>> = Vec::new();
for b in cells {
if let BlockKind::TableCell {
column,
column_span: 1,
..
} = b.kind
{
let c = column as usize;
if lefts.len() <= c {
lefts.resize(c + 1, None);
}
let x = b.bbox[0];
if x.is_finite() && b.bbox != [0.0; 4] {
lefts[c] = Some(lefts[c].map_or(x, |l: f64| l.min(x)));
}
}
}
lefts
}
fn same_columns(a: &[Block], b: &[Block]) -> bool {
let (la, lb) = (column_lefts(a), column_lefts(b));
la.len() >= 2
&& la.len() == lb.len()
&& la.iter().zip(&lb).all(|(x, y)| match (x, y) {
(Some(x), Some(y)) => (x - y).abs() <= CONTINUED_COLUMN_TOLERANCE,
_ => true,
})
&& la
.iter()
.zip(&lb)
.filter(|(x, y)| x.is_some() && y.is_some())
.count()
>= 2
}
const CONTINUED_COLUMN_TOLERANCE: f64 = 6.0;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum IndentStyle {
Flat,
FirstLine,
Hanging,
}
struct LineMetrics {
left: f64,
indent_left: f64,
right: f64,
baseline: f64,
top: f64,
bottom: f64,
font_size: f64,
bold: bool,
text: String,
initial: Option<usize>,
wide_gaps: Vec<(f64, f64)>,
tabular: bool,
marker: Option<Marker>,
marker_text_left: Option<f64>,
item: Option<ItemMark>,
}
#[derive(Debug, Clone, Copy)]
struct ItemMark {
len: usize,
level: u8,
ordinal: Option<u32>,
text_left: Option<f64>,
}
pub(crate) fn span_right(span: &TextSpan) -> f64 {
if span.width > 0.0 {
span.x + span.width
} else {
span.x + span.font_size * 0.5 * span.text.chars().count() as f64
}
}
fn span_extent(span: &TextSpan) -> (f64, f64) {
let mut bottom = f64::INFINITY;
let mut top = f64::NEG_INFINITY;
for bounds in &span.char_bounds {
bottom = bottom.min(bounds[1]);
top = top.max(bounds[3]);
}
if bottom.is_finite() && top.is_finite() && top > bottom {
return (bottom, top);
}
(span.y - span.font_size * 0.2, span.y + span.font_size * 0.8)
}
fn char_count(span: &TextSpan) -> usize {
span.text.chars().filter(|c| !c.is_whitespace()).count()
}
fn text_left_after(line: &TextBlock, order: &[usize], marker_chars: usize) -> Option<f64> {
if marker_chars == 0 {
return None;
}
let mut seen = 0usize;
for i in order {
match seen.cmp(&marker_chars) {
Ordering::Equal if char_count(&line.spans[*i]) == 0 => {}
Ordering::Equal => return Some(line.spans[*i].x),
Ordering::Greater => return None,
Ordering::Less => seen += char_count(&line.spans[*i]),
}
}
None
}
impl LineMetrics {
fn of(line: &TextBlock) -> Self {
Self::of_with(line, true, false)
}
fn of_with(line: &TextBlock, allow_initial: bool, cell_path_words: bool) -> Self {
let mut order: Vec<usize> = (0..line.spans.len()).collect();
order.sort_by(|a, b| {
line.spans[*a]
.x
.partial_cmp(&line.spans[*b].x)
.unwrap_or(Ordering::Equal)
});
let dominant_size = dominant_font_size(line.spans.iter());
let initial = order.first().copied().filter(|&first| {
allow_initial
&& line.spans.len() > 1
&& char_count(&line.spans[first]) <= INITIAL_MAX_CHARS
&& char_count(&line.spans[first]) > 0
&& dominant_size > 0.0
&& line.spans[first].font_size >= INITIAL_SIZE_RATIO * dominant_size
});
let body: Vec<usize> = order
.iter()
.copied()
.filter(|i| Some(*i) != initial)
.collect();
let measured: Vec<&TextSpan> = if body.is_empty() {
order.iter().map(|i| &line.spans[*i]).collect()
} else {
body.iter().map(|i| &line.spans[*i]).collect()
};
let left = measured.iter().map(|s| s.x).fold(f64::INFINITY, f64::min);
let right = measured
.iter()
.map(|s| span_right(s))
.fold(f64::NEG_INFINITY, f64::max);
let mut bottom = f64::INFINITY;
let mut top = f64::NEG_INFINITY;
for span in &measured {
let (b, t) = span_extent(span);
bottom = bottom.min(b);
top = top.max(t);
}
let anchor = anchor_span(measured.iter().copied()).or_else(|| line.spans.first());
let baseline = anchor.map(|s| s.y).unwrap_or(0.0);
let font_size = match dominant_font_size(measured.iter().copied()) {
size if size > 0.0 => size,
_ => anchor.map(|s| s.font_size).unwrap_or(0.0),
};
let bold = spans_read_bold(measured.iter().copied());
let mut wide_gaps = Vec::new();
if font_size > 0.0 {
let threshold = TABULAR_GAP_EM * font_size;
for pair in body.windows(2) {
let end = span_right(&line.spans[pair[0]]);
let start = line.spans[pair[1]].x;
if start - end >= threshold {
wide_gaps.push((end, start));
}
}
}
let text = line.text_with_cell_path_words(cell_path_words);
let head = line
.spans
.first()
.filter(|span| char_count(span) > 0)
.filter(|span| line.spans.len() > 1 && text.starts_with(span.text.as_str()));
let symbol_prefix = head
.filter(|span| char_count(span) <= MARKER_MAX_CHARS)
.filter(|span| lists::is_symbol_font(span.font_name.as_deref()))
.map(|span| span.text.len());
let raised_prefix = head
.filter(|span| char_count(span) <= MAX_ORDINAL_CHARS)
.filter(|span| font_size > 0.0 && span.font_size < font_size * RAISED_SIZE)
.filter(|span| span.y > baseline + RAISED_RISE * font_size)
.map(|span| span.text.len());
let apart_prefix = head
.filter(|span| char_count(span) == 1 && font_size > 0.0)
.filter(|span| {
line.spans
.iter()
.skip(1)
.find(|next| char_count(next) > 0)
.is_some_and(|next| next.x - span_right(span) >= MARKER_GAP_EM * font_size)
})
.map(|span| span.text.len());
let marker = lists::marker_at(
&text,
lists::Lead {
symbol: symbol_prefix,
raised: raised_prefix,
apart: apart_prefix,
},
);
let marker_text_left = marker.and_then(|marker| {
let marker_chars = text[..marker.len]
.chars()
.filter(|c| !c.is_whitespace())
.count();
text_left_after(line, &order, marker_chars)
});
Self {
left,
indent_left: left,
right,
baseline,
top,
bottom,
font_size,
bold,
marker,
marker_text_left,
text,
initial,
wide_gaps,
tabular: false,
item: None,
}
}
fn ends_sentence(&self) -> bool {
let trimmed = self
.text
.trim_end()
.trim_end_matches(['"', '\'', '”', '’', ')', ']', '»']);
matches!(
trimmed.chars().next_back(),
Some('.') | Some('!') | Some('?') | Some(':') | Some(';')
)
}
}
pub(crate) fn dominant_font_size<'a>(spans: impl Iterator<Item = &'a TextSpan>) -> f64 {
let mut sizes: Vec<f64> = Vec::new();
for span in spans {
if span.char_bounds.is_empty() {
sizes.extend(std::iter::repeat_n(span.font_size, char_count(span).max(1)));
} else {
sizes.extend(span.char_bounds.iter().map(|bound| bound[3] - bound[1]));
}
}
sizes.retain(|size| *size > 0.0);
if sizes.is_empty() {
return 0.0;
}
sizes.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
sizes[sizes.len() / 2]
}
pub(crate) fn spans_read_bold<'a>(spans: impl Iterator<Item = &'a TextSpan>) -> bool {
let mut heavy = 0usize;
let mut total = 0usize;
for span in spans {
let chars = char_count(span);
total += chars;
if span.is_bold {
heavy += chars;
}
}
total > 0 && heavy * 2 > total
}
pub(crate) fn anchor_span<'a>(spans: impl Iterator<Item = &'a TextSpan>) -> Option<&'a TextSpan> {
spans.max_by_key(|s| char_count(s))
}
fn overlap_fraction(a: &LineMetrics, b: &LineMetrics) -> f64 {
overlap_fraction_of(a.left, a.right, b.left, b.right)
}
pub(crate) fn overlap_fraction_of(a_left: f64, a_right: f64, b_left: f64, b_right: f64) -> f64 {
let overlap = a_right.min(b_right) - a_left.max(b_left);
let narrower = (a_right - a_left).max(0.0).min((b_right - b_left).max(0.0));
if narrower <= 0.0 {
return if overlap >= 0.0 { 1.0 } else { 0.0 };
}
(overlap / narrower).max(0.0)
}
fn mark_tabular(metrics: &mut [LineMetrics]) {
let confirmed: Vec<bool> = (0..metrics.len())
.map(|i| {
if metrics[i].wide_gaps.is_empty() {
return false;
}
let neighbours = [i.checked_sub(1), (i + 1 < metrics.len()).then_some(i + 1)];
neighbours.into_iter().flatten().any(|j| {
metrics[i].wide_gaps.iter().any(|mine| {
metrics[j]
.wide_gaps
.iter()
.any(|theirs| mine.0 < theirs.1 && theirs.0 < mine.1)
})
})
})
.collect();
for (line, is_tabular) in metrics.iter_mut().zip(confirmed) {
line.tabular = is_tabular;
}
}
fn confirm_initials(metrics: &mut [LineMetrics], lines: &[&TextBlock], cell_path_words: bool) {
let boxes: Vec<Option<(f64, f64, f64, f64)>> = metrics
.iter()
.zip(lines)
.map(|(m, line)| {
let span = &line.spans[m.initial?];
let (bottom, top) = span_extent(span);
Some((span.x, span_right(span), bottom, top))
})
.collect();
let beside = |line: &LineMetrics, (left, right, bottom, top): (f64, f64, f64, f64)| {
let _ = left;
line.baseline > bottom && line.baseline <= top && line.left >= right - 1.0
};
let mut confirmed: Vec<(f64, f64, f64, f64)> = Vec::new();
let mut rejected: Vec<usize> = Vec::new();
for (i, cap) in boxes.iter().enumerate() {
let Some(cap) = *cap else { continue };
let has_neighbour = metrics
.iter()
.enumerate()
.any(|(j, line)| j != i && line.baseline > metrics[i].baseline && beside(line, cap));
if has_neighbour {
confirmed.push(cap);
} else {
rejected.push(i);
}
}
for i in rejected {
metrics[i] = LineMetrics::of_with(lines[i], false, cell_path_words);
}
if confirmed.is_empty() {
return;
}
for line in metrics.iter_mut() {
for cap in &confirmed {
if beside(line, *cap) {
line.indent_left = line.indent_left.min(cap.0);
}
}
}
}
fn mark_list_items(metrics: &mut [LineMetrics], regions: &[(usize, usize)]) {
let foot = in_the_foot(metrics);
for (start, end) in column_stacks(metrics, regions) {
mark_column_items(&mut metrics[start..end], &foot[start..end]);
}
}
const RUNNING_TEXT_LETTERS: usize = 20;
const FOOT_SHARE: f64 = 0.4;
fn body_size_of<'a>(lines: impl Iterator<Item = &'a LineMetrics>) -> f64 {
let mut sizes: Vec<f64> = Vec::new();
for line in lines {
let chars = line.text.chars().filter(|c| !c.is_whitespace()).count();
if line.font_size > 0.0 {
sizes.extend(std::iter::repeat_n(line.font_size, chars.max(1)));
}
}
sizes.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
sizes.get(sizes.len() / 2).copied().unwrap_or(0.0)
}
fn in_the_foot(metrics: &[LineMetrics]) -> Vec<bool> {
let low = metrics
.iter()
.map(|l| l.bottom)
.fold(f64::INFINITY, f64::min);
let high = metrics
.iter()
.map(|l| l.top)
.fold(f64::NEG_INFINITY, f64::max);
let upper: Vec<usize> = (0..metrics.len())
.filter(|i| metrics[*i].bottom >= low + FOOT_SHARE * (high - low))
.collect();
let page_body = if upper.is_empty() {
column_body(metrics).0
} else {
body_size_of(upper.iter().map(|i| &metrics[*i]))
};
if page_body <= 0.0 {
return vec![false; metrics.len()];
}
let last_body_line = metrics
.iter()
.filter(|l| {
l.font_size >= page_body * (1.0 - SIZE_TOLERANCE)
&& l.text.chars().filter(|c| c.is_alphabetic()).count() >= RUNNING_TEXT_LETTERS
})
.map(|l| l.bottom)
.fold(f64::INFINITY, f64::min);
let heads: Vec<(f64, f64)> = metrics
.iter()
.filter(|l| {
let letters = l.text.chars().filter(|c| c.is_alphabetic()).count();
l.top <= last_body_line
&& l.marker.is_none()
&& (l.bold || l.font_size > page_body * (1.0 + SIZE_TOLERANCE))
&& l.text.chars().any(char::is_alphanumeric)
&& letters < RUNNING_TEXT_LETTERS
})
.map(|l| (l.top, l.bottom))
.collect();
metrics
.iter()
.map(|l| {
l.font_size < page_body * (1.0 - SIZE_TOLERANCE)
&& l.top <= last_body_line
&& !heads.iter().any(|(_, bottom)| *bottom >= l.top)
})
.collect()
}
const STACK_GAP_LINES: f64 = 3.0;
fn column_stacks(metrics: &[LineMetrics], regions: &[(usize, usize)]) -> Vec<(usize, usize)> {
let extent = |start: usize, end: usize| {
let lines = &metrics[start..end];
let left = lines.iter().map(|l| l.left).fold(f64::INFINITY, f64::min);
let right = lines
.iter()
.map(|l| l.right)
.fold(f64::NEG_INFINITY, f64::max);
let top = lines
.iter()
.map(|l| l.top)
.fold(f64::NEG_INFINITY, f64::max);
let bottom = lines.iter().map(|l| l.bottom).fold(f64::INFINITY, f64::min);
(left, right, top, bottom)
};
let mut stacks: Vec<(usize, usize)> = Vec::new();
let mut last: Option<(f64, f64, f64, f64)> = None;
for &(start, end) in regions {
if start >= end {
continue;
}
let here = extent(start, end);
let joins = match (stacks.last(), last) {
(Some(&(_, stack_end)), Some((left, right, _, bottom))) if stack_end == start => {
let overlap = right.min(here.1) - left.max(here.0);
let narrower = (right - left).min(here.1 - here.0);
let size = metrics[start..end]
.iter()
.map(|l| l.font_size)
.fold(0.0_f64, f64::max);
narrower > 0.0
&& overlap >= 0.5 * narrower
&& here.2 <= bottom + 1.0
&& bottom - here.2 <= STACK_GAP_LINES * size.max(1.0)
}
_ => false,
};
if joins {
if let (Some(stack), Some(prev)) = (stacks.last_mut(), last) {
stack.1 = end;
last = Some((
prev.0.min(here.0),
prev.1.max(here.1),
prev.2,
here.3.min(prev.3),
));
}
} else {
stacks.push((start, end));
last = Some(here);
}
}
stacks
}
fn mark_column_items(column: &mut [LineMetrics], foot: &[bool]) {
let (body_size, body_bold) = column_body(column);
let candidates: Vec<usize> = (0..column.len())
.filter(|i| {
let line = &column[*i];
let numbered = line.marker.is_some_and(|marker| marker.is_ordered());
line.marker.is_some()
&& (!numbered || !foot[*i])
&& (!line.tabular || hangs_from_its_marker(line))
&& line.font_size > 0.0
&& line.font_size <= body_size * (1.0 + SIZE_TOLERANCE)
&& (!numbered || line.bold == body_bold)
})
.collect();
if candidates.len() < 2 {
return;
}
let mut by_edge: Vec<Vec<usize>> = Vec::new();
let mut sorted = candidates.clone();
sorted.sort_by(|a, b| {
column[*a]
.indent_left
.partial_cmp(&column[*b].indent_left)
.unwrap_or(Ordering::Equal)
});
for i in sorted {
let edge = column[i].indent_left;
match by_edge.last_mut() {
Some(group)
if edge - column[group[0]].indent_left
<= INDENT_MATCH_EM * column[i].font_size.max(1.0) =>
{
group.push(i)
}
_ => by_edge.push(vec![i]),
}
}
let markers: Vec<Option<Marker>> = column.iter().map(|line| line.marker).collect();
let marker_of = |i: usize| markers[i].expect("a candidate carries its marker");
let left = column.iter().map(|l| l.left).fold(f64::INFINITY, f64::min);
let measure = column
.iter()
.map(|l| l.right)
.fold(f64::NEG_INFINITY, f64::max);
let labels: Vec<bool> = (0..column.len())
.map(|i| {
let line = &column[i];
let short = line.right - left < LABEL_SHARE * (measure - left);
let next = column.get(i + 1);
let title = line.marker.is_some_and(|m| m.is_outline())
&& !line.ends_sentence()
&& next.is_some_and(|next| !wrapped_before(line, next, measure));
line.marker.is_some_and(|m| m.is_ordered())
&& (short || title)
&& !runs_on(&line.text)
&& next.is_none_or(|next| next.marker.is_none())
})
.collect();
let mut confirmed: Vec<(usize, Option<u32>)> = Vec::new();
let take = |sequence: &[usize], confirmed: &mut Vec<(usize, Option<u32>)>| {
if sequence.len() < 2 || sequence.iter().all(|i| labels[*i]) {
return;
}
let run: Vec<Marker> = sequence.iter().copied().map(marker_of).collect();
let roman = lists::is_roman(&run);
confirmed.extend(
sequence
.iter()
.zip(&run)
.map(|(i, marker)| (*i, marker.value(roman).filter(|_| !marker.keeps_its_text()))),
);
};
for group in &mut by_edge {
group.sort_unstable();
let mut sequence: Vec<usize> = Vec::new();
for i in group.iter().copied() {
if labels[i] && marker_of(i).is_outline() {
continue;
}
let mut extended: Vec<Marker> = sequence.iter().copied().map(marker_of).collect();
extended.push(marker_of(i));
if sequence.is_empty() || lists::is_a_run(&extended) {
sequence.push(i);
} else {
take(&sequence, &mut confirmed);
sequence = vec![i];
}
}
take(&sequence, &mut confirmed);
}
if confirmed.is_empty() {
return;
}
let tolerance = INDENT_MATCH_EM * body_size.max(1.0);
let mut edges: Vec<f64> = confirmed
.iter()
.map(|(i, _)| column[*i].indent_left)
.collect();
edges.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
let mut steps: Vec<f64> = Vec::new();
for edge in edges {
if steps.last().is_none_or(|last| edge - last > tolerance) {
steps.push(edge);
}
}
for (i, ordinal) in confirmed {
let edge = column[i].indent_left;
let level = steps
.iter()
.enumerate()
.min_by(|(_, a), (_, b)| {
(edge - *a)
.abs()
.partial_cmp(&(edge - *b).abs())
.unwrap_or(Ordering::Equal)
})
.map_or(0, |(rank, _)| rank)
.min(lists::MAX_LIST_LEVEL as usize) as u8;
let marker = marker_of(i);
column[i].item = Some(ItemMark {
len: if marker.keeps_its_text() {
0
} else {
marker.len
},
level,
ordinal,
text_left: column[i].marker_text_left,
});
}
}
fn hangs_from_its_marker(line: &LineMetrics) -> bool {
let (Some(text_left), [(_, gap_end)]) = (line.marker_text_left, line.wide_gaps.as_slice())
else {
return false;
};
(gap_end - text_left).abs() <= INDENT_MATCH_EM * line.font_size.max(1.0)
}
const LABEL_SHARE: f64 = 0.6;
fn wrapped_before(previous: &LineMetrics, line: &LineMetrics, measure: f64) -> bool {
let chars = previous.text.chars().filter(|c| !c.is_whitespace()).count();
let width = previous.right - previous.indent_left;
if chars == 0 || width <= 0.0 {
return false;
}
let advance = width / previous.text.trim().chars().count().max(1) as f64;
let Some(word) = line.text.split_whitespace().next() else {
return false;
};
let needed = (word.chars().count() + 1) as f64 * advance;
let room = measure - previous.right;
room >= 0.0 && room < needed
}
fn runs_on(text: &str) -> bool {
let text = text.trim_end();
text.ends_with([',', ';', ':', '-', '\u{2013}', '\u{2014}'])
|| text
.rsplit(char::is_whitespace)
.next()
.is_some_and(|last| matches!(last, "and" | "or" | "of" | "the" | "to"))
}
fn column_body(column: &[LineMetrics]) -> (f64, bool) {
let mut sizes: Vec<f64> = Vec::new();
let mut heavy = 0usize;
let mut total = 0usize;
for line in column {
let chars = line.text.chars().filter(|c| !c.is_whitespace()).count();
total += chars;
if line.bold {
heavy += chars;
}
if line.font_size > 0.0 {
sizes.extend(std::iter::repeat_n(line.font_size, chars.max(1)));
}
}
sizes.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
let size = sizes.get(sizes.len() / 2).copied().unwrap_or(0.0);
(size, total > 0 && heavy * 2 > total)
}
fn column_runs(metrics: &[LineMetrics]) -> Vec<(usize, usize)> {
let mut runs = Vec::new();
let mut start = 0usize;
for i in 1..metrics.len() {
let previous = &metrics[i - 1];
let current = &metrics[i];
let descends = previous.baseline - current.baseline
> MIN_BASELINE_STEP_EM * current.font_size.max(previous.font_size);
if !descends || overlap_fraction(previous, current) < COLUMN_OVERLAP_FRACTION {
runs.push((start, i));
start = i;
}
}
if start < metrics.len() {
runs.push((start, metrics.len()));
}
runs
}
fn body_left(metrics: &[LineMetrics]) -> f64 {
let mut sizes: Vec<f64> = metrics.iter().map(|m| m.font_size).collect();
sizes.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
let tolerance = INDENT_MATCH_EM * sizes[sizes.len() / 2].max(1.0);
let mut lefts: Vec<f64> = metrics.iter().map(|m| m.indent_left).collect();
lefts.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
let mut best = lefts.first().copied().unwrap_or(0.0);
let mut best_count = 0usize;
for (i, left) in lefts.iter().enumerate() {
let count = lefts[i..]
.iter()
.take_while(|l| **l - left <= tolerance)
.count();
if count > best_count {
best_count = count;
best = *left;
}
}
best
}
fn indent_style(metrics: &[LineMetrics], runs: &[(usize, usize, f64)]) -> IndentStyle {
let mut first_line = 0usize;
let mut hanging = 0usize;
for (start, end, margin) in runs {
let measure = metrics[*start..*end]
.iter()
.map(|m| m.right)
.fold(f64::NEG_INFINITY, f64::max);
for i in *start + 1..*end {
let line = &metrics[i];
if line.font_size <= 0.0 {
continue;
}
if line.indent_left - margin <= INDENT_MIN_EM * line.font_size {
continue;
}
let above = &metrics[i - 1];
if measure - above.right > SHORT_LINE_EM * above.font_size.max(line.font_size) {
first_line += 1;
} else {
hanging += 1;
}
}
}
if first_line == 0 && hanging == 0 {
IndentStyle::Flat
} else if first_line >= hanging {
IndentStyle::FirstLine
} else {
IndentStyle::Hanging
}
}
fn entries_of_a_list(metrics: &[LineMetrics], groups: &[Vec<usize>], margin: f64) -> Vec<bool> {
let hung = |group: &Vec<usize>| -> bool {
let first = &metrics[group[0]];
let em = first.font_size;
if group.len() < 2 || em <= 0.0 || first.indent_left - margin > INDENT_MIN_EM * em {
return false;
}
let hang = metrics[group[1]].indent_left;
hang - first.indent_left > INDENT_MIN_EM * em
&& group[1..]
.iter()
.all(|i| (metrics[*i].indent_left - hang).abs() <= INDENT_MATCH_EM * em)
};
let one_line_at_the_margin = |group: &Vec<usize>| -> bool {
let first = &metrics[group[0]];
group.len() == 1 && first.indent_left - margin <= INDENT_MIN_EM * first.font_size
};
let mut out = vec![false; groups.len()];
let mut start = 0;
while start < groups.len() {
let mut end = start;
let mut hung_count = 0;
while end < groups.len() && (hung(&groups[end]) || one_line_at_the_margin(&groups[end])) {
hung_count += usize::from(hung(&groups[end]));
end += 1;
}
let (mut first, mut last) = (start, end);
while first < last && !hung(&groups[first]) {
first += 1;
}
while last > first && !hung(&groups[last - 1]) {
last -= 1;
}
if hung_count >= 3 && 2 * hung_count >= last - first {
out[first..last].fill(true);
}
start = end.max(start + 1);
}
out
}
fn rule_between(above: &LineMetrics, below: &LineMetrics, rules: &[HorizontalRule]) -> bool {
rule_between_boxes(
[above.left, above.bottom, above.right, above.top],
[below.left, below.bottom, below.right, below.top],
rules,
)
}
pub(crate) fn rule_between_boxes(
above: [f64; 4],
below: [f64; 4],
rules: &[HorizontalRule],
) -> bool {
let left = above[0].min(below[0]);
let right = above[2].max(below[2]);
rules.iter().any(|rule| {
rule.y >= below[3] && rule.y <= above[1] && rule.left < right && rule.right > left
})
}
fn run_leading(metrics: &[LineMetrics], page_leading: f64) -> f64 {
let em = metrics
.iter()
.map(|m| m.font_size)
.fold(0.0_f64, f64::max)
.max(1.0);
let mut steps: Vec<f64> = metrics
.windows(2)
.map(|pair| pair[0].baseline - pair[1].baseline)
.filter(|step| *step > 0.0 && *step < 4.0 * em)
.collect();
if steps.is_empty() {
return if page_leading > 0.0 {
page_leading
} else {
SOLID_PITCH_EM * em
};
}
steps.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
steps[steps.len() / 2]
}
fn leading_of(metrics: &[LineMetrics], current: &[usize], run_leading: f64) -> f64 {
if current.len() >= 2 {
let mut steps: Vec<f64> = current
.windows(2)
.map(|pair| metrics[pair[0]].baseline - metrics[pair[1]].baseline)
.collect();
steps.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
return steps[steps.len() / 2];
}
run_leading
}
fn tracing() -> bool {
static ON: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
*ON.get_or_init(|| std::env::var_os("PDFLUENT_BLOCK_TRACE").is_some())
}
#[allow(clippy::too_many_arguments)]
fn under_the_hang(metrics: &[LineMetrics], current: &[usize], line: &LineMetrics, em: f64) -> bool {
let first = &metrics[current[0]];
match first.item.map(|item| item.text_left) {
Some(Some(text_left)) => {
text_left - first.indent_left > INDENT_MIN_EM * em
&& line.indent_left >= text_left - INDENT_MATCH_EM * em
}
Some(None) => line.indent_left - first.indent_left > INDENT_MIN_EM * em,
None => false,
}
}
fn within_the_lists_pitch(metrics: &[LineMetrics], current: &[usize], step: f64, em: f64) -> bool {
let first = current[0];
let top = metrics[first].baseline;
let next_item = metrics
.iter()
.skip(first + 1)
.take(HANG_LOOKAHEAD_LINES)
.find(|m| m.item.is_some() && m.baseline < top);
let pitch = match next_item {
Some(next) => top - next.baseline,
None => match first.checked_sub(1) {
Some(before) => metrics[before].baseline - top,
None => return true,
},
};
pitch <= 0.0 || step <= pitch + SIZE_TOLERANCE * em
}
const HANG_LOOKAHEAD_LINES: usize = 6;
#[derive(Debug, Clone, Copy)]
struct Column {
margin: f64,
right: f64,
}
fn continues(
metrics: &[LineMetrics],
current: &[usize],
next: usize,
style: IndentStyle,
column: Column,
rules: &[HorizontalRule],
leading: f64,
) -> bool {
let margin = column.margin;
let previous = &metrics[*current.last().expect("a paragraph holds a line")];
let line = &metrics[next];
macro_rules! no {
($reason:expr) => {{
if tracing() {
eprintln!("BREAK {} | {:?} -> {:?}", $reason, previous.text, line.text);
}
return false;
}};
}
if previous.tabular || line.tabular {
no!("tabular");
}
if line.item.is_some() {
no!("list item");
}
let em = previous.font_size.max(line.font_size);
if em <= 0.0 {
no!("no type size");
}
let step = previous.baseline - line.baseline;
if step <= MIN_BASELINE_STEP_EM * em {
no!("same line");
}
let hung = step <= HANG_MAX_LEADING_EM * em
&& under_the_hang(metrics, current, line, em)
&& within_the_lists_pitch(metrics, current, step, em);
if step > leading_of(metrics, current, leading) * PARAGRAPH_LEADING_TOLERANCE && !hung {
no!(format!(
"leading {step:.2} over {:.2}",
leading_of(metrics, current, leading)
));
}
if step > MAX_LEADING_EM * em && !hung {
no!(format!("a line of white: {step:.2} on {em:.2} of type"));
}
if (line.font_size - previous.font_size).abs() > SIZE_TOLERANCE * em {
no!(format!(
"type size {:.3} vs {:.3}",
previous.font_size, line.font_size
));
}
if line.bold != previous.bold {
no!(format!(
"weight {} vs {}",
if previous.bold { "bold" } else { "regular" },
if line.bold { "bold" } else { "regular" }
));
}
if overlap_fraction(previous, line) < COLUMN_OVERLAP_FRACTION {
no!("column");
}
if rule_between(previous, line, rules) {
no!("rule");
}
let measure = current
.iter()
.map(|i| metrics[*i].right)
.chain(std::iter::once(line.right))
.fold(f64::NEG_INFINITY, f64::max);
if previous.ends_sentence() && measure - previous.right > SHORT_LINE_EM * em {
no!("short line");
}
if let Some(item) = metrics[current[0]].item {
let marker_left = metrics[current[0]].indent_left;
match item.text_left {
Some(text_left) => {
if line.indent_left >= text_left - INDENT_MATCH_EM * em {
return true;
}
if !(style == IndentStyle::FirstLine
&& line.indent_left < marker_left - INDENT_MIN_EM * em)
{
no!("the line is back at the item's marker edge");
}
}
None if current.len() == 1 => {
if line.indent_left - marker_left <= INDENT_MIN_EM * em
&& measure - previous.right > SHORT_LINE_EM * em
{
no!("the item ended short of the measure");
}
if line.indent_left - marker_left > INDENT_MIN_EM * em
&& (measure - previous.right <= SHORT_LINE_EM * em
|| runs_on(&previous.text)
|| wrapped_before(previous, line, column.right))
{
return true;
}
}
None => {
let hang = metrics[current[1]].indent_left;
if hang - marker_left > INDENT_MIN_EM * em
&& (line.indent_left - hang).abs() <= INDENT_MATCH_EM * em
{
return true;
}
}
}
}
match style {
IndentStyle::FirstLine => {
if line.indent_left - margin > INDENT_MIN_EM * em {
no!("first-line indent");
}
true
}
IndentStyle::Hanging | IndentStyle::Flat => {
let body = if current.len() >= 2 {
current[1..]
.iter()
.map(|i| metrics[*i].indent_left)
.fold(f64::INFINITY, f64::min)
} else {
previous.indent_left
};
if line.indent_left - body < -INDENT_MIN_EM * em {
no!("outdent");
}
true
}
}
}
pub(crate) fn join_lines(lines: &[String]) -> String {
let mut out = String::new();
for line in lines {
let trimmed = line.trim();
if trimmed.is_empty() {
continue;
}
if out.is_empty() {
out.push_str(trimmed);
continue;
}
if is_hyphen_wrap_candidate(&out, trimmed) {
out.pop();
out.push_str(trimmed);
} else {
out.push(' ');
out.push_str(trimmed);
}
}
out
}
fn assemble(
page: usize,
index: usize,
lines: &[&TextBlock],
metrics: &[&LineMetrics],
item: Option<ItemMark>,
) -> Block {
let mut spans: Vec<TextSpan> = Vec::new();
let mut texts: Vec<String> = Vec::new();
let displaced = metrics
.iter()
.enumerate()
.skip(1)
.find_map(|(i, m)| m.initial.map(|s| (i, s)))
.filter(|(i, s)| {
metrics[*i]
.text
.starts_with(lines[*i].spans[*s].text.as_str())
});
if let Some((line, span)) = displaced {
spans.push(lines[line].spans[span].clone());
texts.push(lines[line].spans[span].text.clone());
}
for (i, line) in lines.iter().enumerate() {
for (s, span) in line.spans.iter().enumerate() {
if displaced == Some((i, s)) {
continue;
}
spans.push(span.clone());
}
let text = match displaced {
Some((displaced_line, span)) if displaced_line == i => metrics[i]
.text
.strip_prefix(lines[i].spans[span].text.as_str())
.expect("the prefix `displaced` was chosen for")
.to_string(),
_ => metrics[i].text.clone(),
};
texts.push(text);
}
let mut text = join_lines(&texts);
if let Some(item) = item {
let marker = metrics
.first()
.and_then(|m| m.text.get(..item.len))
.unwrap_or_default()
.trim();
if let Some(rest) = text.strip_prefix(marker) {
text = rest.trim_start().to_string();
}
}
let mut block = Block {
kind: match item {
Some(item) => BlockKind::ListItem {
level: item.level,
ordinal: item.ordinal,
},
None => BlockKind::Paragraph,
},
page,
bbox: [0.0; 4],
text,
spans,
index,
continues_previous: false,
confidence: None,
grid: None,
table_origin: TableOrigin::Other,
trace_learned: None,
};
recompute_bbox(&mut block);
block
}
enum Group {
Lines(Vec<usize>),
Table(tables::Table),
}
fn table_rows(metrics: &[LineMetrics], start: usize, end: usize) -> Vec<tables::Row> {
let baselines_of = |tabular_only: bool| -> Vec<f64> {
let mut baselines: Vec<f64> = (start..end)
.filter(|i| !tabular_only || !metrics[*i].wide_gaps.is_empty())
.map(|i| metrics[i].baseline)
.collect();
baselines.sort_by(|a, b| b.partial_cmp(a).unwrap_or(Ordering::Equal));
baselines.dedup_by(|a, b| (*a - *b).abs() < SAME_BASELINE);
baselines
};
let steps_of = |baselines: Vec<f64>| -> Vec<f64> {
let mut steps: Vec<f64> = baselines.windows(2).map(|pair| pair[0] - pair[1]).collect();
steps.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
steps
};
let steps = match steps_of(baselines_of(true)) {
tabular if !tabular.is_empty() => tabular,
_ => steps_of(baselines_of(false)),
};
let pitch = match steps.len() {
0 => f64::INFINITY,
len => steps[len / 2] * ROW_PITCH_FRACTION,
};
let leading = wrapped_leading(&steps_of(baselines_of(false)));
let mut rows: Vec<(usize, usize)> = Vec::new();
let mut top = f64::NEG_INFINITY;
let mut previous = f64::NEG_INFINITY;
let mut opener: Vec<f64> = Vec::new();
for (i, line) in metrics.iter().enumerate().take(end).skip(start) {
let gap_up = top - line.baseline;
let step = previous - line.baseline;
let starts = if leading.is_some() {
cell_starts(line)
} else {
Vec::new()
};
let in_the_same_cells = starts.iter().all(|at| {
opener
.iter()
.any(|was| (at - was).abs() <= line.font_size * CELL_LEFT_EM)
});
let gap_down = (i + 1..end)
.map(|j| line.baseline - metrics[j].baseline)
.find(|step| *step > SAME_BASELINE)
.unwrap_or(f64::INFINITY);
let continues_the_row = gap_up <= SAME_BASELINE
|| match leading {
Some(rail) => step <= rail + SAME_BASELINE && in_the_same_cells,
None => gap_up < pitch && line.wide_gaps.is_empty() && gap_up < gap_down,
};
match rows.last_mut() {
Some(row) if continues_the_row => {
row.1 = i + 1;
top = top.max(line.baseline);
opener.extend(starts);
}
_ => {
rows.push((i, i + 1));
top = line.baseline;
opener = starts;
}
}
previous = line.baseline;
}
let rows = match leading {
None => rows,
Some(_) => rows
.into_iter()
.flat_map(|(first, end)| unfold_whole_lines(metrics, first, end))
.collect(),
};
rows.into_iter()
.map(|(first, end)| {
let lines = &metrics[first..end];
tables::Row {
first,
end,
left: lines.iter().map(|m| m.left).fold(f64::INFINITY, f64::min),
right: lines
.iter()
.map(|m| m.right)
.fold(f64::NEG_INFINITY, f64::max),
top: lines
.iter()
.map(|m| m.top)
.fold(f64::NEG_INFINITY, f64::max),
bottom: lines.iter().map(|m| m.bottom).fold(f64::INFINITY, f64::min),
font_size: dominant_size(lines),
bold: lines.iter().filter(|m| m.bold).count() * 2 > lines.len(),
}
})
.collect()
}
fn unfold_whole_lines(metrics: &[LineMetrics], first: usize, end: usize) -> Vec<(usize, usize)> {
let mut baselines: Vec<(usize, usize)> = Vec::new();
for i in first..end {
match baselines.last_mut() {
Some(group)
if (metrics[group.0].baseline - metrics[i].baseline).abs() <= SAME_BASELINE =>
{
group.1 = i + 1
}
_ => baselines.push((i, i + 1)),
}
}
if baselines.len() < 2 {
return vec![(first, end)];
}
let starts_of = |group: &(usize, usize)| -> Vec<f64> {
(group.0..group.1)
.flat_map(|i| cell_starts(&metrics[i]))
.collect()
};
let em = metrics[first].font_size.max(f64::MIN_POSITIVE) * CELL_LEFT_EM;
let whole: Vec<f64> = baselines.iter().flat_map(starts_of).collect();
let is_whole = |group: &(usize, usize)| -> bool {
let mine = starts_of(group);
whole
.iter()
.all(|was| mine.iter().any(|at| (at - was).abs() <= em))
};
let column_one = starts_of(&baselines[0])
.into_iter()
.fold(f64::INFINITY, f64::min);
let a_sparse_row = |group: &(usize, usize)| -> bool {
let mine = starts_of(group);
mine.len() == 1 && (mine[0] - column_one).abs() <= em
};
let wrapped = baselines[1..]
.iter()
.any(|group| !is_whole(group) && !a_sparse_row(group));
if wrapped {
vec![(first, end)]
} else {
baselines
}
}
fn cell_starts(line: &LineMetrics) -> Vec<f64> {
std::iter::once(line.left)
.chain(line.wide_gaps.iter().map(|(_, to)| *to))
.collect()
}
fn wrapped_leading(steps: &[f64]) -> Option<f64> {
if steps.len() <= ROW_PITCH_CLUSTER {
return None;
}
let last = steps.len() - ROW_PITCH_CLUSTER;
steps
.windows(2)
.enumerate()
.take_while(|(at, _)| *at < last)
.find(|(_, pair)| pair[0] > 0.0 && pair[1] / pair[0] >= ROW_PITCH_JUMP)
.map(|(_, pair)| pair[0])
}
fn dominant_size(lines: &[LineMetrics]) -> f64 {
let mut sizes: Vec<f64> = lines
.iter()
.map(|m| m.font_size)
.filter(|s| *s > 0.0)
.collect();
sizes.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
sizes.get(sizes.len() / 2).copied().unwrap_or(0.0)
}
fn assemble_cell(
page: usize,
lines: &[&TextBlock],
cell: &tables::Cell,
doubt: GridDoubt,
origin: TableOrigin,
cell_path_words: bool,
) -> Block {
let mut spans: Vec<TextSpan> = cell
.spans
.iter()
.map(|(line, span)| lines[*line].spans[*span].clone())
.collect();
spans.sort_by(|a, b| {
b.y.partial_cmp(&a.y)
.unwrap_or(Ordering::Equal)
.then(a.x.partial_cmp(&b.x).unwrap_or(Ordering::Equal))
});
let mut rows: Vec<Vec<TextSpan>> = Vec::new();
for span in &spans {
let same_line = rows.last().is_some_and(|row: &Vec<TextSpan>| {
let previous: &TextSpan = &row[0];
(previous.y - span.y).abs() <= previous.font_size.max(span.font_size) * 0.5
});
match rows.last_mut() {
Some(row) if same_line => row.push(span.clone()),
_ => rows.push(vec![span.clone()]),
}
}
let texts: Vec<String> = rows
.into_iter()
.map(|spans| TextBlock { spans }.text_with_cell_path_words(cell_path_words))
.collect();
let mut block = Block {
kind: BlockKind::TableCell {
row: cell.row,
column: cell.column,
row_span: cell.row_span,
column_span: cell.column_span,
header: cell.header,
},
page,
bbox: [0.0; 4],
text: join_lines(&texts),
spans,
index: 0,
continues_previous: false,
confidence: None,
grid: Some(doubt),
table_origin: origin,
trace_learned: None,
};
recompute_bbox(&mut block);
block
}
pub(crate) fn recompute_bbox(block: &mut Block) {
let mut bbox = [
f64::INFINITY,
f64::INFINITY,
f64::NEG_INFINITY,
f64::NEG_INFINITY,
];
for span in &block.spans {
let (bottom, top) = span_extent(span);
bbox[0] = bbox[0].min(span.x);
bbox[1] = bbox[1].min(bottom);
bbox[2] = bbox[2].max(span_right(span));
bbox[3] = bbox[3].max(top);
}
block.bbox = if bbox.iter().all(|v| v.is_finite()) {
bbox
} else {
[0.0; 4]
};
}
fn dominant_face(line: &TextBlock) -> Option<&str> {
dominant_face_of_spans(&line.spans)
}
pub(crate) fn dominant_face_of_spans(spans: &[TextSpan]) -> Option<&str> {
let mut faces: Vec<(Option<&str>, usize)> = Vec::new();
for span in spans {
let face = span.font_name.as_deref();
let chars = char_count(span);
match faces.iter_mut().find(|(held, _)| *held == face) {
Some(entry) => entry.1 += chars,
None => faces.push((face, chars)),
}
}
faces
.into_iter()
.max_by_key(|(_, count)| *count)
.and_then(|(face, _)| face)
}
fn ends_terminally(text: &str) -> bool {
let trimmed = text
.trim_end()
.trim_end_matches(['"', '\'', '”', '’', ')', ']', '»']);
matches!(
trimmed.chars().next_back(),
Some('.') | Some('!') | Some('?')
)
}
fn opens_lowercase(text: &str) -> bool {
text.chars()
.find(|c| c.is_alphabetic())
.is_some_and(|c| c.is_lowercase())
}
pub(crate) fn median_step(steps: &mut [f64]) -> f64 {
if steps.is_empty() {
return 0.0;
}
steps.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
steps[steps.len() / 2]
}
pub(crate) struct JoinLine<'a> {
pub left: f64,
pub indent_left: f64,
pub right: f64,
pub baseline: f64,
pub top: f64,
pub bottom: f64,
pub font_size: f64,
pub bold: bool,
pub face: Option<&'a str>,
pub text: &'a str,
pub marker_or_item: bool,
pub tabular: bool,
}
impl<'a> JoinLine<'a> {
fn of(metrics: &'a LineMetrics, face: Option<&'a str>, marker_or_item: bool) -> Self {
Self {
left: metrics.left,
indent_left: metrics.indent_left,
right: metrics.right,
baseline: metrics.baseline,
top: metrics.top,
bottom: metrics.bottom,
font_size: metrics.font_size,
bold: metrics.bold,
face,
text: &metrics.text,
marker_or_item,
tabular: metrics.tabular,
}
}
}
pub(crate) fn narrow_column_pair_joins(
above: &JoinLine,
above_item: bool,
below: &JoinLine,
pitch: f64,
measure: f64,
rules: &[HorizontalRule],
) -> bool {
if below.marker_or_item {
return false;
}
if above_item {
return false;
}
if above.tabular || below.tabular {
return false;
}
if rule_between_boxes(
[above.left, above.bottom, above.right, above.top],
[below.left, below.bottom, below.right, below.top],
rules,
) {
return false;
}
let em = above.font_size.max(below.font_size);
if em <= 0.0 {
return false;
}
let step = above.baseline - below.baseline;
if step <= MIN_BASELINE_STEP_EM * em
|| step > NARROW_PITCH_MULT * pitch
|| step > MAX_LEADING_EM * em
{
return false;
}
if (above.font_size - below.font_size).abs() > NARROW_SIZE_PT {
return false;
}
if above.bold != below.bold || above.face != below.face {
return false;
}
let ragged = |m: &JoinLine| measure - m.right > SHORT_LINE_EM * em;
if (above.indent_left - below.indent_left).abs() > NARROW_X0_EM * em
&& !(ragged(above)
&& ragged(below)
&& overlap_fraction_of(above.left, above.right, below.left, below.right)
>= COLUMN_OVERLAP_FRACTION)
{
return false;
}
if ends_terminally(above.text) && opens_lowercase(below.text) && !ragged(above) {
return false;
}
if above.text.trim_end().ends_with(':') {
return false;
}
true
}
fn join_narrow_columns(
groups: &mut Vec<(usize, Group)>,
metrics: &[LineMetrics],
lines: &[&TextBlock],
runs: &[(usize, usize, f64)],
shapes: &[(f64, f64)],
rules: &[HorizontalRule],
entries: &std::collections::HashSet<usize>,
) {
let joinable = |open: &[usize], open_joined: bool, next: &[usize]| -> bool {
if next.len() != 1 || (open.len() != 1 && !open_joined) {
return false;
}
let (Some(&last), Some(&first), Some(&at)) = (open.last(), open.first(), next.first())
else {
return false;
};
let above = &metrics[last];
let below = &metrics[at];
let em = above.font_size.max(below.font_size);
let pitch = if open.len() >= 2 {
let mut steps: Vec<f64> = open
.windows(2)
.map(|pair| metrics[pair[0]].baseline - metrics[pair[1]].baseline)
.collect();
median_step(&mut steps)
} else {
runs.iter()
.zip(shapes.iter())
.find(|((start, end, _), _)| *start <= last && last < *end)
.map(|(_, shape)| shape.0)
.unwrap_or(0.0)
.max(SOLID_PITCH_EM * em)
};
let measure = runs
.iter()
.zip(shapes.iter())
.filter(|((start, end, _), _)| {
(*start <= last && last < *end) || (*start <= at && at < *end)
})
.map(|(_, shape)| shape.1)
.fold(f64::NEG_INFINITY, f64::max);
let upper = JoinLine::of(
above,
dominant_face(lines[last]),
false,
);
let lower = JoinLine::of(
below,
dominant_face(lines[at]),
below.marker.is_some() || below.item.is_some() || entries.contains(&at),
);
let above_item = metrics[first].item.is_some() || entries.contains(&first);
narrow_column_pair_joins(&upper, above_item, &lower, pitch, measure, rules)
};
let mut out: Vec<(usize, Group)> = Vec::with_capacity(groups.len());
let mut open: Option<(usize, Vec<usize>, bool)> = None;
for (first, group) in std::mem::take(groups) {
match group {
Group::Table(table) => {
if let Some((key, lines, _)) = open.take() {
out.push((key, Group::Lines(lines)));
}
out.push((first, Group::Table(table)));
}
Group::Lines(next) => {
let join = match &open {
Some((_, open_lines, open_joined)) => joinable(open_lines, *open_joined, &next),
None => false,
};
if join {
if tracing() {
if let Some((_, open_lines, _)) = &open {
let a = open_lines
.last()
.map(|i| metrics[*i].text.as_str())
.unwrap_or("");
let b = next
.first()
.map(|i| metrics[*i].text.as_str())
.unwrap_or("");
eprintln!("JOIN narrow-column | {a:?} -> {b:?}");
}
}
let (_, open_lines, open_joined) =
open.as_mut().expect("a join has a block above it");
open_lines.extend(next);
*open_joined = true;
} else {
if let Some((key, lines, _)) = open.take() {
out.push((key, Group::Lines(lines)));
}
open = Some((first, next, false));
}
}
}
}
if let Some((key, lines, _)) = open.take() {
out.push((key, Group::Lines(lines)));
}
*groups = out;
}
const FUSED_MARKER_GAP_EM: f64 = 2.0;
const FUSED_BASELINE_PT: f64 = 1.0;
fn lone_marker_glyph(line: &TextBlock) -> Option<char> {
let mut found = None;
for span in &line.spans {
for c in span.text.chars() {
if c.is_whitespace() {
continue;
}
if found.is_some() || !lists::BULLET_CHARS.contains(&c) {
return None;
}
found = Some(c);
}
}
found
}
struct FusedPage {
lines: Vec<TextBlock>,
bounds: Vec<(usize, usize)>,
table_first: Vec<bool>,
}
fn fuse_lone_markers(
lines: &[&TextBlock],
bounds: &[(usize, usize)],
table_first: &[bool],
cell_path_words: bool,
) -> Option<FusedPage> {
if !lines.iter().any(|line| lone_marker_glyph(line).is_some()) {
return None;
}
let baseline = |line: &TextBlock| anchor_span(line.spans.iter()).map(|s| s.y).unwrap_or(0.0);
let left = |line: &TextBlock| line.spans.iter().map(|s| s.x).fold(f64::INFINITY, f64::min);
let right = |line: &TextBlock| {
line.spans
.iter()
.map(span_right)
.fold(f64::NEG_INFINITY, f64::max)
};
let mut donated: Vec<Option<Vec<TextSpan>>> = vec![None; lines.len()];
let mut killed = vec![false; lines.len()];
for (i, marker) in lines.iter().enumerate() {
let Some(_) = lone_marker_glyph(marker) else {
continue;
};
let em = anchor_span(marker.spans.iter())
.map(|s| s.font_size.max(1.0))
.unwrap_or(1.0);
let base = baseline(marker);
let edge = right(marker);
let mut best: Option<(usize, f64)> = None;
for (j, line) in lines.iter().enumerate() {
if i == j || killed[j] || donated[j].is_some() || lone_marker_glyph(line).is_some() {
continue;
}
if line
.text_with_cell_path_words(cell_path_words)
.trim()
.is_empty()
{
continue;
}
if lists::marker_at(
&line.text_with_cell_path_words(cell_path_words),
lists::Lead::default(),
)
.is_some()
{
continue;
}
if (baseline(line) - base).abs() > FUSED_BASELINE_PT {
continue;
}
let start = left(line);
if start <= edge {
continue;
}
let gap = start - edge;
if gap > FUSED_MARKER_GAP_EM * em {
continue;
}
if best.is_none_or(|(_, known): (usize, f64)| gap < known) {
best = Some((j, gap));
}
}
if let Some((j, _)) = best {
let mut spans = marker.spans.clone();
spans.extend(lines[j].spans.iter().cloned());
spans.sort_by(|a, b| a.x.partial_cmp(&b.x).unwrap_or(Ordering::Equal));
donated[j] = Some(spans);
killed[i] = true;
}
}
if donated.iter().all(Option::is_none) {
return None;
}
let mut region_of = vec![0usize; lines.len()];
for (region, &(start, end)) in bounds.iter().enumerate() {
for slot in region_of.iter_mut().take(end.min(lines.len())).skip(start) {
*slot = region;
}
}
let mut owned: Vec<TextBlock> = Vec::with_capacity(lines.len());
let mut regions: Vec<usize> = Vec::with_capacity(lines.len());
for (i, line) in lines.iter().enumerate() {
if killed[i] {
continue;
}
match donated[i].take() {
Some(spans) => owned.push(TextBlock { spans }),
None => owned.push((*line).clone()),
}
regions.push(region_of[i]);
}
let mut fused_bounds: Vec<(usize, usize)> = Vec::new();
let mut fused_first: Vec<bool> = Vec::new();
for (i, region) in regions.iter().enumerate() {
if i > 0 && regions[i - 1] == *region {
fused_bounds.last_mut().expect("a bound is open").1 = i + 1;
} else {
fused_bounds.push((i, i + 1));
fused_first.push(table_first.get(*region).copied().unwrap_or(false));
}
}
Some(FusedPage {
lines: owned,
bounds: fused_bounds,
table_first: fused_first,
})
}
const GUTTER_SUPPORT_LINES: usize = 3;
const GUTTER_HALF_MIN_CHARS: usize = 8;
struct SplitPage {
lines: Vec<TextBlock>,
bounds: Vec<(usize, usize)>,
in_table: Vec<bool>,
}
type LineGap = (usize, f64, f64);
fn split_fused_lines(
lines: &[&TextBlock],
metrics: &[LineMetrics],
bounds: &[(usize, usize)],
in_table: &[bool],
groups: &mut [(usize, Group)],
) -> Option<SplitPage> {
let mut gaps: Vec<LineGap> = Vec::new();
for (i, line) in metrics.iter().enumerate() {
if in_table[i] {
continue;
}
for &(end, start) in &line.wide_gaps {
gaps.push((i, end, start));
}
}
if gaps.len() < GUTTER_SUPPORT_LINES {
return None;
}
gaps.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));
let mut clusters: Vec<(Vec<usize>, Vec<LineGap>)> = Vec::new();
for (line, end, start) in gaps {
match clusters.last_mut() {
Some((member_lines, members))
if members.iter().any(|&(_, e, s)| end <= s && e <= start) =>
{
if !member_lines.contains(&line) {
member_lines.push(line);
}
members.push((line, end, start));
}
_ => clusters.push((vec![line], vec![(line, end, start)])),
}
}
let gutters: Vec<&Vec<LineGap>> = clusters
.iter()
.filter(|(member_lines, _)| member_lines.len() >= GUTTER_SUPPORT_LINES)
.map(|(_, members)| members)
.collect();
if gutters.is_empty() {
return None;
}
let in_a_gutter = |line: usize, end: f64, start: f64| {
gutters.iter().any(|members| {
members
.iter()
.any(|&(l, e, s)| l == line && e == end && s == start)
})
};
let x_order = |line: &TextBlock| {
let mut order: Vec<usize> = (0..line.spans.len()).collect();
order.sort_by(|a, b| {
line.spans[*a]
.x
.partial_cmp(&line.spans[*b].x)
.unwrap_or(Ordering::Equal)
});
order
};
let mut halves: Vec<Option<Vec<TextBlock>>> = vec![None; lines.len()];
let mut marks: Vec<Vec<bool>> = vec![Vec::new(); lines.len()];
for (i, line) in lines.iter().enumerate() {
if in_table[i] {
continue;
}
let order = x_order(line);
let mut cuts = vec![false; order.len().saturating_sub(1)];
for (k, pair) in order.windows(2).enumerate() {
let end = span_right(&line.spans[pair[0]]);
let start = line.spans[pair[1]].x;
cuts[k] = end < start && in_a_gutter(i, end, start);
}
if !cuts.iter().any(|cut| *cut) {
continue;
}
let mut parts: Vec<TextBlock> = Vec::new();
let mut at = 0usize;
for (k, cut) in cuts.iter().enumerate() {
if *cut {
parts.push(TextBlock {
spans: order[at..=k]
.iter()
.map(|j| line.spans[*j].clone())
.collect(),
});
at = k + 1;
}
}
parts.push(TextBlock {
spans: order[at..].iter().map(|j| line.spans[*j].clone()).collect(),
});
let measured: Vec<LineMetrics> = parts.iter().map(LineMetrics::of).collect();
let substantial = measured.iter().all(|half| {
half.text.chars().filter(|c| !c.is_whitespace()).count() >= GUTTER_HALF_MIN_CHARS
});
if !substantial {
continue;
}
marks[i] = measured.iter().map(|half| half.marker.is_some()).collect();
halves[i] = Some(parts);
}
let mut bearing = vec![false; lines.len()];
for (start, end) in column_stacks(metrics, bounds) {
let count: usize = (start..end)
.map(|i| marks[i].iter().filter(|marked| **marked).count())
.sum();
if count >= 2 {
bearing[start..end].fill(true);
}
}
if !halves
.iter()
.enumerate()
.any(|(i, parts)| parts.is_some() && bearing[i])
{
return None;
}
let mut region_of = vec![0usize; lines.len()];
for (region, &(start, end)) in bounds.iter().enumerate() {
for slot in region_of.iter_mut().take(end.min(lines.len())).skip(start) {
*slot = region;
}
}
let split: Vec<bool> = halves
.iter()
.enumerate()
.map(|(i, parts)| parts.is_some() && bearing[i])
.collect();
let mut owned: Vec<TextBlock> = Vec::with_capacity(lines.len());
let mut regions: Vec<usize> = Vec::with_capacity(lines.len());
let mut tabled: Vec<bool> = Vec::with_capacity(lines.len());
let mut moved: Vec<usize> = vec![0; lines.len()];
for (i, line) in lines.iter().enumerate() {
moved[i] = owned.len();
match halves[i].take() {
Some(parts) if split[i] => {
for part in parts {
owned.push(part);
regions.push(region_of[i]);
tabled.push(false);
}
}
_ => {
owned.push((*line).clone());
regions.push(region_of[i]);
tabled.push(in_table[i]);
}
}
}
let mut split_bounds: Vec<(usize, usize)> = Vec::new();
for (i, region) in regions.iter().enumerate() {
if i > 0 && regions[i - 1] == *region {
split_bounds.last_mut().expect("a bound is open").1 = i + 1;
} else {
split_bounds.push((i, i + 1));
}
}
debug_assert_eq!(
split_bounds.len(),
bounds.len(),
"a split adds lines to regions, never regions"
);
for (first, group) in groups.iter_mut() {
*first = moved[*first];
if let Group::Table(table) = group {
for cell in table.cells.iter_mut() {
for (line, _) in cell.spans.iter_mut() {
debug_assert!(!split[*line], "a table holds no split line");
*line = moved[*line];
}
}
}
}
Some(SplitPage {
lines: owned,
bounds: split_bounds,
in_table: tabled,
})
}
#[cfg(test)]
pub(crate) fn paragraphs(
page: usize,
first_index: usize,
regions: &[Vec<TextBlock>],
whole: &[bool],
rules: &[HorizontalRule],
page_leading: f64,
table_strategy: TableStrategy,
) -> Vec<Block> {
paragraphs_with_cell_path_words(
page,
first_index,
regions,
whole,
rules,
page_leading,
table_strategy,
true,
)
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn paragraphs_with_cell_path_words(
page: usize,
first_index: usize,
regions: &[Vec<TextBlock>],
whole: &[bool],
rules: &[HorizontalRule],
page_leading: f64,
table_strategy: TableStrategy,
cell_path_words: bool,
) -> Vec<Block> {
let mut lines: Vec<&TextBlock> = Vec::new();
let mut bounds: Vec<(usize, usize)> = Vec::new();
let mut table_first: Vec<bool> = Vec::new();
for (k, region) in regions.iter().enumerate() {
let start = lines.len();
lines.extend(region.iter().filter(|line| !line.spans.is_empty()));
if lines.len() > start {
bounds.push((start, lines.len()));
table_first.push(whole.get(k).copied().unwrap_or(false));
}
}
if lines.is_empty() {
return Vec::new();
}
let owned;
if let Some(fused) = fuse_lone_markers(&lines, &bounds, &table_first, cell_path_words) {
owned = fused.lines;
lines = owned.iter().collect();
bounds = fused.bounds;
table_first = fused.table_first;
}
let mut metrics: Vec<LineMetrics> = lines
.iter()
.map(|line| LineMetrics::of_with(line, true, cell_path_words))
.collect();
mark_tabular(&mut metrics);
confirm_initials(&mut metrics, &lines, cell_path_words);
let mut groups: Vec<(usize, Group)> = Vec::new();
let mut in_table: Vec<bool> = vec![false; lines.len()];
for ((region_start, region_end), whole) in bounds.iter().zip(&table_first) {
let rows = table_rows(&metrics, *region_start, *region_end);
let _trace_page = crate::table_trace::trace_page_guard(page);
let found = if *whole {
tables::find_whole(&lines, &rows, rules)
} else {
tables::find(&lines, &rows, rules)
};
let found = match table_strategy {
TableStrategy::Lines => found
.into_iter()
.filter(|table| tables::table_has_ruling(&rows, table, rules))
.collect(),
TableStrategy::Text | TableStrategy::Both => found,
};
for table in found {
let (first, end) = (rows[table.first].first, rows[table.end - 1].end);
in_table[first..end].fill(true);
groups.push((first, Group::Table(table)));
}
}
let split_owned;
if let Some(split) = split_fused_lines(&lines, &metrics, &bounds, &in_table, &mut groups) {
split_owned = split.lines;
lines = split_owned.iter().collect();
bounds = split.bounds;
in_table = split.in_table;
metrics = lines
.iter()
.map(|line| LineMetrics::of_with(line, true, cell_path_words))
.collect();
mark_tabular(&mut metrics);
confirm_initials(&mut metrics, &lines, cell_path_words);
}
let mut stretches: Vec<(usize, usize)> = Vec::new();
for (region_start, region_end) in &bounds {
let mut start = *region_start;
for (i, held) in in_table
.iter()
.enumerate()
.take(*region_end)
.skip(*region_start)
{
if *held {
if start < i {
stretches.push((start, i));
}
start = i + 1;
}
}
if start < *region_end {
stretches.push((start, *region_end));
}
}
let runs: Vec<(usize, usize, f64)> = stretches
.iter()
.flat_map(|(stretch_start, stretch_end)| {
column_runs(&metrics[*stretch_start..*stretch_end])
.into_iter()
.map(|(first, last)| (stretch_start + first, stretch_start + last))
.collect::<Vec<_>>()
})
.map(|(start, end)| (start, end, body_left(&metrics[start..end])))
.collect();
mark_list_items(&mut metrics, &bounds);
let style = indent_style(&metrics, &runs);
let run_shapes: Vec<(f64, f64)> = runs
.iter()
.map(|(start, end, _)| {
let leading = run_leading(&metrics[*start..*end], page_leading);
let run_left = metrics[*start..*end]
.iter()
.map(|m| m.indent_left)
.fold(f64::INFINITY, f64::min);
let run_right = metrics[*start..*end]
.iter()
.map(|m| m.right)
.fold(f64::NEG_INFINITY, f64::max);
let measure = metrics
.iter()
.filter(|m| m.indent_left < run_right && m.right > run_left)
.map(|m| m.right)
.fold(run_right, f64::max);
(leading, measure)
})
.collect();
let mut entries: std::collections::HashSet<usize> = std::collections::HashSet::new();
for (index, (start, end, margin)) in runs.iter().enumerate() {
let (start, end, margin) = (*start, *end, *margin);
let (leading, measure) = run_shapes[index];
let column = Column {
margin,
right: measure,
};
let mut current = vec![start];
let mut run_groups: Vec<Vec<usize>> = Vec::new();
for i in start + 1..end {
if continues(&metrics, ¤t, i, style, column, rules, leading) {
current.push(i);
} else {
run_groups.push(std::mem::take(&mut current));
current = vec![i];
}
}
run_groups.push(current);
for (group, entry) in
run_groups
.iter()
.zip(entries_of_a_list(&metrics, &run_groups, margin))
{
if entry {
entries.insert(group[0]);
}
}
groups.extend(
run_groups
.into_iter()
.map(|group| (group[0], Group::Lines(group))),
);
}
groups.sort_by_key(|(first, _)| *first);
join_narrow_columns(
&mut groups,
&metrics,
&lines,
&runs,
&run_shapes,
rules,
&entries,
);
let mut blocks: Vec<Block> = Vec::new();
for (_, group) in groups {
match group {
Group::Lines(group) if !group.is_empty() => {
let block_lines: Vec<&TextBlock> = group.iter().map(|i| lines[*i]).collect();
let block_metrics: Vec<&LineMetrics> = group.iter().map(|i| &metrics[*i]).collect();
let item = block_metrics.first().and_then(|m| m.item);
let mut block = assemble(page, 0, &block_lines, &block_metrics, item);
if item.is_none() && entries.contains(&group[0]) {
block.kind = BlockKind::ListItem {
level: 0,
ordinal: None,
};
}
blocks.push(block);
}
Group::Lines(_) => {}
Group::Table(table) => {
for cell in &table.cells {
blocks.push(assemble_cell(
page,
&lines,
cell,
table.doubt,
table.origin,
cell_path_words,
));
}
}
}
}
blocks.retain(|block| !block.text.trim().is_empty());
for (n, block) in blocks.iter_mut().enumerate() {
block.index = first_index + n;
}
blocks
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn extract_options_defaults_pin_every_new_field() {
let options = ExtractOptions::default();
assert_eq!(options.ocr, OcrMode::Never);
assert_eq!(options.ocr_language, "eng");
assert_eq!(options.ocr_dpi, 150);
assert!(matches!(options.quality, Quality::Fast));
assert_eq!(options.model_dir, None);
assert!(!options.keep_furniture);
assert!(options.heading_overrides.is_empty());
assert!(!options.include_hidden);
assert!(!options.raw_order);
assert!(matches!(options.table_strategy, TableStrategy::Both));
assert!(matches!(options.table_render_mode, TableRenderMode::Auto));
}
#[test]
fn extract_options_still_implements_eq() {
fn assert_is_eq<T: Eq>() {}
assert_is_eq::<ExtractOptions>();
assert_is_eq::<HeadingOverride>();
}
#[test]
fn extract_options_stays_eq() {
fn assert_impl_eq<T: Eq>() {}
assert_impl_eq::<ExtractOptions>();
}
fn table_cell(row: u16, column: u16, text: &str) -> Block {
Block {
kind: BlockKind::TableCell {
row,
column,
row_span: 1,
column_span: if text.len() > 30 { 3 } else { 1 },
header: row == 0,
},
page: 0,
bbox: [
72.0 + 100.0 * f64::from(column),
700.0 - 12.0 * f64::from(row),
160.0,
709.0,
],
text: text.into(),
spans: Vec::new(),
index: 0,
continues_previous: false,
confidence: None,
grid: Some(GridDoubt::default()),
table_origin: TableOrigin::Other,
trace_learned: None,
}
}
fn table_with(over: Option<&str>, under: Option<&str>) -> Vec<Block> {
let mut blocks = Vec::new();
let mut row = 0;
if let Some(text) = over {
blocks.push(table_cell(row, 0, text));
row += 1;
}
for (label, a, b) in [
("Macrophages", "49.5", "50.5"),
("Granulocytes", "17.7", "15.5"),
("T lymphocytes", "5.0", "6.7"),
] {
blocks.push(table_cell(row, 0, label));
blocks.push(table_cell(row, 1, a));
blocks.push(table_cell(row, 2, b));
row += 1;
}
if let Some(text) = under {
blocks.push(table_cell(row, 0, text));
}
blocks
}
fn cells(blocks: &[Block]) -> usize {
blocks
.iter()
.filter(|b| matches!(b.kind, BlockKind::TableCell { .. }))
.count()
}
#[test]
fn extract_options_keeps_its_eq() {
fn assert_eq<T: Eq>() {}
assert_eq::<ExtractOptions>();
}
#[test]
fn tatr_options_default_to_four_threads() {
assert_eq!(TatrOptions::default().intra_threads, 4);
}
#[test]
fn clip_margins_rejects_a_negative_side() {
assert!(ClipMargins::new(0.0, 0.0, 0.0, 0.0).is_ok());
assert!(ClipMargins::new(10.0, 20.0, 30.0, 40.0).is_ok());
for (side, margins) in [
("left", (-1.0, 0.0, 0.0, 0.0)),
("top", (0.0, -1.0, 0.0, 0.0)),
("right", (0.0, 0.0, -1.0, 0.0)),
("bottom", (0.0, 0.0, 0.0, -0.5)),
] {
let (left, top, right, bottom) = margins;
let value = [left, top, right, bottom]
.into_iter()
.find(|v| *v < 0.0)
.expect("one negative side");
assert_eq!(
ClipMargins::new(left, top, right, bottom),
Err(OptionsError::InvalidClipMargins { side, value }),
"{side} rejects its negative side",
);
}
}
#[test]
fn clip_margins_rejects_what_is_not_finite() {
for (side, index) in [("left", 0), ("top", 1), ("right", 2), ("bottom", 3)] {
for value in [f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
let mut margins = [0.0; 4];
margins[index] = value;
let [left, top, right, bottom] = margins;
assert_eq!(
ClipMargins::new(left, top, right, bottom),
Err(OptionsError::InvalidClipMargins { side, value }),
"{side} rejects {value:?}",
);
}
}
}
#[test]
fn clip_margins_round_trips_through_its_accessor() {
let margins = ClipMargins::new(10.0, 20.0, 30.0, 40.0).expect("valid");
assert_eq!(margins.as_array(), [10.0, 20.0, 30.0, 40.0]);
}
#[test]
fn clip_margins_compares_float_equal_margins_equal() {
let one = ClipMargins::new(1.0, 2.0, 3.0, 4.0).expect("valid");
let same = ClipMargins::new(1.0, 2.0, 3.0, 4.0).expect("valid");
assert_eq!(one, same);
let neg_zero = ClipMargins::new(-0.0, 0.0, 0.0, 0.0).expect("valid");
let pos_zero = ClipMargins::new(0.0, 0.0, 0.0, 0.0).expect("valid");
assert_eq!(neg_zero, pos_zero);
assert_eq!(neg_zero.as_array().map(f64::to_bits), [0.0f64.to_bits(); 4]);
let mut seen = std::collections::HashSet::new();
seen.insert(one);
assert!(seen.contains(&same));
seen.insert(neg_zero);
assert!(seen.contains(&pos_zero));
}
#[test]
fn clip_margins_error_names_the_side() {
let err = ClipMargins::new(-1.0, 0.0, 0.0, 0.0).expect_err("negative");
assert_eq!(
err.to_string(),
"invalid clip margins: left must be finite and at least 0, got -1"
);
let _: &dyn std::error::Error = &err;
}
fn hidden_span(text: &str) -> TextSpan {
TextSpan {
text: text.to_string(),
render_mode: Some(3),
..Default::default()
}
}
fn visible_span(text: &str) -> TextSpan {
TextSpan {
text: text.to_string(),
..Default::default()
}
}
#[test]
fn a_spanless_figure_does_not_mark_its_page_visible() {
let figure = Block::new(
BlockKind::Figure,
0,
[0.0, 0.0, 10.0, 10.0],
String::new(),
0,
);
let mut words = Block::new(
BlockKind::Paragraph,
0,
[0.0, 0.0, 10.0, 10.0],
"words".to_string(),
1,
);
words.spans = vec![hidden_span("words")];
let mut blocks = vec![figure, words];
drop_hidden_text(&mut blocks);
assert_eq!(blocks.len(), 2, "the hidden words went with the figure");
assert_eq!(blocks[1].text, "words");
}
#[test]
fn visible_text_still_drops_hidden_spans() {
let mut block = Block::new(
BlockKind::Paragraph,
0,
[0.0, 0.0, 10.0, 10.0],
"seen gone".to_string(),
0,
);
block.spans = vec![visible_span("seen"), hidden_span("gone")];
let mut blocks = vec![block];
drop_hidden_text(&mut blocks);
assert_eq!(blocks.len(), 1);
assert_eq!(blocks[0].spans.len(), 1);
assert_eq!(blocks[0].text, "seen");
}
#[test]
fn a_caption_and_a_note_are_taken_out_of_the_table() {
let mut blocks = table_with(
Some("Table 1 Cellular composition of cells infiltrating synovial tissue"),
Some("Values are percentages (mean \u{b1} standard deviation) of positive cells."),
);
peel_table_edges(&mut blocks, false);
assert_eq!(
blocks[0].kind,
BlockKind::Paragraph,
"the caption stayed a cell"
);
assert!(
blocks[0].grid.is_none(),
"a peeled caption kept its table's evidence"
);
assert_eq!(
blocks.last().map(|b| b.kind),
Some(BlockKind::Paragraph),
"the note stayed a cell"
);
assert_eq!(cells(&blocks), 9);
assert!(
matches!(
blocks[1].kind,
BlockKind::TableCell {
row: 0,
column: 0,
..
}
),
"the table's rows were not counted from its new first row: {:?}",
blocks[1].kind
);
}
#[test]
fn a_spanning_head_and_a_crystal_head_stay_in_the_table() {
for head in [
"Male Female",
"x y z U iso*/ U eq",
"Diplotype No. rs12979860 rs738409",
"Stable isotope composition",
] {
let mut blocks = table_with(Some(head), None);
peel_table_edges(&mut blocks, false);
assert_eq!(cells(&blocks), 10, "`{head}` was taken out of the table");
let mut blocks = table_with(None, Some(head));
peel_table_edges(&mut blocks, false);
assert!(
blocks
.iter()
.all(|b| { matches!(b.kind, BlockKind::TableCell { .. }) })
&& blocks.iter().any(|b| b.text.contains(head)),
"`{head}` under the table was taken out"
);
}
}
#[test]
fn a_sentence_over_the_table_stays_in_it() {
let mut blocks = table_with(
Some("suitable for clinical trials for regulatory purposes and for the review."),
None,
);
peel_table_edges(&mut blocks, false);
assert_eq!(cells(&blocks), 10);
}
fn table_beside_prose(prose: &[&str]) -> Vec<Block> {
let mut blocks = Vec::new();
for (row, line) in prose.iter().enumerate() {
let row = row as u16;
let mut label = table_cell(row, 0, "Campbelltown");
label.bbox = [
72.0,
700.0 - 12.0 * f64::from(row),
150.0,
709.0 - 12.0 * f64::from(row),
];
let mut figure = table_cell(row, 1, "1,000");
figure.bbox = [
200.0,
700.0 - 12.0 * f64::from(row),
230.0,
709.0 - 12.0 * f64::from(row),
];
let mut text = table_cell(row, 2, line);
text.kind = BlockKind::TableCell {
row,
column: 2,
row_span: 1,
column_span: 1,
header: row == 0,
};
let drop = if row >= 3 { 12.0 } else { 0.0 };
text.bbox = [
320.0,
700.0 - 12.0 * f64::from(row) - drop,
460.0,
709.0 - 12.0 * f64::from(row) - drop,
];
blocks.extend([label, figure, text]);
}
blocks
}
#[test]
fn a_column_of_running_text_leaves_the_table() {
let mut blocks = table_beside_prose(&[
"During the year considerable effort was given to restocking",
"our Residential Estates land portfolio across the country to",
"meet our future growth requirements and our objectives.",
"We successfully acquired future lots and we now control more",
"residential allotments for development in the coming years,",
"most of them in strategic growth areas within the states that",
"are expected to lead demand for housing over the next decade.",
]);
peel_table_edges(&mut blocks, false);
let paragraphs: Vec<&str> = blocks
.iter()
.filter(|b| b.kind == BlockKind::Paragraph)
.map(|b| b.text.as_str())
.collect();
assert_eq!(cells(&blocks), 14, "the running text stayed in the table");
assert_eq!(paragraphs.len(), 2, "not two paragraphs: {paragraphs:?}");
assert!(
paragraphs[0].starts_with("During the year") && paragraphs[0].ends_with("objectives.")
);
assert!(
blocks.iter().position(|b| b.kind == BlockKind::Paragraph)
> blocks
.iter()
.rposition(|b| matches!(b.kind, BlockKind::TableCell { .. })),
"the text was not set after the table"
);
}
#[test]
fn a_wrapping_description_column_stays_in_the_table() {
let mut blocks = Vec::new();
for (row, (date, text)) in [
(
"18 December 2002",
"Authorised the directors to approve the purchase of shares",
),
(
"",
"in issue on that date by the company or any of its subsidiaries",
),
(
"18 December 2002",
"Amended the articles of association in terms of which the maximum",
),
(
"",
"number of directors allowed was increased from thirteen to fifteen.",
),
(
"18 December 2002",
"Amended the articles of association to ensure that one-third",
),
(
"",
"of the directors retire from office at every annual general meeting.",
),
("20 March 2003", "Approved the annual financial statements"),
]
.iter()
.enumerate()
{
if !date.is_empty() {
blocks.push(table_cell(row as u16, 0, date));
}
let mut cell = table_cell(row as u16, 1, text);
cell.kind = BlockKind::TableCell {
row: row as u16,
column: 1,
row_span: 1,
column_span: 1,
header: row == 0,
};
blocks.push(cell);
}
peel_table_edges(&mut blocks, false);
assert!(
blocks
.iter()
.all(|b| matches!(b.kind, BlockKind::TableCell { .. })),
"a wrapping description column left the table"
);
assert!(
blocks.iter().any(|b| b.text
== "Amended the articles of association in terms of which the maximum \
number of directors allowed was increased from thirteen to fifteen."),
"{:?}",
blocks.iter().map(|b| &b.text).collect::<Vec<_>>()
);
}
fn span_at(text: &str, x: f64, width: f64) -> TextSpan {
TextSpan {
text: text.into(),
x,
width,
font_size: 9.0,
height: 9.0,
..TextSpan::default()
}
}
fn one_column(rows: &[&[(&str, f64, f64)]]) -> Vec<Block> {
rows.iter()
.enumerate()
.map(|(row, runs)| {
let mut cell = table_cell(row as u16, 0, "");
cell.text = runs.iter().map(|r| r.0).collect::<Vec<_>>().join(" ");
cell.spans = runs.iter().map(|&(t, x, w)| span_at(t, x, w)).collect();
cell
})
.collect()
}
#[test]
fn a_table_read_as_one_column_gets_its_columns_back() {
let mut blocks = one_column(&[
&[("AUC score", 57.0, 40.0)],
&[("CSF t-tau", 57.0, 29.0), ("0.616", 264.0, 17.0)],
&[("CSF A\u{3b2}42", 57.0, 29.0), ("0.612", 264.0, 17.0)],
&[("CSF p-tau", 57.0, 31.0), ("0.628", 264.0, 17.0)],
&[("Biomarkers-15", 57.0, 45.0), ("0.830", 264.0, 17.0)],
&[(
"Note that the AUC score for Biosignature-15 reported here",
57.0,
260.0,
)],
]);
peel_table_edges(&mut blocks, false);
let at = |text: &str| {
blocks
.iter()
.find(|b| b.text == text)
.map(|b| b.kind)
.unwrap_or(BlockKind::Paragraph)
};
assert!(
matches!(at("0.616"), BlockKind::TableCell { column: 1, .. }),
"the figures did not get a column of their own: {:?}",
blocks.iter().map(|b| (&b.text, b.kind)).collect::<Vec<_>>()
);
assert_eq!(
blocks.last().map(|b| b.kind),
Some(BlockKind::Paragraph),
"the note that closed the white stayed in the table"
);
}
#[test]
fn a_regridded_table_keeps_the_indices_in_reading_order() {
let mut blocks = one_column(&[
&[("CSF t-tau", 57.0, 29.0), ("0.616", 264.0, 17.0)],
&[("CSF A\u{3b2}42", 57.0, 29.0), ("0.612", 264.0, 17.0)],
&[("CSF p-tau", 57.0, 31.0), ("0.628", 264.0, 17.0)],
&[("Biomarkers-15", 57.0, 45.0), ("0.830", 264.0, 17.0)],
]);
let mut after = table_cell(0, 0, "The paragraph after the table.");
after.kind = BlockKind::Paragraph;
blocks.push(after);
for (n, b) in blocks.iter_mut().enumerate() {
b.index = n;
}
peel_table_edges(&mut blocks, false);
let indices: Vec<usize> = blocks.iter().map(|b| b.index).collect();
assert_eq!(indices, (0..blocks.len()).collect::<Vec<_>>());
}
#[test]
fn a_regridded_cell_keeps_a_word_drawn_in_two_spans() {
let mut blocks = one_column(&[
&[("CSF t-tau", 57.0, 29.0), ("0.616", 264.0, 17.0)],
&[
("CSF p-", 57.0, 24.0),
("tau", 81.0, 10.0),
("0.628", 264.0, 17.0),
],
&[("CSF A\u{3b2}42", 57.0, 29.0), ("0.612", 264.0, 17.0)],
&[("Biomarkers-15", 57.0, 45.0), ("0.830", 264.0, 17.0)],
]);
peel_table_edges(&mut blocks, false);
assert!(
blocks.iter().any(|b| b.text == "CSF p-tau"),
"{:?}",
blocks.iter().map(|b| &b.text).collect::<Vec<_>>()
);
}
#[test]
fn two_runs_in_one_column_are_one_cell() {
let mut blocks = one_column(&[
&[("Label one", 57.0, 30.0), ("1.0", 200.0, 12.0)],
&[("Label two", 57.0, 30.0), ("2.0", 200.0, 12.0)],
&[("Label three", 57.0, 34.0), ("3.0", 200.0, 12.0)],
&[
("Label", 57.0, 20.0),
("four", 110.0, 16.0),
("4.0", 200.0, 12.0),
],
]);
peel_table_edges(&mut blocks, false);
let end = crate::markdown::table_run(&blocks, 0);
assert_eq!(end, Some(blocks.len()), "the table came apart into two");
}
#[test]
fn one_column_of_ragged_runs_is_left_alone() {
let mut blocks = one_column(&[
&[
("The committee met", 57.0, 70.0),
("on Monday", 180.0, 40.0),
],
&[("and resolved", 57.0, 50.0), ("that the", 240.0, 30.0)],
&[("officers report", 57.0, 60.0), ("before the", 300.0, 40.0)],
&[("next meeting", 57.0, 50.0), ("of the board", 150.0, 40.0)],
]);
peel_table_edges(&mut blocks, false);
assert!(blocks
.iter()
.all(|b| matches!(b.kind, BlockKind::TableCell { column: 0, .. })));
}
fn grid(cells: &[(u16, u16, &str)]) -> Vec<Block> {
cells
.iter()
.map(|&(row, column, text)| {
let mut cell = table_cell(row, column, text);
cell.kind = BlockKind::TableCell {
row,
column,
row_span: 1,
column_span: 1,
header: row == 0,
};
cell
})
.collect()
}
#[test]
fn a_caption_across_the_head_row_comes_out_whole() {
let mut blocks = grid(&[
(0, 0, "Table 1: Comparison methods"),
(0, 1, "of the"),
(0, 2, "logP values calculated"),
(0, 3, "by several"),
(1, 0, "Program"),
(1, 1, "colchicine"),
(1, 2, "paclitaxel"),
(1, 3, "colchitaxel"),
(2, 0, "ALOGP"),
(2, 1, "1.59"),
(2, 2, "3.20"),
(2, 3, "4.64"),
(3, 0, "CLOGP"),
(3, 1, "1.20"),
(3, 2, "4.95"),
(3, 3, "6.50"),
]);
peel_table_edges(&mut blocks, false);
assert_eq!(blocks[0].kind, BlockKind::Paragraph);
assert_eq!(
blocks[0].text,
"Table 1: Comparison methods of the logP values calculated by several"
);
assert!(
matches!(
blocks[1].kind,
BlockKind::TableCell {
row: 0,
column: 0,
..
}
),
"the table does not start at its own head: {:?}",
blocks[1].kind
);
assert_eq!(cells(&blocks), 12);
}
#[test]
fn a_caption_beside_column_heads_leaves_the_heads() {
let mut blocks = grid(&[
(0, 0, "Table 1 Descriptive statistics for publication rate"),
(0, 1, "Statistics"),
(0, 2, "PR P1"),
(0, 3, "PR P2"),
(1, 1, "Mean"),
(1, 2, "0.41"),
(1, 3, "0.52"),
(2, 1, "SD"),
(2, 2, "0.12"),
(2, 3, "0.18"),
]);
peel_table_edges(&mut blocks, false);
assert_eq!(blocks[0].kind, BlockKind::Paragraph);
assert!(blocks.iter().any(
|b| b.text == "Statistics" && matches!(b.kind, BlockKind::TableCell { row: 0, .. })
));
}
#[test]
fn a_table_of_one_row_is_a_line_unless_it_runs_on_leaders() {
let mut blocks = grid(&[
(
0,
0,
"New records of the endemic Sicilian land snail species",
),
(0, 1, "137"),
]);
peel_table_edges(&mut blocks, false);
assert_eq!(blocks.len(), 1);
assert_eq!(blocks[0].kind, BlockKind::Paragraph);
let mut blocks = grid(&[
(0, 0, "Letter from the Chairman . . . . . . . . 2"),
(0, 1, "Feature Client Stories . . . . . . . . 6"),
(0, 2, "Client Innovation Highlights . . . . 14"),
]);
peel_table_edges(&mut blocks, false);
assert_eq!(cells(&blocks), 3, "a contents line lost its table");
}
#[test]
fn a_head_that_opens_with_the_word_table_is_no_caption() {
let mut blocks = grid(&[
(0, 0, "Table size"),
(0, 1, "rows"),
(0, 2, "columns"),
(1, 0, "Small"),
(1, 1, "12"),
(1, 2, "4"),
(2, 0, "Large"),
(2, 1, "480"),
(2, 2, "16"),
]);
peel_table_edges(&mut blocks, false);
assert_eq!(cells(&blocks), 9, "the head row was taken for a caption");
assert!(is_numbered_caption("Table IV. Results"));
assert!(is_numbered_caption("Table S2 Primers"));
assert!(!is_numbered_caption("Table value"));
}
#[test]
fn one_row_left_by_a_page_break_stays_a_table() {
let mut blocks = grid(&[
(0, 0, "Revenue"),
(0, 1, "13,110"),
(1, 0, "Cost of sales"),
(1, 1, "(8,406)"),
(2, 0, "Gross profit"),
(2, 1, "4,704"),
]);
let mut rest = grid(&[(0, 0, "Operating profit"), (0, 1, "1,559")]);
for b in rest.iter_mut() {
b.page = 1;
}
blocks.extend(rest);
peel_table_edges(&mut blocks, false);
assert_eq!(cells(&blocks), 8, "the page's one row became a line");
}
#[test]
fn one_row_with_columns_of_its_own_after_a_break_is_a_line() {
let mut blocks = grid(&[
(0, 0, "Revenue"),
(0, 1, "13,110"),
(1, 0, "Cost of sales"),
(1, 1, "(8,406)"),
(2, 0, "Gross profit"),
(2, 1, "4,704"),
]);
let mut head = grid(&[
(0, 0, "New records of the endemic snail species"),
(0, 1, "137"),
]);
for (k, b) in head.iter_mut().enumerate() {
b.page = 1;
b.bbox[0] = [300.0, 540.0][k];
}
blocks.extend(head);
peel_table_edges(&mut blocks, false);
assert_eq!(
cells(&blocks),
6,
"an unrelated one-row grid stayed a table"
);
}
#[test]
fn one_row_before_a_table_read_as_one_column_stays_a_table() {
let mut lead = table_cell(0, 0, "Notes to the statements.");
lead.kind = BlockKind::Paragraph;
let mut blocks = vec![lead];
let mut row = grid(&[(0, 0, "Revenue"), (0, 1, "13,110")]);
row[0].bbox[0] = 57.0;
row[1].bbox[0] = 264.0;
blocks.extend(row);
let mut rest = one_column(&[
&[("Cost of sales", 57.0, 50.0), ("(8,406)", 264.0, 30.0)],
&[("Gross profit", 57.0, 45.0), ("4,704", 264.0, 20.0)],
&[("Selling expenses", 57.0, 60.0), ("(3,145)", 264.0, 30.0)],
&[("Operating profit", 57.0, 60.0), ("1,559", 264.0, 20.0)],
]);
for b in rest.iter_mut() {
b.page = 1;
}
blocks.extend(rest);
peel_table_edges(&mut blocks, false);
assert!(
blocks
.iter()
.any(|b| b.text == "Revenue" && matches!(b.kind, BlockKind::TableCell { .. })),
"the page's last row became a line: {:?}",
blocks.iter().map(|b| (&b.text, b.kind)).collect::<Vec<_>>()
);
}
#[test]
fn a_financial_row_label_under_the_table_stays_in_it() {
let mut blocks = table_with(
None,
Some("Prima facie income tax (benefit)/expense calculated at 30%"),
);
peel_table_edges(&mut blocks, false);
assert_eq!(cells(&blocks), 10);
}
fn line(text: &str, x: f64, y: f64, size: f64) -> TextBlock {
TextBlock {
spans: vec![span(text, x, y, size)],
}
}
fn span(text: &str, x: f64, y: f64, size: f64) -> TextSpan {
TextSpan {
text: text.to_string(),
x,
y,
width: size * 0.5 * text.chars().count() as f64,
height: size,
font_size: size,
..Default::default()
}
}
fn texts(blocks: &[Block]) -> Vec<String> {
blocks.iter().map(|b| b.text.clone()).collect()
}
fn para_block(lines: &[(&str, f64, f64)], size: f64) -> Block {
let spans: Vec<TextSpan> = lines
.iter()
.map(|(text, x, y)| span(text, *x, *y, size))
.collect();
let mut block = Block {
kind: BlockKind::Paragraph,
page: 0,
bbox: [0.0; 4],
text: join_lines(
&lines
.iter()
.map(|(text, _, _)| text.to_string())
.collect::<Vec<_>>(),
),
spans,
index: 0,
continues_previous: false,
confidence: None,
grid: None,
table_origin: TableOrigin::Other,
trace_learned: None,
};
recompute_bbox(&mut block);
block
}
fn merged_pair() -> Block {
para_block(
&[
("the first paragraph opens here and runs", 72.0, 700.0),
("the whole measure to its second line,", 72.0, 688.0),
("and closes on its third.", 72.0, 676.0),
("the second paragraph opens lower down", 72.0, 652.0),
("and runs the measure to its own end,", 72.0, 640.0),
("closing here.", 72.0, 628.0),
],
10.0,
)
}
#[test]
fn a_paragraph_sized_gap_inside_a_block_cuts_it() {
let mut blocks = vec![merged_pair()];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(
texts(&blocks),
vec![
"the first paragraph opens here and runs the whole measure to its second line, and closes on its third.",
"the second paragraph opens lower down and runs the measure to its own end, closing here.",
]
);
assert!(blocks
.iter()
.all(|b| matches!(b.kind, BlockKind::Paragraph)));
assert_eq!(blocks[0].spans.len(), 3);
assert_eq!(blocks[1].spans.len(), 3);
assert!(blocks[0].bbox[1] > blocks[1].bbox[3]);
}
#[test]
fn an_evenly_double_spaced_paragraph_is_not_cut() {
let even = para_block(
&[
("a double-spaced line one", 72.0, 700.0),
("a double-spaced line two", 72.0, 676.0),
("a double-spaced line three", 72.0, 652.0),
("a double-spaced line four", 72.0, 628.0),
("a double-spaced line five", 72.0, 604.0),
("a double-spaced line six", 72.0, 580.0),
],
10.0,
);
let mut blocks = vec![merged_pair(), even];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(blocks.len(), 3, "{:?}", texts(&blocks));
assert!(blocks[2].text.starts_with("a double-spaced line one"));
assert!(blocks[2].text.ends_with("line six"));
assert_eq!(blocks[2].spans.len(), 6);
}
#[test]
fn a_column_change_is_not_this_rules_business() {
let shifted = para_block(
&[
("the left column ends here and runs", 72.0, 700.0),
("the whole measure to its own end.", 72.0, 688.0),
("it closes on this third line.", 72.0, 676.0),
("the right column opens lower down", 300.0, 652.0),
("and runs to its own second line.", 300.0, 640.0),
("closing here at last.", 300.0, 628.0),
],
10.0,
);
let mut blocks = vec![merged_pair(), shifted];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(blocks.len(), 3, "{:?}", texts(&blocks));
assert_eq!(blocks[2].spans.len(), 6);
}
#[test]
fn headings_and_list_items_are_untouched() {
let mut heading = merged_pair();
heading.kind = BlockKind::Heading { level: 1 };
let mut item = merged_pair();
item.kind = BlockKind::ListItem {
level: 0,
ordinal: None,
};
let heading_text = heading.text.clone();
let mut blocks = vec![merged_pair(), heading, item];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(blocks.len(), 4, "{:?}", texts(&blocks));
assert_eq!(blocks[2].text, heading_text);
assert!(matches!(blocks[2].kind, BlockKind::Heading { level: 1 }));
assert!(matches!(
blocks[3].kind,
BlockKind::ListItem { level: 0, .. }
));
assert_eq!(blocks[3].spans.len(), 6);
}
#[test]
fn a_vertical_word_is_not_cut_into_salad() {
let word = para_block(
&[
("T", 72.0, 700.0),
("h", 72.0, 688.0),
("i", 72.0, 676.0),
("c", 72.0, 664.0),
("k", 72.0, 652.0),
("n", 72.0, 628.0),
("e", 72.0, 616.0),
("s", 72.0, 604.0),
("s", 72.0, 592.0),
],
10.0,
);
let text = word.text.clone();
let mut blocks = vec![merged_pair(), word];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(blocks.len(), 3, "{:?}", texts(&blocks));
assert_eq!(blocks[2].text, text);
assert_eq!(blocks[2].spans.len(), 9);
}
#[test]
fn a_rotated_stamp_is_not_cut() {
let mut stamp = merged_pair();
for span in &mut stamp.spans {
let size = span.font_size;
span.transform = Some([0.0, size, -size, 0.0, span.x, span.y]);
}
let text = stamp.text.clone();
let mut blocks = vec![merged_pair(), stamp];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(blocks.len(), 3, "{:?}", texts(&blocks));
assert_eq!(blocks[2].text, text);
assert_eq!(blocks[2].spans.len(), 6);
}
#[test]
fn a_number_block_is_not_split() {
let figure = "1,234.5 (678) 12.3%";
let mut rows: Vec<(&str, f64, f64)> = Vec::new();
let mut y = 700.0;
for row in 0..20 {
rows.push((figure, 72.0, y));
y -= if row % 5 == 4 { 24.0 } else { 12.0 };
}
let figures = para_block(&rows, 10.0);
let text = figures.text.clone();
let mut blocks = vec![merged_pair(), figures];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(blocks.len(), 3, "{:?}", texts(&blocks));
assert_eq!(blocks[2].text, text);
assert_eq!(blocks[2].spans.len(), 20);
}
#[test]
fn prose_cuts_still_happen() {
let parent = merged_pair();
let mut blocks = vec![parent.clone()];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(blocks.len(), 2, "{:?}", texts(&blocks));
let plain = |text: &str| {
text.replace("- ", "")
.chars()
.filter(|c| !c.is_whitespace())
.collect::<Vec<_>>()
};
let mut got: Vec<char> = Vec::new();
for piece in &blocks {
got.extend(plain(&piece.text));
}
assert_eq!(got, plain(&parent.text));
}
#[test]
fn a_reversed_reassembly_refuses_the_whole_split() {
let label = para_block(
&[
("aaa", 72.0, 100.0),
("bbb", 72.0, 112.0),
("ccc", 72.0, 124.0),
("ddd", 72.0, 148.0),
],
10.0,
);
let text = label.text.clone();
let mut blocks = vec![merged_pair(), label];
split_paragraphs_on_steps(&mut blocks);
assert_eq!(blocks.len(), 3, "{:?}", texts(&blocks));
assert_eq!(blocks[2].text, text);
assert_eq!(blocks[2].spans.len(), 4);
}
#[test]
fn consecutive_lines_of_one_measure_become_one_paragraph() {
let lines = vec![
line("the first line of the paragraph runs", 72.0, 700.0, 10.0),
line("the whole measure and the second one", 72.0, 688.0, 10.0),
line("stops short of it.", 72.0, 676.0, 10.0),
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(
texts(&blocks),
vec![
"the first line of the paragraph runs the whole measure and the second one stops short of it."
]
);
}
#[test]
fn extra_leading_starts_a_new_paragraph() {
let lines = vec![
line("the first paragraph ends here and", 72.0, 700.0, 10.0),
line("carries on to a second line.", 72.0, 688.0, 10.0),
line("the second paragraph begins after a", 72.0, 664.0, 10.0),
line("line of extra space.", 72.0, 652.0, 10.0),
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 2, "{:?}", texts(&blocks));
assert!(blocks[0].text.ends_with("second line."));
assert!(blocks[1].text.starts_with("the second paragraph"));
}
#[test]
fn a_word_broken_across_a_line_is_put_back_together() {
let lines = vec![
line("the typesetter broke this para-", 72.0, 700.0, 10.0),
line("graph across two lines.", 72.0, 688.0, 10.0),
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(
texts(&blocks),
vec!["the typesetter broke this paragraph across two lines."]
);
}
fn references(entries: usize) -> Vec<TextBlock> {
let mut lines = vec![line("References", 72.0, 716.0, 12.0)];
let mut y = 700.0;
for n in 0..entries {
lines.push(line(
&format!("Author{n}, A. B., and C. D. Author, 2003, Phys. Rev. Lett. 88,"),
72.0,
y,
10.0,
));
lines.push(line(
"014517, and the pages after it.",
84.0,
y - 12.0,
10.0,
));
y -= 24.0;
}
lines
}
#[test]
fn a_run_of_hung_entries_is_a_list_of_items() {
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&references(4)),
&[],
&[],
12.0,
TableStrategy::Both,
);
let kinds: Vec<bool> = blocks
.iter()
.map(|b| {
matches!(
b.kind,
BlockKind::ListItem {
level: 0,
ordinal: None
}
)
})
.collect();
assert_eq!(
kinds,
vec![false, true, true, true, true],
"{:?}",
texts(&blocks)
);
assert!(
blocks[1].text.starts_with("Author0, A. B."),
"{:?}",
texts(&blocks)
);
assert!(
blocks[1].text.ends_with("the pages after it."),
"{:?}",
texts(&blocks)
);
}
#[test]
fn two_hung_entries_are_not_yet_a_list() {
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&references(2)),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 3, "{:?}", texts(&blocks));
assert!(
blocks
.iter()
.all(|b| matches!(b.kind, BlockKind::Paragraph)),
"{:?}",
texts(&blocks)
);
}
#[test]
fn a_first_line_indent_starts_a_paragraph_and_a_hanging_indent_does_not() {
let indented = vec![
line(" the first paragraph opens with an", 90.0, 700.0, 10.0),
line("indent and runs the full measure of", 72.0, 688.0, 10.0),
line("the column.", 72.0, 676.0, 10.0),
line(" the second one opens the same way", 90.0, 664.0, 10.0),
line("and also runs the full measure here.", 72.0, 652.0, 10.0),
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&indented),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 2, "{:?}", texts(&blocks));
let hanging = vec![
line("Aho, A. and Ullman, J. Principles of", 72.0, 700.0, 10.0),
line(" compiler design. Addison-Wesley,", 90.0, 688.0, 10.0),
line(" Reading, 1977.", 90.0, 676.0, 10.0),
line("Knuth, D. The art of computer program", 72.0, 664.0, 10.0),
line(" ming. Addison-Wesley, Reading, 1968", 90.0, 652.0, 10.0),
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&hanging),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 2, "{:?}", texts(&blocks));
assert!(blocks[0].text.starts_with("Aho"));
assert!(blocks[1].text.starts_with("Knuth"));
}
#[test]
fn a_heading_is_not_swallowed_by_the_paragraph_under_it() {
let lines = vec![
line("2 Scope", 72.0, 700.0, 16.0),
line("the body of the section starts here", 72.0, 684.0, 10.0),
line("and runs on for a second line.", 72.0, 672.0, 10.0),
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 2, "{:?}", texts(&blocks));
assert_eq!(blocks[0].text, "2 Scope");
}
#[test]
fn a_ruled_row_never_joins_the_row_under_it() {
let lines = vec![
line("id-6-1-2-t01 the first message", 60.0, 700.0, 10.0),
line("id-6-1-3-t01 the second message", 60.0, 682.0, 10.0),
];
let rules = vec![HorizontalRule {
left: 55.0,
right: 540.0,
y: 693.0,
}];
assert_eq!(
paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
18.0,
TableStrategy::Both
)
.len(),
1,
"the unruled fixture no longer merges, so the pair below proves nothing"
);
assert_eq!(
paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&rules,
18.0,
TableStrategy::Both
)
.len(),
2,
"a rule between two rows did not keep them apart"
);
}
#[test]
fn a_wide_word_gap_on_one_line_is_not_a_table() {
let justified = vec![
TextBlock {
spans: vec![
span("the quick brown", 72.0, 700.0, 10.0),
span("fox jumps over it", 200.0, 700.0, 10.0),
],
},
line("and the second line is set solid.", 72.0, 688.0, 10.0),
];
assert_eq!(
paragraphs(
0,
0,
std::slice::from_ref(&justified),
&[],
&[],
12.0,
TableStrategy::Both
)
.len(),
1
);
let tabular = vec![
TextBlock {
spans: vec![
span("Widget", 72.0, 700.0, 10.0),
span("12.00", 260.0, 700.0, 10.0),
],
},
TextBlock {
spans: vec![
span("Gadget", 72.0, 688.0, 10.0),
span("8.50", 260.0, 688.0, 10.0),
],
},
];
let cells = paragraphs(
0,
0,
std::slice::from_ref(&tabular),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(texts(&cells), vec!["Widget", "12.00", "Gadget", "8.50"]);
assert!(
cells
.iter()
.all(|block| matches!(block.kind, BlockKind::TableCell { .. })),
"{:?}",
cells.iter().map(|b| b.kind).collect::<Vec<_>>()
);
}
#[test]
fn a_full_width_title_does_not_join_the_column_under_it() {
let title = vec![line(
"A title that runs the whole width of the page and then some more",
72.0,
720.0,
10.0,
)];
let left = vec![
line("the left column", 72.0, 708.0, 10.0),
line("starts here and", 72.0, 696.0, 10.0),
];
let right = vec![
line("the right column", 320.0, 708.0, 10.0),
line("starts up here", 320.0, 696.0, 10.0),
];
let blocks = paragraphs(
0,
0,
&[title, left, right],
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 3, "{:?}", texts(&blocks));
assert!(blocks[0].text.starts_with("A title"));
assert_eq!(blocks[1].text, "the left column starts here and");
assert_eq!(blocks[2].text, "the right column starts up here");
}
#[test]
fn a_drop_cap_is_read_at_the_front_of_its_paragraph() {
let lines = vec![
line("he first line clears the", 100.0, 700.0, 10.0),
line("initial, and so does the", 100.0, 688.0, 10.0),
TextBlock {
spans: vec![
span("T", 72.0, 676.0, 30.0),
span("second one; the third runs", 100.0, 676.0, 10.0),
],
},
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 1, "{:?}", texts(&blocks));
assert!(
blocks[0].text.starts_with("T he first line"),
"the initial is not at the front: {:?}",
blocks[0].text
);
}
#[test]
fn a_footnote_under_a_rule_stays_its_own_block() {
let lines = vec![
line("the last line of the body text sits", 72.0, 200.0, 10.0),
line("above the footnote rule.", 72.0, 188.0, 10.0),
line("1 The footnote itself is set smaller.", 72.0, 170.0, 8.0),
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 2, "{:?}", texts(&blocks));
assert!(blocks[1].text.starts_with("1 The footnote"));
}
#[test]
fn a_block_carries_its_page_bbox_and_reading_order() {
let lines = vec![
line("one", 72.0, 700.0, 10.0),
line("two", 72.0, 600.0, 10.0),
];
let blocks = paragraphs(
3,
17,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 2);
assert_eq!(blocks[0].page, 3);
assert_eq!(blocks[0].index, 17);
assert_eq!(blocks[1].index, 18);
assert_eq!(blocks[0].kind, BlockKind::Paragraph);
assert!(blocks[0].bbox[0] <= 72.0 && blocks[0].bbox[3] >= 700.0);
assert!(blocks[0].bbox[1] < blocks[0].bbox[3]);
assert_eq!(blocks[0].spans.len(), 1);
}
#[test]
fn an_oversized_marker_with_nothing_beside_it_is_not_a_drop_cap() {
let lines = vec![
line("the first line of the paragraph", 72.0, 700.0, 10.0),
TextBlock {
spans: vec![
span("\u{2022}", 72.0, 688.0, 20.0),
span("and the second one after a marker", 95.0, 688.0, 10.0),
],
},
];
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(blocks.len(), 1, "{:?}", texts(&blocks));
assert!(
blocks[0].text.starts_with("the first line"),
"the marker was hoisted to the front as if it were an initial: {:?}",
blocks[0].text
);
}
#[test]
fn the_reading_order_has_no_gap_where_a_block_held_only_space() {
let lines = vec![
line("the first paragraph", 72.0, 700.0, 10.0),
line(" ", 72.0, 600.0, 10.0),
line("the second paragraph", 72.0, 500.0, 10.0),
];
let blocks = paragraphs(
0,
7,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert_eq!(
texts(&blocks),
vec!["the first paragraph", "the second paragraph"]
);
assert_eq!(
blocks.iter().map(|b| b.index).collect::<Vec<_>>(),
vec![7, 8],
"a block that held only space left a hole in the reading order, and \
the next page starts at the count rather than at the last index"
);
}
fn heavy(text: &str, x: f64, y: f64, size: f64) -> TextBlock {
let mut span = span(text, x, y, size);
span.is_bold = true;
TextBlock { spans: vec![span] }
}
#[test]
fn a_numbered_heading_inside_a_column_is_not_a_list_item() {
let mut lines = vec![heavy("3. Method", 72.0, 700.0, 14.0)];
for (i, text) in [
"The committee considered the proposals put before it in",
"the order they had been received, and resolved that each",
]
.iter()
.enumerate()
{
lines.push(line(text, 72.0, 686.0 - i as f64 * 12.0, 10.0));
}
lines.push(heavy("4. Results", 72.0, 650.0, 14.0));
lines.push(line(
"of them be referred to the officers for a report.",
72.0,
636.0,
10.0,
));
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
assert!(
blocks
.iter()
.all(|block| !matches!(block.kind, BlockKind::ListItem { .. })),
"a numbered heading was read as a list item: {:?}",
blocks.iter().map(|b| (b.kind, &b.text)).collect::<Vec<_>>()
);
}
#[test]
fn a_numbered_list_inside_the_same_column_is_one() {
let mut lines = vec![line(
"The committee resolved that each of the proposals be referred",
72.0,
700.0,
10.0,
)];
for (i, text) in ["3. to the officers", "4. to the auditors"]
.iter()
.enumerate()
{
lines.push(line(text, 72.0, 686.0 - i as f64 * 12.0, 10.0));
}
let blocks = paragraphs(
0,
0,
std::slice::from_ref(&lines),
&[],
&[],
12.0,
TableStrategy::Both,
);
let kinds: Vec<BlockKind> = blocks.iter().map(|block| block.kind).collect();
assert_eq!(
kinds,
vec![
BlockKind::Paragraph,
BlockKind::ListItem {
level: 0,
ordinal: Some(3)
},
BlockKind::ListItem {
level: 0,
ordinal: Some(4)
},
],
"{:?}",
texts(&blocks)
);
assert_eq!(blocks[1].text, "to the officers");
}
#[test]
fn a_page_of_nothing_produces_no_blocks() {
assert!(paragraphs(0, 0, &[], &[], &[], 0.0, TableStrategy::Both).is_empty());
assert!(paragraphs(
0,
0,
&[vec![TextBlock { spans: Vec::new() }]],
&[],
&[],
0.0,
TableStrategy::Both
)
.is_empty());
}
fn subtitle_span(size: f64) -> TextSpan {
TextSpan {
font_size: size,
..Default::default()
}
}
fn subtitle_block(kind: BlockKind, text: &str, size: f64, bbox: [f64; 4]) -> Block {
Block {
kind,
page: 0,
bbox,
text: text.into(),
spans: vec![subtitle_span(size)],
trace_learned: None,
index: 0,
continues_previous: false,
confidence: None,
grid: None,
table_origin: TableOrigin::Other,
}
}
fn subtitle_heading(text: &str, size: f64, bbox: [f64; 4]) -> Block {
subtitle_block(BlockKind::Heading { level: 1 }, text, size, bbox)
}
#[test]
fn a_title_keeps_its_subtitle() {
let mut blocks = vec![
subtitle_heading(
"Statements of cash flows",
18.0,
[72.0, 700.0, 300.0, 718.0],
),
subtitle_block(
BlockKind::Paragraph,
"for the year ended 30 June 2003",
9.5,
[72.0, 680.0, 280.0, 698.5],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(blocks.len(), 1, "the subtitle stayed apart: {blocks:?}");
assert_eq!(blocks[0].kind, BlockKind::Heading { level: 1 });
assert_eq!(
blocks[0].text,
"Statements of cash flows for the year ended 30 June 2003"
);
assert_eq!(blocks[0].spans.len(), 2);
assert_eq!(blocks[0].bbox, [72.0, 680.0, 300.0, 718.0]);
assert_eq!(blocks[0].index, 0);
}
#[test]
fn a_two_line_title_is_one_heading() {
let mut blocks = vec![
subtitle_heading(
"WE DON'T PLAY GAMES WITH",
32.0,
[72.0, 700.0, 400.0, 732.0],
),
subtitle_heading(
"ELECTRICITY, OUR CUSTOMERS",
32.0,
[72.0, 660.0, 400.0, 693.6],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(blocks.len(), 1, "the title stayed in pieces: {blocks:?}");
assert_eq!(blocks[0].kind, BlockKind::Heading { level: 1 });
assert_eq!(
blocks[0].text,
"WE DON'T PLAY GAMES WITH ELECTRICITY, OUR CUSTOMERS"
);
}
#[test]
fn a_heading_collects_two_tight_lines() {
let mut blocks = vec![
subtitle_heading("Annual report", 18.0, [72.0, 700.0, 200.0, 718.0]),
subtitle_block(
BlockKind::Paragraph,
"for the year ended",
9.5,
[72.0, 690.0, 180.0, 698.5],
),
subtitle_block(
BlockKind::Paragraph,
"30 June 2003",
9.5,
[72.0, 680.0, 150.0, 688.5],
),
subtitle_block(
BlockKind::Paragraph,
"The year in review.",
10.0,
[72.0, 600.0, 300.0, 610.0],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(blocks.len(), 2, "the three lines did not join: {blocks:?}");
assert_eq!(
blocks[0].text,
"Annual report for the year ended 30 June 2003"
);
assert_eq!(blocks[0].spans.len(), 3);
assert_eq!((blocks[0].index, blocks[1].index), (0, 1));
}
#[test]
fn a_heading_over_a_sentence_stays_apart() {
let mut blocks = vec![
subtitle_heading("January 1989", 14.0, [72.0, 700.0, 200.0, 714.0]),
subtitle_block(
BlockKind::Paragraph,
"Emperor Hirohito of Japan dead at 87.",
10.0,
[72.0, 680.0, 300.0, 698.0],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading swallowed the sentence under it: {blocks:?}"
);
}
#[test]
fn a_larger_line_under_a_heading_stays_apart() {
let mut blocks = vec![
subtitle_heading("Notes", 10.0, [72.0, 700.0, 200.0, 710.0]),
subtitle_block(
BlockKind::Paragraph,
"A line set larger than the heading above it",
14.0,
[72.0, 680.0, 300.0, 698.5],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading swallowed a larger line: {blocks:?}"
);
}
#[test]
fn a_loose_line_under_a_heading_stays_apart() {
let mut blocks = vec![
subtitle_heading(
"Statements of cash flows",
18.0,
[72.0, 700.0, 300.0, 718.0],
),
subtitle_block(
BlockKind::Paragraph,
"for the year ended 30 June 2003",
9.5,
[72.0, 671.0, 280.0, 691.0],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading reached half an em down: {blocks:?}"
);
}
#[test]
fn an_indented_line_under_a_heading_stays_apart() {
let mut blocks = vec![
subtitle_heading(
"Statements of cash flows",
18.0,
[72.0, 700.0, 300.0, 718.0],
),
subtitle_block(
BlockKind::Paragraph,
"for the year ended 30 June 2003",
9.5,
[92.0, 680.0, 300.0, 698.5],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading swallowed an indented line: {blocks:?}"
);
}
#[test]
fn a_heading_over_a_list_like_line_stays_apart() {
let mut blocks = vec![
subtitle_heading("Contents", 14.0, [72.0, 700.0, 200.0, 714.0]),
subtitle_block(
BlockKind::Paragraph,
"1. The first item of a list",
10.0,
[72.0, 680.0, 300.0, 698.0],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading swallowed a list item: {blocks:?}"
);
}
#[test]
fn a_subtitle_two_points_under_a_nine_point_head_joins() {
let mut blocks = vec![
subtitle_heading(
"Directors and Their Interests",
9.0,
[72.0, 700.0, 250.0, 709.0],
),
subtitle_block(
BlockKind::Paragraph,
"Ordinary Shares and Options",
9.0,
[72.0, 689.0, 280.0, 698.0],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(blocks.len(), 1, "the subtitle stayed apart: {blocks:?}");
assert_eq!(
blocks[0].text,
"Directors and Their Interests Ordinary Shares and Options"
);
}
#[test]
fn a_line_three_points_under_a_nine_point_head_stays_apart() {
let mut blocks = vec![
subtitle_heading(
"Directors and Their Interests",
9.0,
[72.0, 700.0, 250.0, 709.0],
),
subtitle_block(
BlockKind::Paragraph,
"Ordinary Shares and Options",
9.0,
[72.0, 688.0, 280.0, 697.0],
),
];
join_heading_subtitles(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading reached a third of an em down: {blocks:?}"
);
}
fn heading_line_span(size: f64, bold: bool) -> TextSpan {
TextSpan {
font_size: size,
is_bold: bold,
..Default::default()
}
}
fn heading_line_block(
kind: BlockKind,
text: &str,
size: f64,
bold: bool,
bbox: [f64; 4],
) -> Block {
Block {
kind,
page: 0,
bbox,
text: text.into(),
spans: vec![heading_line_span(size, bold)],
trace_learned: None,
index: 0,
continues_previous: false,
confidence: None,
grid: None,
table_origin: TableOrigin::Other,
}
}
#[test]
fn two_heading_lines_in_one_style_become_one_heading() {
let mut blocks = vec![
heading_line_block(
BlockKind::Heading { level: 1 },
"ELECTRONIC DELIVERY OF",
8.0,
true,
[72.0, 700.0, 220.0, 708.0],
),
heading_line_block(
BlockKind::Heading { level: 2 },
"ANNUAL MEETING MATERIALS",
8.0,
true,
[72.0, 689.0, 230.0, 697.0],
),
];
join_heading_lines(&mut blocks);
assert_eq!(blocks.len(), 1, "the title stayed in pieces: {blocks:?}");
assert_eq!(blocks[0].kind, BlockKind::Heading { level: 1 });
assert_eq!(
blocks[0].text,
"ELECTRONIC DELIVERY OF ANNUAL MEETING MATERIALS"
);
assert_eq!(blocks[0].spans.len(), 2);
assert_eq!(blocks[0].bbox, [72.0, 689.0, 230.0, 708.0]);
assert_eq!(blocks[0].index, 0);
}
#[test]
fn a_heading_and_its_same_style_paragraph_line_join_when_short() {
let mut blocks = vec![
heading_line_block(
BlockKind::Paragraph,
"Powell Power Electronics",
10.0,
true,
[72.0, 700.0, 240.0, 710.0],
),
heading_line_block(
BlockKind::Heading { level: 2 },
"Company, Inc",
10.0,
true,
[72.0, 688.0, 180.0, 698.0],
),
];
join_heading_lines(&mut blocks);
assert_eq!(blocks.len(), 1, "the name stayed in pieces: {blocks:?}");
assert_eq!(blocks[0].kind, BlockKind::Heading { level: 2 });
assert_eq!(blocks[0].text, "Powell Power Electronics Company, Inc");
}
#[test]
fn a_heading_never_swallows_a_sentence() {
let mut blocks = vec![
heading_line_block(
BlockKind::Heading { level: 2 },
"Remuneration",
10.0,
true,
[72.0, 700.0, 180.0, 710.0],
),
heading_line_block(
BlockKind::Paragraph,
"The managing director's remuneration is made up of the following components.",
10.0,
true,
[72.0, 685.0, 420.0, 698.0],
),
];
join_heading_lines(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading swallowed the sentence under it: {blocks:?}"
);
}
#[test]
fn a_heading_piece_ending_in_a_colon_still_joins() {
let mut blocks = vec![
heading_line_block(
BlockKind::Paragraph,
"To the Board of Directors and Stockholders of",
9.0,
true,
[72.0, 700.0, 300.0, 709.0],
),
heading_line_block(
BlockKind::Heading { level: 2 },
"Powell Industries, Inc.:",
9.0,
true,
[72.0, 689.2, 250.0, 698.2],
),
];
join_heading_lines(&mut blocks);
assert_eq!(blocks.len(), 1, "the name stayed in pieces: {blocks:?}");
assert_eq!(blocks[0].kind, BlockKind::Heading { level: 2 });
assert_eq!(
blocks[0].text,
"To the Board of Directors and Stockholders of Powell Industries, Inc.:"
);
}
#[test]
fn different_sizes_do_not_join() {
let mut blocks = vec![
heading_line_block(
BlockKind::Heading { level: 1 },
"Notes",
11.0,
false,
[72.0, 700.0, 150.0, 711.0],
),
heading_line_block(
BlockKind::Paragraph,
"A line set smaller than the heading",
9.0,
false,
[72.0, 690.0, 300.0, 699.0],
),
];
join_heading_lines(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading swallowed a line set in another size: {blocks:?}"
);
}
#[test]
fn a_marker_line_is_not_joined() {
let mut blocks = vec![
heading_line_block(
BlockKind::Heading { level: 2 },
"Employee share plans",
10.0,
true,
[72.0, 700.0, 260.0, 710.0],
),
heading_line_block(
BlockKind::Paragraph,
"(a) The consolidated entity has implemented two plans",
10.0,
true,
[72.0, 688.0, 420.0, 698.0],
),
];
join_heading_lines(&mut blocks);
assert_eq!(
blocks.len(),
2,
"the heading swallowed a list item: {blocks:?}"
);
}
}