use crate::pdfium_backend::{Glyph, TextCell};
const MERGE: f64 = 1.0; const MERGE_WITH_SPACE: f64 = 0.33;
const WORD_MERGE: f64 = 0.33; const WORD_MERGE_WITH_SPACE: f64 = 2.0 * WORD_MERGE;
const H_TOL: f64 = 1.0;
#[derive(Clone)]
struct Cell {
text: String,
rx0: f64,
ry0: f64, rx1: f64,
ry1: f64, rx2: f64,
ry2: f64, rx3: f64,
ry3: f64, ltr: bool,
active: bool,
lig_carry: bool, font: u64, blank: bool, lig: bool, fb: bool, nchars: usize, b_l: f64, b_r: f64,
b_b: f64,
b_t: f64,
pen: Option<[f64; 3]>,
math_font: bool,
}
impl Cell {
fn length(&self) -> f64 {
((self.rx1 - self.rx0).powi(2) + (self.ry1 - self.ry0).powi(2)).sqrt()
}
fn avg_char_width(&self) -> f64 {
if self.nchars > 0 {
self.length() / self.nchars as f64
} else {
0.0
}
}
fn gap(&self, other: &Cell) -> f64 {
((self.rx1 - other.rx0).powi(2) + (self.ry1 - other.ry0).powi(2)).sqrt()
}
fn adjacent(&self, other: &Cell, eps0: f64, eps1: f64) -> bool {
let d0 = self.gap(other);
let d1 = ((self.rx2 - other.rx3).powi(2) + (self.ry2 - other.ry3).powi(2)).sqrt();
d0 < eps0 && d1 < eps1
}
fn same_orientation(&self, other: &Cell) -> bool {
self.ltr == other.ltr || is_punct_or_space(&self.text) || is_punct_or_space(&other.text)
}
fn merge_with(&mut self, other: &Cell, delta: f64, euclidean: bool) {
let gap = if euclidean {
self.gap(other)
} else {
other.rx0 - self.rx1
};
let space = delta < gap;
if !self.ltr || !other.ltr {
if space {
self.text.insert(0, ' ');
}
self.text = format!("{}{}", other.text, self.text);
self.ltr = false;
} else {
if space {
self.text.push(' ');
}
self.text.push_str(&other.text);
self.ltr = true;
}
self.rx1 = other.rx1;
self.ry1 = other.ry1;
self.rx2 = other.rx2;
self.ry2 = other.ry2;
self.blank = self.blank && other.blank;
self.nchars += other.nchars + usize::from(space);
self.fb = self.fb || other.fb;
self.lig = if self.text.len() <= 3 {
is_ligature(&self.text)
} else {
self.fb
};
let (l, r, b, t) = quad_bounds(self);
self.b_l = l;
self.b_r = r;
self.b_b = b;
self.b_t = t;
}
}
fn bounds(c: &Cell) -> (f64, f64, f64, f64) {
(c.b_l, c.b_r, c.b_b, c.b_t)
}
fn quad_bounds(c: &Cell) -> (f64, f64, f64, f64) {
let xs = [c.rx0, c.rx1, c.rx2, c.rx3];
let ys = [c.ry0, c.ry1, c.ry2, c.ry3];
let fold = |it: &[f64], f: fn(f64, f64) -> f64| it.iter().copied().reduce(f).unwrap();
(
fold(&xs, f64::min),
fold(&xs, f64::max),
fold(&ys, f64::min),
fold(&ys, f64::max),
)
}
fn gap_occupied(cells: &[Cell], i: usize, j: usize) -> bool {
let (al, ar, ab, at) = bounds(&cells[i]);
let (bl, br, bb, bt) = bounds(&cells[j]);
let (gl, gr) = if ar <= bl { (ar, bl) } else { (br, al) };
if gr - gl < 0.5 {
return false; }
let (band_b, band_t) = (ab.min(bb), at.max(bt));
cells.iter().enumerate().any(|(k, c)| {
if k == i || k == j || !c.active || c.blank {
return false;
}
let (cl, cr, cb, ct) = bounds(c);
let overlap = (ct.min(band_t) - cb.max(band_b)).max(0.0);
overlap > 0.5 * (ct - cb).max(f64::EPSILON)
&& cr.min(gr) - cl.max(gl) > 0.1
})
}
fn applicable(a: &Cell, b: &Cell, parser: bool, block_spaces: bool) -> bool {
if !a.active || !b.active {
return false;
}
if block_spaces && (is_all_space(&a.text) || is_all_space(&b.text)) {
return false;
}
let lone_punct = |s: &str| {
let mut ch = s.chars();
matches!(ch.next(), Some(c) if c != ' ' && is_punct_or_space(&c.to_string()))
&& ch.next().is_none()
};
let punct_bridge =
parser && ((lone_punct(&a.text) && !b.ltr) || (lone_punct(&b.text) && !a.ltr));
let font_neutral = a.lig || b.lig || punct_bridge;
if a.font != 0 && b.font != 0 && a.font != b.font && !font_neutral {
return false;
}
a.same_orientation(b)
}
fn pass_ltr(cells: &mut [Cell], allow_reverse: bool, euclidean: bool, p: Factors) {
for i in 0..cells.len() {
if !cells[i].active {
continue;
}
let mut j = i + 1;
while j < cells.len() {
if !applicable(&cells[i], &cells[j], euclidean, p.block_spaces) {
break;
}
let i_lig = cells[i].lig || cells[i].lig_carry;
let j_lig = cells[j].lig || cells[j].lig_carry;
let d0 = cells[i].avg_char_width() * p.merge;
let d1 = cells[i].avg_char_width() * p.merge_with_space;
let adj_d1 = d0 + if i_lig || j_lig { H_TOL } else { 0.0 };
if cells[i].adjacent(&cells[j], d0, adj_d1) && !gap_occupied(cells, i, j) {
let other = cells[j].clone();
cells[i].merge_with(&other, d1, euclidean);
cells[i].lig_carry = other.lig;
cells[j].active = false;
j += 1; } else if allow_reverse
&& cells[j].adjacent(&cells[i], d0, adj_d1)
&& !gap_occupied(cells, j, i)
{
let other = cells[i].clone();
cells[j].merge_with(&other, d1, euclidean);
cells[j].lig_carry = other.lig;
cells[i].active = false;
break; } else {
break;
}
}
}
}
fn pass_rtl(cells: &mut [Cell], euclidean: bool, p: Factors) {
let n = cells.len();
for k in 0..n {
let i = n - 1 - k;
if !cells[i].active || i == 0 {
continue;
}
let j = i - 1;
if !applicable(&cells[i], &cells[j], euclidean, p.block_spaces) {
continue;
}
let i_lig = cells[i].lig || cells[i].lig_carry;
let j_lig = cells[j].lig || cells[j].lig_carry;
let d0 = cells[i].avg_char_width() * p.merge;
let d1 = cells[i].avg_char_width() * p.merge_with_space;
let adj_d1 = d0 + if i_lig || j_lig { H_TOL } else { 0.0 };
if cells[j].adjacent(&cells[i], d0, adj_d1) && !gap_occupied(cells, j, i) {
let other = cells[i].clone();
cells[j].merge_with(&other, d1, euclidean);
cells[j].lig_carry = other.lig;
cells[i].active = false;
}
}
}
#[derive(Clone, Copy)]
struct Factors {
merge: f64,
merge_with_space: f64,
block_spaces: bool,
}
const LINE_FACTORS: Factors = Factors {
merge: MERGE,
merge_with_space: MERGE_WITH_SPACE,
block_spaces: false,
};
const WORD_FACTORS: Factors = Factors {
merge: WORD_MERGE,
merge_with_space: WORD_MERGE_WITH_SPACE,
block_spaces: true,
};
fn is_all_space(s: &str) -> bool {
!s.is_empty() && s.chars().all(char::is_whitespace)
}
fn contract(cells: &mut Vec<Cell>, euclidean: bool, p: Factors) {
pass_ltr(cells, false, euclidean, p);
cells.retain(|c| c.active);
pass_rtl(cells, euclidean, p);
cells.retain(|c| c.active);
pass_ltr(cells, true, euclidean, p);
cells.retain(|c| c.active);
}
fn build_cells(glyphs: &[Glyph], euclidean: bool) -> Vec<Cell> {
let mut cells: Vec<Cell> = Vec::new();
for g in glyphs {
if !g.ll.is_finite() {
continue;
}
let q = g.quad.map(|q| q.map(f64::from)).unwrap_or_else(|| {
let (l, b, r, t) = (g.ll as f64, g.lb as f64, g.lr as f64, g.lt as f64);
[l, b, r, b, r, t, l, t]
});
if g.ch == ' ' && (q[2] - q[0]).hypot(q[3] - q[1]) < 0.5 {
continue;
}
if let Some(last) = cells.last_mut() {
let near =
|ax: f64, ay: f64, bx: f64, by: f64| (ax - bx).abs() < 0.5 && (ay - by).abs() < 0.5;
if near(last.rx0, last.ry0, q[0], q[1]) && near(last.rx1, last.ry1, q[2], q[3]) {
let offset = match g.quad {
None => (q[0] - last.rx0).abs(),
Some(_) => (q[0] - last.rx0).hypot(q[1] - last.ry0),
};
if euclidean && offset > 0.1 && last.text.ends_with(g.ch) {
continue;
}
last.text.push(g.ch);
last.ltr = !is_right_to_left(&last.text);
last.blank = last.blank && g.ch.is_whitespace();
last.nchars += 1;
last.fb = last.fb || (0xFB00..=0xFB06).contains(&(g.ch as u32));
last.lig = is_ligature(&last.text);
continue;
}
}
let text = g.ch.to_string();
let ltr = !is_right_to_left(&text);
let blank = g.ch.is_whitespace();
let lig = is_ligature(&text);
let fb = (0xFB00..=0xFB06).contains(&(g.ch as u32));
cells.push(Cell {
text,
rx0: q[0],
ry0: q[1],
rx1: q[2],
ry1: q[3],
rx2: q[4],
ry2: q[5],
rx3: q[6],
ry3: q[7],
ltr,
active: true,
lig_carry: false,
font: g.font,
blank,
lig,
fb,
nchars: 1,
b_l: (g.ll as f64).min(g.lr as f64),
b_r: (g.ll as f64).max(g.lr as f64),
b_b: (g.lb as f64).min(g.lt as f64),
b_t: (g.lb as f64).max(g.lt as f64),
pen: g.pen.map(|p| p.map(f64::from)),
math_font: g.math_font,
});
}
cells
}
pub(crate) fn line_cells(glyphs: &[Glyph], page_h: f32, euclidean: bool) -> Vec<TextCell> {
line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::from_env()).0
}
pub(crate) fn word_cells(glyphs: &[Glyph], page_h: f32, euclidean: bool) -> Vec<TextCell> {
line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::from_env()).1
}
#[cfg(test)]
pub(crate) fn line_and_word_cells(
glyphs: &[Glyph],
page_h: f32,
euclidean: bool,
) -> (Vec<TextCell>, Vec<TextCell>) {
line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::Legacy)
}
pub(crate) fn line_and_word_cells_with(
glyphs: &[Glyph],
page_h: f32,
euclidean: bool,
gap: WordGap,
) -> (Vec<TextCell>, Vec<TextCell>) {
let built = build_cells(glyphs, euclidean);
if gap != WordGap::Legacy {
return contract_runs(&built, gap, page_h);
}
let to_text_cell = |c: Cell| {
let l = c.rx0.min(c.rx1).min(c.rx2).min(c.rx3) as f32;
let r = c.rx0.max(c.rx1).max(c.rx2).max(c.rx3) as f32;
let top = c.ry0.max(c.ry1).max(c.ry2).max(c.ry3) as f32;
let bot = c.ry0.min(c.ry1).min(c.ry2).min(c.ry3) as f32;
TextCell {
text: c.text,
l,
t: page_h - top,
r,
b: page_h - bot,
}
};
let mut word_run: Vec<Cell> = built.clone();
let mut cells = built;
contract(&mut cells, euclidean, LINE_FACTORS);
let lines = to_text_cells(cells, to_text_cell);
contract(&mut word_run, euclidean, WORD_FACTORS);
word_run.retain(|c| !c.text.trim().is_empty());
let words = to_text_cells(word_run, to_text_cell);
(lines, words)
}
fn to_text_cells(cells: Vec<Cell>, f: impl Fn(Cell) -> TextCell) -> Vec<TextCell> {
let mut out = Vec::with_capacity(cells.len());
out.extend(cells.into_iter().map(f));
out
}
fn is_rtl_char(c: char) -> bool {
let ch = c as u32;
(0x0600..=0x06FF).contains(&ch)
|| (0x0750..=0x077F).contains(&ch)
|| (0x08A0..=0x08FF).contains(&ch)
|| (0xFB50..=0xFDFF).contains(&ch)
|| (0xFE70..=0xFEFF).contains(&ch)
|| (0x0590..=0x05FF).contains(&ch)
|| (0xFB1D..=0xFB4F).contains(&ch)
|| (0x0700..=0x074F).contains(&ch)
|| (0x0780..=0x07BF).contains(&ch)
|| (0x07C0..=0x07FF).contains(&ch)
}
fn is_right_to_left(s: &str) -> bool {
!s.is_empty() && s.chars().all(is_rtl_char)
}
fn is_punct_or_space(s: &str) -> bool {
let mut chars = s.chars();
let (Some(c), None) = (chars.next(), chars.next()) else {
return false;
};
if matches!(
c,
' ' | '\t'
| '\n'
| '\r'
| '\u{0c}'
| '\u{0b}'
| '.'
| ','
| ';'
| ':'
| '!'
| '?'
| '('
| ')'
| '['
| ']'
| '{'
| '}'
| '\''
| '"'
| '`'
| '\u{2018}'
| '\u{2019}'
| '\u{201c}'
| '\u{201d}'
| '-'
| '\u{2013}'
| '\u{2014}'
| '_'
| '/'
| '\\'
| '|'
| '@'
| '#'
| '%'
| '&'
| '*'
| '+'
| '='
| '<'
| '>'
) {
return true;
}
let ch = c as u32;
(0x2000..=0x206F).contains(&ch)
|| (0x3000..=0x303F).contains(&ch)
|| (0xFE50..=0xFE6F).contains(&ch)
|| (0xFF00..=0xFF0F).contains(&ch)
|| (0xFF1A..=0xFF1F).contains(&ch)
|| (0xFF3B..=0xFF5E).contains(&ch)
}
fn is_ligature(s: &str) -> bool {
matches!(s, "ff" | "fi" | "fl" | "ffi" | "ffl")
|| s.chars().any(|c| (0xFB00..=0xFB06).contains(&(c as u32)))
}
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub enum WordGap {
Legacy,
Factor(f64),
#[default]
Adaptive,
}
impl WordGap {
pub const ACCEPTED: &'static str = "legacy, adaptive, or a factor in (0, 4]";
pub fn parse(s: &str) -> Result<Self, String> {
let t = s.trim().to_ascii_lowercase();
match t.as_str() {
"legacy" => Ok(WordGap::Legacy),
"adaptive" | "auto" | "default" => Ok(WordGap::Adaptive),
_ => match t.parse::<f64>() {
Ok(f) if f.is_finite() && f > 0.0 && f <= 4.0 => Ok(WordGap::Factor(f)),
_ => Err(format!(
"pdf_word_gap must be {}, got {s:?}",
WordGap::ACCEPTED
)),
},
}
}
pub fn from_env() -> Self {
let Some(v) = docling_core::env::nonempty("DOCLING_RS_PDF_WORD_GAP") else {
return WordGap::default();
};
WordGap::parse(&v).unwrap_or_else(|e| {
static WARNED: std::sync::Once = std::sync::Once::new();
WARNED.call_once(|| {
eprintln!("docling-pdf: DOCLING_RS_PDF_WORD_GAP: {e}; using adaptive")
});
WordGap::default()
})
}
}
struct RunCell<'a> {
cell: &'a Cell,
ux: f64,
uy: f64,
advance: f64,
height: f64,
space: bool,
}
impl<'a> RunCell<'a> {
fn new(cell: &'a Cell) -> Self {
let (dx, dy) = (cell.rx1 - cell.rx0, cell.ry1 - cell.ry0);
let advance = dx.hypot(dy);
let (ux, uy) = if advance > 1e-9 {
(dx / advance, dy / advance)
} else {
(1.0, 0.0)
};
let h0 = (cell.rx3 - cell.rx0).hypot(cell.ry3 - cell.ry0);
let h1 = (cell.rx2 - cell.rx1).hypot(cell.ry2 - cell.ry1);
RunCell {
cell,
ux,
uy,
advance,
height: 0.5 * (h0 + h1),
space: cell.blank,
}
}
fn scale(&self) -> f64 {
if self.advance > 1e-6 {
self.advance
} else {
(0.5 * self.height).max(1e-6)
}
}
}
fn forward_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
let (l, r) = (lhs.cell, rhs.cell);
let (tx, ty) = (0.5 * (l.rx1 + l.rx2), 0.5 * (l.ry1 + l.ry2));
let (hx, hy) = (0.5 * (r.rx0 + r.rx3), 0.5 * (r.ry0 + r.ry3));
(hx - tx) * lhs.ux + (hy - ty) * lhs.uy
}
fn facing_edge_overlap(lhs: &RunCell, rhs: &RunCell) -> f64 {
let (l, r) = (lhs.cell, rhs.cell);
let (ux, uy) = if l.ltr {
(lhs.ux, lhs.uy)
} else {
(-lhs.ux, -lhs.uy)
};
let (nx, ny) = (-uy, ux);
let proj = |x: f64, y: f64| x * nx + y * ny;
let (a0, a1) = if l.ltr {
(proj(l.rx1, l.ry1), proj(l.rx2, l.ry2))
} else {
(proj(l.rx0, l.ry0), proj(l.rx3, l.ry3))
};
let (b0, b1) = if l.ltr {
(proj(r.rx0, r.ry0), proj(r.rx3, r.ry3))
} else {
(proj(r.rx1, r.ry1), proj(r.rx2, r.ry2))
};
a0.max(a1).min(b0.max(b1)) - a0.min(a1).max(b0.min(b1))
}
fn is_math_glyph(text: &str) -> bool {
const MATH: &str = "∑∏∫√∞∈∉≠≤≥⊂⊃⊆⊇⊥∪∩⎛⎜⎝⎞⎟⎠⎡⎢⎣⎤⎥⎦";
text.chars().any(|c| MATH.contains(c))
}
fn is_local_attachment(lhs: &RunCell, rhs: &RunCell) -> bool {
let scale = lhs.scale().max(rhs.scale());
if forward_gap(lhs, rhs) > 0.10 * scale {
return false;
}
let (off, (lh, rh)) = baseline_offset(lhs, rhs);
let math = |c: &RunCell| c.cell.math_font || is_math_glyph(&c.cell.text);
off <= 2.0 * lh.max(rh).max(1e-6) && (math(lhs) || math(rhs))
}
fn baseline_offset(lhs: &RunCell, rhs: &RunCell) -> (f64, (f64, f64)) {
let (nx, ny) = (-lhs.uy, lhs.ux);
match (lhs.cell.pen, rhs.cell.pen) {
(Some(a), Some(b)) => (
((b[0] - a[0]) * nx + (b[1] - a[1]) * ny).abs(),
(a[2], b[2]),
),
_ => (
((rhs.cell.rx0 - lhs.cell.rx0) * nx + (rhs.cell.ry0 - lhs.cell.ry0) * ny).abs(),
(lhs.height, rhs.height),
),
}
}
fn continues_line(lhs: &RunCell, rhs: &RunCell) -> bool {
if lhs.ux * rhs.ux + lhs.uy * rhs.uy < 0.985 {
return false;
}
let scale = lhs.scale().max(rhs.scale());
let gap = forward_gap(lhs, rhs);
if facing_edge_overlap(lhs, rhs) <= 1e-6 && !is_local_attachment(lhs, rhs) {
return false;
}
-scale <= gap && gap <= 4.0 * scale
}
fn baselines_compatible(lhs: &RunCell, rhs: &RunCell) -> bool {
let (off, (lh, rh)) = baseline_offset(lhs, rhs);
off <= 0.35 * lh.min(rh).max(1e-6) || is_local_attachment(lhs, rhs)
}
fn normalized_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
forward_gap(lhs, rhs).max(0.0) / (0.5 * (lhs.scale() + rhs.scale())).max(1e-6)
}
#[derive(Clone, Copy, PartialEq)]
enum TrackClass {
Letter,
Dot,
Other,
}
fn track_class(text: &str) -> TrackClass {
if matches!(text, "." | "·" | "…") {
TrackClass::Dot
} else if !text.is_empty() && text.chars().all(char::is_alphanumeric) {
TrackClass::Letter
} else {
TrackClass::Other
}
}
fn tracking_tolerance(gap: f64) -> f64 {
(0.08 * gap).max(0.25)
}
fn tracked_gaps(run: &[RunCell]) -> Vec<bool> {
struct Gap {
left: usize,
right: usize,
pt: f64,
n: f64,
left_class: TrackClass,
right_class: TrackClass,
}
let mut gaps: Vec<Gap> = Vec::new();
let mut prev: Option<usize> = None;
let mut crossed_space = false;
for (i, c) in run.iter().enumerate() {
if c.space {
crossed_space = true;
continue;
}
if let (Some(p), false) = (prev, crossed_space) {
gaps.push(Gap {
left: p,
right: i,
pt: forward_gap(&run[p], c),
n: normalized_gap(&run[p], c),
left_class: track_class(&run[p].cell.text),
right_class: track_class(&c.cell.text),
});
}
prev = Some(i);
crossed_space = false;
}
let joined = |k: usize| gaps[k + 1].left == gaps[k].right;
let stretch = |k: usize, fits: &dyn Fn(&Gap) -> bool| {
let mut end = k;
while end < gaps.len() && fits(&gaps[end]) && (end == k || joined(end - 1)) {
end += 1;
}
end
};
let flanks_open = |k: usize, end: usize, floor: f64| {
let before = k > 0 && joined(k - 1) && gaps[k - 1].pt < floor;
let after = end < gaps.len() && joined(end - 1) && gaps[end].pt < floor;
!before && !after
};
let mut tracked = vec![false; run.len()];
let mut leader = vec![false; run.len()];
let mut letter_tracking: Vec<f64> = Vec::new();
let mut k = 0;
while k < gaps.len() {
let dots = |g: &Gap| {
g.left_class == TrackClass::Dot && g.right_class == TrackClass::Dot && g.n <= 1.0
};
let end = stretch(k, &dots);
if end - k >= 3 {
for g in &gaps[k..end] {
tracked[g.right] = true;
leader[g.left] = true;
leader[g.right] = true;
}
k = end;
continue;
}
let first = &gaps[k];
let letters = |g: &Gap| {
g.left_class == TrackClass::Letter
&& g.right_class == TrackClass::Letter
&& (0.1..=1.0).contains(&g.n)
};
if !letters(first) {
k += 1;
continue;
}
let (mut lo, mut hi) = (first.pt, first.pt);
let mut end = k + 1;
while end < gaps.len()
&& joined(end - 1)
&& letters(&gaps[end])
&& hi.max(gaps[end].pt) - lo.min(gaps[end].pt) <= tracking_tolerance(lo)
{
lo = lo.min(gaps[end].pt);
hi = hi.max(gaps[end].pt);
end += 1;
}
let one_char = gaps[k..end]
.iter()
.all(|g| run[g.right].cell.text == run[first.left].cell.text);
if end - k >= 3 && !one_char && flanks_open(k, end, lo - tracking_tolerance(lo)) {
for g in &gaps[k..end] {
tracked[g.right] = true;
}
letter_tracking.push(0.5 * (lo + hi));
k = end;
} else {
k += 1;
}
}
for &t in &letter_tracking {
let tol = tracking_tolerance(t);
let same = |g: &Gap| {
(g.left_class == TrackClass::Letter || g.right_class == TrackClass::Letter)
&& g.left_class != TrackClass::Dot
&& g.right_class != TrackClass::Dot
&& g.n <= 1.0
&& (g.pt - t).abs() <= tol
};
let mut k = 0;
while k < gaps.len() {
let end = stretch(k, &same);
if end == k {
k += 1;
continue;
}
if flanks_open(k, end, t - tol) && !gaps[k..end].iter().any(|g| leader[g.left]) {
for g in &gaps[k..end] {
tracked[g.right] = true;
}
}
k = end;
}
}
tracked
}
const GAP_CLUSTER_CLIP: f64 = 0.5;
fn infer_word_gap(run: &[RunCell], tracked: &[bool]) -> f64 {
let mut gaps = Vec::new();
let mut prev: Option<&RunCell> = None;
let mut crossed_space = false;
for (i, c) in run.iter().enumerate() {
if c.space {
crossed_space = true;
continue;
}
if let (Some(p), false, false) = (prev, crossed_space, tracked[i]) {
gaps.push(normalized_gap(p, c).min(GAP_CLUSTER_CLIP));
}
prev = Some(c);
crossed_space = false;
}
if gaps.len() < 2 {
return 0.25;
}
let mut low = gaps.iter().copied().fold(f64::INFINITY, f64::min);
let mut high = gaps.iter().copied().fold(f64::NEG_INFINITY, f64::max);
if high < 0.18 || high - low < 0.08 {
return 0.25;
}
for _ in 0..8 {
let mid = 0.5 * (low + high);
let (mut ls, mut ln, mut hs, mut hn) = (0.0, 0usize, 0.0, 0usize);
for &g in &gaps {
if g <= mid {
ls += g;
ln += 1;
} else {
hs += g;
hn += 1;
}
}
if ln == 0 || hn == 0 {
return 0.25;
}
low = ls / ln as f64;
high = hs / hn as f64;
}
if high < 0.18 || high - low < 0.08 {
return 0.25;
}
(0.5 * (low + high)).max(0.18)
}
struct Agg {
text: String,
ltr: bool,
q: [f64; 8],
glued: bool,
}
impl Agg {
fn of(c: &Cell, glued: bool) -> Self {
Agg {
text: c.text.clone(),
ltr: c.ltr,
q: [c.rx0, c.ry0, c.rx1, c.ry1, c.rx2, c.ry2, c.rx3, c.ry3],
glued,
}
}
fn append(&mut self, text: &str, ltr: bool, q: &[f64; 8], space: bool) {
if self.ltr && ltr {
if space {
self.text.push(' ');
}
self.text.push_str(text);
} else {
let sep = if space { " " } else { "" };
self.text = format!("{text}{sep}{}", self.text);
self.ltr = false;
}
let (mut ux, mut uy) = (self.q[2] - self.q[0], self.q[3] - self.q[1]);
if ux.hypot(uy) <= 1e-9 {
(ux, uy) = (q[2] - q[0], q[3] - q[1]);
}
let n = ux.hypot(uy);
if n <= 1e-9 {
return;
}
let (ux, uy) = (ux / n, uy / n);
let (nx, ny) = (-uy, ux);
let (mut u0, mut u1, mut n0, mut n1) = (
f64::INFINITY,
f64::NEG_INFINITY,
f64::INFINITY,
f64::NEG_INFINITY,
);
for k in 0..4 {
for (x, y) in [(self.q[2 * k], self.q[2 * k + 1]), (q[2 * k], q[2 * k + 1])] {
let (u, v) = (x * ux + y * uy, x * nx + y * ny);
u0 = u0.min(u);
u1 = u1.max(u);
n0 = n0.min(v);
n1 = n1.max(v);
}
}
let pt = |u: f64, v: f64| (u * ux + v * nx, u * uy + v * ny);
let (a, b, c, d) = (pt(u0, n0), pt(u1, n0), pt(u1, n1), pt(u0, n1));
self.q = [a.0, a.1, b.0, b.1, c.0, c.1, d.0, d.1];
}
fn into_cell(self, page_h: f32) -> TextCell {
let xs = [self.q[0], self.q[2], self.q[4], self.q[6]];
let ys = [self.q[1], self.q[3], self.q[5], self.q[7]];
let (l, r) = (
xs.iter().copied().fold(f64::INFINITY, f64::min),
xs.iter().copied().fold(f64::NEG_INFINITY, f64::max),
);
let (b, t) = (
ys.iter().copied().fold(f64::INFINITY, f64::min),
ys.iter().copied().fold(f64::NEG_INFINITY, f64::max),
);
TextCell {
text: self.text,
l: l as f32,
t: page_h - t as f32,
r: r as f32,
b: page_h - b as f32,
}
}
}
fn page_draws_spaces(runs: &[Vec<RunCell>]) -> bool {
let long = |r: &&Vec<RunCell>| r.iter().filter(|c| !c.space).count() >= 8;
let lines = runs.iter().filter(long).count();
let spaced = runs
.iter()
.filter(long)
.filter(|r| r.iter().any(|c| c.space))
.count();
lines > 0 && 2 * spaced >= lines
}
fn contract_runs(cells: &[Cell], gap: WordGap, page_h: f32) -> (Vec<TextCell>, Vec<TextCell>) {
let mut runs: Vec<Vec<RunCell>> = Vec::new();
for c in cells.iter().filter(|c| !c.text.is_empty()) {
let rc = RunCell::new(c);
if rc.space {
match runs.last_mut() {
Some(run) => run.push(rc),
None => runs.push(vec![rc]),
}
continue;
}
let starts = match runs.last().and_then(|r| r.iter().rev().find(|c| !c.space)) {
Some(prev) => !continues_line(prev, &rc),
None => runs.is_empty(),
};
if starts {
runs.push(Vec::new());
}
runs.last_mut().expect("a run is open").push(rc);
}
let (mut words_out, mut lines_out) = (Vec::new(), Vec::new());
let page_spaced = page_draws_spaces(&runs);
for run in &runs {
let has_spaces = page_spaced || run.iter().any(|c| c.space);
let tracked = tracked_gaps(run);
let threshold = match gap {
WordGap::Factor(f) if has_spaces => f.max(0.35),
WordGap::Factor(f) => f,
_ => (if has_spaces {
1.0
} else {
infer_word_gap(run, &tracked)
})
.min(0.35),
};
let mut words: Vec<Agg> = Vec::new();
let mut prev: Option<&RunCell> = None;
let mut boundary = false;
for (i, c) in run.iter().enumerate() {
if c.space {
boundary = true;
continue;
}
let mut starts = words.is_empty() || boundary;
let mut glued = false;
if !starts
&& c.cell.text == "."
&& i + 4 < run.len()
&& run[i + 1].space
&& run[i + 2].cell.text == "."
&& run[i + 3].space
&& run[i + 4].cell.text == "."
&& prev.is_some_and(|p| p.cell.text != ".")
{
starts = true;
}
if let (false, Some(p)) = (starts, prev) {
let shifted = !baselines_compatible(p, c);
let gapped = !tracked[i] && normalized_gap(p, c) > threshold;
starts = shifted || gapped;
let opens = |s: &str| matches!(s.chars().last(), Some('(' | '[' | '{'));
let closes = |s: &str| matches!(s.chars().next(), Some(')' | ']' | '}'));
glued = shifted
&& !gapped
&& (words.last().is_some_and(|w| opens(&w.text)) || closes(&c.cell.text));
}
if starts {
words.push(Agg::of(c.cell, glued));
} else {
let q = [
c.cell.rx0, c.cell.ry0, c.cell.rx1, c.cell.ry1, c.cell.rx2, c.cell.ry2,
c.cell.rx3, c.cell.ry3,
];
words.last_mut().expect("a word is open").append(
&c.cell.text,
c.cell.ltr,
&q,
false,
);
}
prev = Some(c);
boundary = false;
}
let mut it = words.into_iter();
let Some(first) = it.next() else {
continue;
};
let mut line = Agg {
text: first.text.clone(),
ltr: first.ltr,
q: first.q,
glued: false,
};
words_out.push(first.into_cell(page_h));
for w in it {
line.append(&w.text, w.ltr, &w.q, !w.glued);
words_out.push(w.into_cell(page_h));
}
lines_out.push(line.into_cell(page_h));
}
(lines_out, words_out)
}
#[cfg(test)]
mod tests {
use super::*;
fn glyph(ch: char, l: f32, r: f32) -> Glyph {
Glyph {
ch,
l,
b: 100.0,
r,
t: 110.0,
ll: l,
lb: 98.0,
lr: r,
lt: 110.0,
font: 0,
quad: None,
pen: None,
math_font: false,
invisible: false,
}
}
#[test]
fn space_glyph_separates_tight_words() {
let glyphs = [
glyph('M', 137.66, 143.74),
glyph('O', 143.74, 149.82),
glyph('D', 149.82, 155.90),
glyph('E', 155.90, 161.98),
glyph(' ', 161.84, 164.09),
glyph('t', 163.82, 166.60),
glyph('o', 166.60, 171.60),
];
let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
assert_eq!(words, ["MODE", "to"]);
assert_eq!(lines.len(), 1);
assert_eq!(lines[0].text, "MODE to");
}
#[test]
fn stacked_glyphs_at_one_x_stay_separate_cells() {
let at = |ch: char, b: f32| Glyph {
lb: b,
lt: b + 10.0,
b,
t: b + 10.0,
..glyph(ch, 98.0, 103.0)
};
let ticks: Vec<Glyph> = "345678"
.chars()
.enumerate()
.map(|(k, ch)| at(ch, 316.0 + 25.92 * k as f32))
.collect();
let lines = line_cells(&ticks, 792.0, true);
let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
assert_eq!(texts, ["3", "4", "5", "6", "7", "8"]);
assert!(lines.windows(2).all(|w| w[0].t > w[1].t));
let lig = [glyph('f', 10.0, 16.0), glyph('i', 10.0, 16.0)];
let lines = line_cells(&lig, 792.0, true);
assert_eq!(lines.len(), 1);
assert_eq!(lines[0].text, "fi");
}
#[test]
fn cells_do_not_keep_the_glyph_buffer() {
let glyphs: Vec<Glyph> = (0..400)
.map(|i| {
let x = (i % 40) as f32 * 6.0;
let ch = if i % 4 == 3 { ' ' } else { '7' };
let mut g = glyph(ch, x, x + 6.0);
let row = (i / 40) as f32 * 14.0;
(g.b, g.t, g.lb, g.lt) = (100.0 + row, 110.0 + row, 98.0 + row, 110.0 + row);
g
})
.collect();
let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
assert_eq!((lines.len(), words.len()), (10, 100));
assert_eq!(lines.capacity(), lines.len());
assert_eq!(words.capacity(), words.len());
}
fn und_dem_line() -> Vec<Glyph> {
let at = |ch: char, l: f32, r: f32, font: u64| Glyph {
ch,
l,
b: 682.056,
r,
t: 691.05,
ll: l,
lb: 682.056,
lr: r,
lt: 691.05,
font,
quad: None,
pen: None,
math_font: false,
invisible: false,
};
let mut g = Vec::new();
let mut run = |text: &str, edges: &[f32], font: u64| {
for (i, ch) in text.chars().enumerate() {
g.push(at(ch, edges[i], edges[i + 1], font));
}
};
run(
"schaft",
&[
328.976, 333.216, 338.572, 344.325, 350.486, 353.920, 357.248,
],
1,
);
run("und", &[359.261, 365.121, 370.875, 377.035], 2);
run("dem", &[378.990, 385.151, 390.701, 399.287], 2);
run("Öst", &[401.214, 409.092, 413.332, 416.660], 1);
g
}
#[test]
fn legacy_rule_keeps_the_borderline_und_dem_glued() {
let (lines, words) = line_and_word_cells(&und_dem_line(), 792.0, true);
assert!(lines.iter().any(|c| c.text == "unddem"), "{lines:?}");
assert!(words.iter().any(|c| c.text == "unddem"), "{words:?}");
}
#[test]
fn line_local_word_gaps_split_und_dem() {
for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
let (lines, words) = line_and_word_cells_with(&und_dem_line(), 792.0, true, gap);
let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
assert_eq!(texts, ["schaft und dem Öst"], "{gap:?}");
let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
assert_eq!(texts, ["schaft", "und", "dem", "Öst"], "{gap:?}");
assert!((words[1].l - 359.261).abs() < 1e-3 && (words[1].r - 377.035).abs() < 1e-3);
}
let (lines, _) =
line_and_word_cells_with(&und_dem_line(), 792.0, true, WordGap::Factor(0.5));
assert_eq!(lines[0].text, "schaftunddemÖst");
}
#[test]
fn a_superscript_attaches_by_pen_origin_and_math_face() {
let at = |ch: char, l: f32, y: f32, size: f32, math: bool, pen: bool| Glyph {
lb: y - 0.2 * size,
lt: y + 0.8 * size,
b: y - 0.2 * size,
t: y + 0.8 * size,
pen: pen.then_some([l, y, size]),
math_font: math,
..glyph(ch, l, l + 0.5 * size)
};
let line = |rise: f32, math: bool, pen: bool| {
let mut g: Vec<Glyph> = "Lysak"
.chars()
.enumerate()
.map(|(k, ch)| at(ch, 100.0 + 5.0 * k as f32, 600.0, 10.0, math, pen))
.collect();
g.extend(
"[0000"
.chars()
.enumerate()
.map(|(k, ch)| at(ch, 125.0 + 3.5 * k as f32, 600.0 + rise, 7.0, math, pen)),
);
let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
(
lines[0].text.clone(),
words.iter().map(|w| w.text.clone()).collect::<Vec<_>>(),
)
};
let one = |s: &str| (s.to_string(), vec![s.to_string()]);
let two = |s: &str| {
(
s.to_string(),
vec!["Lysak".to_string(), "[0000".to_string()],
)
};
assert_eq!(line(3.6, true, true), one("Lysak[0000"));
assert_eq!(line(3.6, false, true), two("Lysak [0000"));
assert_eq!(line(2.0, false, true), one("Lysak[0000"));
assert_eq!(line(2.0, false, false), two("Lysak [0000"));
}
#[test]
fn a_touching_superscript_joins_the_line_text_inside_brackets_only() {
let at = |ch: char, l: f32, w: f32, y: f32, size: f32| Glyph {
lb: y - 0.2 * size,
lt: y + 0.8 * size,
b: y - 0.2 * size,
t: y + 0.8 * size,
pen: Some([l, y, size]),
..glyph(ch, l, l + w)
};
let g = [
at('E', 100.0, 6.0, 600.0, 10.5),
at('G', 106.0, 6.9, 600.0, 10.5),
at('(', 115.3, 3.2, 600.0, 10.5),
at('1', 118.5, 3.1, 603.5, 6.8),
at(')', 121.6, 3.2, 600.0, 10.5),
at('e', 127.2, 5.0, 600.0, 10.5),
];
let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
assert_eq!(lines[0].text, "EG (1) e");
let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
assert_eq!(words, ["EG", "(", "1", ")", "e"]);
let g = [
at('E', 100.0, 6.0, 600.0, 10.5),
at('G', 106.0, 6.9, 600.0, 10.5),
at('1', 112.9, 3.1, 603.5, 6.8),
];
let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
assert_eq!(lines[0].text, "EG 1");
}
#[test]
fn a_factor_keeps_docling_parse_s_floor_on_lines_with_space_glyphs() {
let mut g = Vec::new();
let mut x = 100.0f32;
let put = |g: &mut Vec<Glyph>, s: &str, x: &mut f32| {
for ch in s.chars() {
g.push(glyph(ch, *x, *x + 2.5));
*x += 2.5;
}
};
put(&mut g, "Die", &mut x);
g.push(glyph(' ', x, x + 2.5));
x += 2.5;
put(&mut g, "Verpf", &mut x);
x += 0.6;
put(&mut g, "lichtungen", &mut x);
let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Factor(0.2));
assert_eq!(lines[0].text, "Die Verpflichtungen");
let spaceless: Vec<Glyph> = g.into_iter().filter(|c| c.ch != ' ').collect();
let (lines, _) = line_and_word_cells_with(&spaceless, 792.0, true, WordGap::Factor(0.2));
assert_eq!(lines[0].text, "Die Verpf lichtungen");
}
#[test]
fn right_to_left_glyphs_in_visual_order_stay_one_line() {
let mut g = Vec::new();
let mut x = 100.0f32;
for (k, word) in [
"\u{0631}\u{0627}\u{0632}\u{0627}\u{0628}",
"\u{0631}\u{062f}",
]
.iter()
.enumerate()
{
if k > 0 {
x += 3.0;
}
for ch in word.chars() {
g.push(glyph(ch, x, x + 5.0));
x += 5.0;
}
}
for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
let (lines, words) = line_and_word_cells_with(&g, 792.0, true, gap);
assert_eq!(
lines.len(),
1,
"{gap:?}: {:?}",
lines.iter().map(|c| &c.text).collect::<Vec<_>>()
);
assert_eq!(words.len(), 2, "{gap:?}");
}
}
#[test]
fn letter_spacing_stays_one_word_under_the_adaptive_rule() {
let mut g = Vec::new();
let mut x = 100.0f32;
for (k, word) in ["Allgemeine", "Bestimmungen"].iter().enumerate() {
if k > 0 {
x += 6.0;
}
for ch in word.chars() {
g.push(glyph(ch, x, x + 5.0));
x += 5.0 + 1.5;
}
x -= 1.5;
}
let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
assert_eq!(lines[0].text, "Allgemeine Bestimmungen");
}
fn set_line(pieces: &[(&str, f32)], y: f32) -> Vec<Glyph> {
let mut g = Vec::new();
let mut x = 100.0f32;
for (text, gap) in pieces {
x += gap;
for ch in text.chars() {
g.push(Glyph {
b: y,
t: y + 10.0,
lb: y - 2.0,
lt: y + 10.0,
..glyph(ch, x, x + 2.5)
});
x += 2.5;
}
}
g
}
#[test]
fn one_wide_gap_does_not_raise_the_line_s_word_gap() {
let g = set_line(
&[
("jedoch", 0.0),
("werden", 0.8),
("weiterlaufende", 0.8),
("Quartierkosten", 8.0),
],
600.0,
);
let (_, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
assert_eq!(
texts,
["jedoch", "werden", "weiterlaufende", "Quartierkosten"]
);
}
#[test]
fn a_lone_word_on_a_page_that_draws_spaces_keeps_its_kerning() {
let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
let spaced = |y| {
set_line(
&[
("Die", 0.0),
(" ", 0.0),
("Taxonomie", 0.0),
(" ", 0.0),
("gilt", 0.0),
],
y,
)
};
let mut page = lone();
page.extend(spaced(600.0));
page.extend(spaced(620.0));
let texts = |g: &[Glyph]| {
let (lines, _) = line_and_word_cells_with(g, 792.0, true, WordGap::Adaptive);
lines.into_iter().map(|c| c.text).collect::<Vec<_>>()
};
assert!(texts(&page).contains(&"Offenlegungspflichten".to_string()));
assert_eq!(texts(&lone()), ["Offenlegungspf lichten"]);
}
#[test]
fn word_gap_spellings() {
assert_eq!(WordGap::parse("adaptive"), Ok(WordGap::Adaptive));
assert_eq!(WordGap::parse(" Legacy "), Ok(WordGap::Legacy));
assert_eq!(WordGap::parse("0.2"), Ok(WordGap::Factor(0.2)));
for bad in ["0", "-1", "5", "nan", "wide"] {
assert!(WordGap::parse(bad).is_err(), "{bad}");
}
}
}