1use crate::pdfium_backend::{Glyph, TextCell};
15
16const 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;
28const H_TOL: f64 = 1.0; #[derive(Clone)]
31struct Cell {
32 text: String,
33 rx0: f64,
34 ry0: f64, rx1: f64,
36 ry1: f64, rx2: f64,
38 ry2: f64, rx3: f64,
40 ry3: f64, ltr: bool,
42 active: bool,
43 lig_carry: bool, font: u64, blank: bool, lig: bool, fb: bool, nchars: usize, b_l: f64, b_r: f64,
56 b_b: f64,
57 b_t: f64,
58 pen: Option<[f64; 3]>,
61 math_font: bool,
63}
64
65impl Cell {
66 fn length(&self) -> f64 {
68 ((self.rx1 - self.rx0).powi(2) + (self.ry1 - self.ry0).powi(2)).sqrt()
69 }
70
71 fn avg_char_width(&self) -> f64 {
73 if self.nchars > 0 {
74 self.length() / self.nchars as f64
75 } else {
76 0.0
77 }
78 }
79
80 fn gap(&self, other: &Cell) -> f64 {
82 ((self.rx1 - other.rx0).powi(2) + (self.ry1 - other.ry0).powi(2)).sqrt()
83 }
84
85 fn adjacent(&self, other: &Cell, eps0: f64, eps1: f64) -> bool {
89 let d0 = self.gap(other);
90 let d1 = ((self.rx2 - other.rx3).powi(2) + (self.ry2 - other.ry3).powi(2)).sqrt();
91 d0 < eps0 && d1 < eps1
92 }
93
94 fn same_orientation(&self, other: &Cell) -> bool {
96 self.ltr == other.ltr || is_punct_or_space(&self.text) || is_punct_or_space(&other.text)
97 }
98
99 fn merge_with(&mut self, other: &Cell, delta: f64, euclidean: bool) {
110 let gap = if euclidean {
111 self.gap(other)
112 } else {
113 other.rx0 - self.rx1
114 };
115 let space = delta < gap;
116 if !self.ltr || !other.ltr {
117 if space {
118 self.text.insert(0, ' ');
119 }
120 self.text = format!("{}{}", other.text, self.text);
121 self.ltr = false;
122 } else {
123 if space {
124 self.text.push(' ');
125 }
126 self.text.push_str(&other.text);
127 self.ltr = true;
128 }
129 self.rx1 = other.rx1;
131 self.ry1 = other.ry1;
132 self.rx2 = other.rx2;
133 self.ry2 = other.ry2;
134 self.blank = self.blank && other.blank;
141 self.nchars += other.nchars + usize::from(space);
142 self.fb = self.fb || other.fb;
143 self.lig = if self.text.len() <= 3 {
144 is_ligature(&self.text)
145 } else {
146 self.fb
147 };
148 let (l, r, b, t) = quad_bounds(self);
149 self.b_l = l;
150 self.b_r = r;
151 self.b_b = b;
152 self.b_t = t;
153 }
154}
155
156fn bounds(c: &Cell) -> (f64, f64, f64, f64) {
159 (c.b_l, c.b_r, c.b_b, c.b_t)
160}
161
162fn quad_bounds(c: &Cell) -> (f64, f64, f64, f64) {
164 let xs = [c.rx0, c.rx1, c.rx2, c.rx3];
165 let ys = [c.ry0, c.ry1, c.ry2, c.ry3];
166 let fold = |it: &[f64], f: fn(f64, f64) -> f64| it.iter().copied().reduce(f).unwrap();
167 (
168 fold(&xs, f64::min),
169 fold(&xs, f64::max),
170 fold(&ys, f64::min),
171 fold(&ys, f64::max),
172 )
173}
174
175fn gap_occupied(cells: &[Cell], i: usize, j: usize) -> bool {
184 let (al, ar, ab, at) = bounds(&cells[i]);
185 let (bl, br, bb, bt) = bounds(&cells[j]);
186 let (gl, gr) = if ar <= bl { (ar, bl) } else { (br, al) };
187 if gr - gl < 0.5 {
188 return false; }
190 let (band_b, band_t) = (ab.min(bb), at.max(bt));
191 cells.iter().enumerate().any(|(k, c)| {
192 if k == i || k == j || !c.active || c.blank {
193 return false;
194 }
195 let (cl, cr, cb, ct) = bounds(c);
196 let overlap = (ct.min(band_t) - cb.max(band_b)).max(0.0);
198 overlap > 0.5 * (ct - cb).max(f64::EPSILON)
199 && cr.min(gr) - cl.max(gl) > 0.1
201 })
202}
203
204fn applicable(a: &Cell, b: &Cell, parser: bool, block_spaces: bool) -> bool {
210 if !a.active || !b.active {
211 return false;
212 }
213 if block_spaces && (is_all_space(&a.text) || is_all_space(&b.text)) {
217 return false;
218 }
219 let lone_punct = |s: &str| {
225 let mut ch = s.chars();
226 matches!(ch.next(), Some(c) if c != ' ' && is_punct_or_space(&c.to_string()))
227 && ch.next().is_none()
228 };
229 let punct_bridge =
230 parser && ((lone_punct(&a.text) && !b.ltr) || (lone_punct(&b.text) && !a.ltr));
231 let font_neutral = a.lig || b.lig || punct_bridge;
232 if a.font != 0 && b.font != 0 && a.font != b.font && !font_neutral {
233 return false;
234 }
235 a.same_orientation(b)
236}
237
238fn pass_ltr(cells: &mut [Cell], allow_reverse: bool, euclidean: bool, p: Factors) {
240 for i in 0..cells.len() {
241 if !cells[i].active {
242 continue;
243 }
244 let mut j = i + 1;
245 while j < cells.len() {
246 if !applicable(&cells[i], &cells[j], euclidean, p.block_spaces) {
247 break;
248 }
249 let i_lig = cells[i].lig || cells[i].lig_carry;
250 let j_lig = cells[j].lig || cells[j].lig_carry;
251 let d0 = cells[i].avg_char_width() * p.merge;
252 let d1 = cells[i].avg_char_width() * p.merge_with_space;
253 let adj_d1 = d0 + if i_lig || j_lig { H_TOL } else { 0.0 };
254 if cells[i].adjacent(&cells[j], d0, adj_d1) && !gap_occupied(cells, i, j) {
255 let other = cells[j].clone();
256 cells[i].merge_with(&other, d1, euclidean);
257 cells[i].lig_carry = other.lig;
258 cells[j].active = false;
259 j += 1; } else if allow_reverse
261 && cells[j].adjacent(&cells[i], d0, adj_d1)
262 && !gap_occupied(cells, j, i)
263 {
264 let other = cells[i].clone();
265 cells[j].merge_with(&other, d1, euclidean);
266 cells[j].lig_carry = other.lig;
267 cells[i].active = false;
268 break; } else {
270 break;
271 }
272 }
273 }
274}
275
276fn pass_rtl(cells: &mut [Cell], euclidean: bool, p: Factors) {
279 let n = cells.len();
280 for k in 0..n {
281 let i = n - 1 - k;
282 if !cells[i].active || i == 0 {
283 continue;
284 }
285 let j = i - 1;
286 if !applicable(&cells[i], &cells[j], euclidean, p.block_spaces) {
287 continue;
288 }
289 let i_lig = cells[i].lig || cells[i].lig_carry;
290 let j_lig = cells[j].lig || cells[j].lig_carry;
291 let d0 = cells[i].avg_char_width() * p.merge;
292 let d1 = cells[i].avg_char_width() * p.merge_with_space;
293 let adj_d1 = d0 + if i_lig || j_lig { H_TOL } else { 0.0 };
294 if cells[j].adjacent(&cells[i], d0, adj_d1) && !gap_occupied(cells, j, i) {
295 let other = cells[i].clone();
296 cells[j].merge_with(&other, d1, euclidean);
297 cells[j].lig_carry = other.lig;
298 cells[i].active = false;
299 }
300 }
301}
302
303#[derive(Clone, Copy)]
306struct Factors {
307 merge: f64,
308 merge_with_space: f64,
309 block_spaces: bool,
310}
311
312const LINE_FACTORS: Factors = Factors {
313 merge: MERGE,
314 merge_with_space: MERGE_WITH_SPACE,
315 block_spaces: false,
316};
317const WORD_FACTORS: Factors = Factors {
318 merge: WORD_MERGE,
319 merge_with_space: WORD_MERGE_WITH_SPACE,
320 block_spaces: true,
321};
322
323fn is_all_space(s: &str) -> bool {
325 !s.is_empty() && s.chars().all(char::is_whitespace)
326}
327
328fn contract(cells: &mut Vec<Cell>, euclidean: bool, p: Factors) {
329 pass_ltr(cells, false, euclidean, p);
330 cells.retain(|c| c.active);
331 pass_rtl(cells, euclidean, p);
332 cells.retain(|c| c.active);
333 pass_ltr(cells, true, euclidean, p);
334 cells.retain(|c| c.active);
335}
336
337fn build_cells(glyphs: &[Glyph], euclidean: bool) -> Vec<Cell> {
340 let mut cells: Vec<Cell> = Vec::new();
341 for g in glyphs {
342 if !g.ll.is_finite() {
345 continue;
346 }
347 let q = g.quad.map(|q| q.map(f64::from)).unwrap_or_else(|| {
352 let (l, b, r, t) = (g.ll as f64, g.lb as f64, g.lr as f64, g.lt as f64);
353 [l, b, r, b, r, t, l, t]
354 });
355 if g.ch == ' ' && (q[2] - q[0]).hypot(q[3] - q[1]) < 0.5 {
362 continue;
363 }
364 if let Some(last) = cells.last_mut() {
374 let near =
375 |ax: f64, ay: f64, bx: f64, by: f64| (ax - bx).abs() < 0.5 && (ay - by).abs() < 0.5;
376 if near(last.rx0, last.ry0, q[0], q[1]) && near(last.rx1, last.ry1, q[2], q[3]) {
377 let offset = match g.quad {
385 None => (q[0] - last.rx0).abs(),
386 Some(_) => (q[0] - last.rx0).hypot(q[1] - last.ry0),
387 };
388 if euclidean && offset > 0.1 && last.text.ends_with(g.ch) {
389 continue;
390 }
391 last.text.push(g.ch);
392 last.ltr = !is_right_to_left(&last.text);
393 last.blank = last.blank && g.ch.is_whitespace();
394 last.nchars += 1;
395 last.fb = last.fb || (0xFB00..=0xFB06).contains(&(g.ch as u32));
397 last.lig = is_ligature(&last.text);
398 continue;
399 }
400 }
401 let text = g.ch.to_string();
402 let ltr = !is_right_to_left(&text);
403 let blank = g.ch.is_whitespace();
404 let lig = is_ligature(&text);
405 let fb = (0xFB00..=0xFB06).contains(&(g.ch as u32));
406 cells.push(Cell {
407 text,
408 rx0: q[0],
409 ry0: q[1],
410 rx1: q[2],
411 ry1: q[3],
412 rx2: q[4],
413 ry2: q[5],
414 rx3: q[6],
415 ry3: q[7],
416 ltr,
417 active: true,
418 lig_carry: false,
419 font: g.font,
420 blank,
421 lig,
422 fb,
423 nchars: 1,
424 b_l: (g.ll as f64).min(g.lr as f64),
425 b_r: (g.ll as f64).max(g.lr as f64),
426 b_b: (g.lb as f64).min(g.lt as f64),
427 b_t: (g.lb as f64).max(g.lt as f64),
428 pen: g.pen.map(|p| p.map(f64::from)),
429 math_font: g.math_font,
430 });
431 }
432 cells
433}
434
435pub(crate) fn line_cells(glyphs: &[Glyph], page_h: f32, euclidean: bool) -> Vec<TextCell> {
438 line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::from_env()).0
439}
440
441pub(crate) fn word_cells(glyphs: &[Glyph], page_h: f32, euclidean: bool) -> Vec<TextCell> {
449 line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::from_env()).1
450}
451
452#[cfg(test)]
459pub(crate) fn line_and_word_cells(
460 glyphs: &[Glyph],
461 page_h: f32,
462 euclidean: bool,
463) -> (Vec<TextCell>, Vec<TextCell>) {
464 line_and_word_cells_with(glyphs, page_h, euclidean, WordGap::Legacy)
465}
466
467pub(crate) fn line_and_word_cells_with(
470 glyphs: &[Glyph],
471 page_h: f32,
472 euclidean: bool,
473 gap: WordGap,
474) -> (Vec<TextCell>, Vec<TextCell>) {
475 let built = build_cells(glyphs, euclidean);
476 if gap != WordGap::Legacy {
477 return contract_runs(&built, gap, page_h);
478 }
479 let to_text_cell = |c: Cell| {
480 let l = c.rx0.min(c.rx1).min(c.rx2).min(c.rx3) as f32;
481 let r = c.rx0.max(c.rx1).max(c.rx2).max(c.rx3) as f32;
482 let top = c.ry0.max(c.ry1).max(c.ry2).max(c.ry3) as f32;
483 let bot = c.ry0.min(c.ry1).min(c.ry2).min(c.ry3) as f32;
484 TextCell {
485 text: c.text,
486 l,
487 t: page_h - top,
488 r,
489 b: page_h - bot,
490 }
491 };
492 let mut word_run: Vec<Cell> = built.clone();
501 let mut cells = built;
502 contract(&mut cells, euclidean, LINE_FACTORS);
503 let lines = to_text_cells(cells, to_text_cell);
504 contract(&mut word_run, euclidean, WORD_FACTORS);
505 word_run.retain(|c| !c.text.trim().is_empty());
506 let words = to_text_cells(word_run, to_text_cell);
507 (lines, words)
508}
509
510fn to_text_cells(cells: Vec<Cell>, f: impl Fn(Cell) -> TextCell) -> Vec<TextCell> {
520 let mut out = Vec::with_capacity(cells.len());
521 out.extend(cells.into_iter().map(f));
522 out
523}
524
525fn is_rtl_char(c: char) -> bool {
526 let ch = c as u32;
527 (0x0600..=0x06FF).contains(&ch)
528 || (0x0750..=0x077F).contains(&ch)
529 || (0x08A0..=0x08FF).contains(&ch)
530 || (0xFB50..=0xFDFF).contains(&ch)
531 || (0xFE70..=0xFEFF).contains(&ch)
532 || (0x0590..=0x05FF).contains(&ch)
533 || (0xFB1D..=0xFB4F).contains(&ch)
534 || (0x0700..=0x074F).contains(&ch)
535 || (0x0780..=0x07BF).contains(&ch)
536 || (0x07C0..=0x07FF).contains(&ch)
537}
538
539fn is_right_to_left(s: &str) -> bool {
541 !s.is_empty() && s.chars().all(is_rtl_char)
542}
543
544fn is_punct_or_space(s: &str) -> bool {
546 let mut chars = s.chars();
547 let (Some(c), None) = (chars.next(), chars.next()) else {
548 return false;
549 };
550 if matches!(
551 c,
552 ' ' | '\t'
553 | '\n'
554 | '\r'
555 | '\u{0c}'
556 | '\u{0b}'
557 | '.'
558 | ','
559 | ';'
560 | ':'
561 | '!'
562 | '?'
563 | '('
564 | ')'
565 | '['
566 | ']'
567 | '{'
568 | '}'
569 | '\''
570 | '"'
571 | '`'
572 | '\u{2018}'
573 | '\u{2019}'
574 | '\u{201c}'
575 | '\u{201d}'
576 | '-'
577 | '\u{2013}'
578 | '\u{2014}'
579 | '_'
580 | '/'
581 | '\\'
582 | '|'
583 | '@'
584 | '#'
585 | '%'
586 | '&'
587 | '*'
588 | '+'
589 | '='
590 | '<'
591 | '>'
592 ) {
593 return true;
594 }
595 let ch = c as u32;
596 (0x2000..=0x206F).contains(&ch)
597 || (0x3000..=0x303F).contains(&ch)
598 || (0xFE50..=0xFE6F).contains(&ch)
599 || (0xFF00..=0xFF0F).contains(&ch)
600 || (0xFF1A..=0xFF1F).contains(&ch)
601 || (0xFF3B..=0xFF5E).contains(&ch)
602}
603
604fn is_ligature(s: &str) -> bool {
606 matches!(s, "ff" | "fi" | "fl" | "ffi" | "ffl")
607 || s.chars().any(|c| (0xFB00..=0xFB06).contains(&(c as u32)))
608}
609
610#[derive(Clone, Copy, Debug, Default, PartialEq)]
633pub enum WordGap {
634 Legacy,
636 Factor(f64),
638 #[default]
642 Adaptive,
643}
644
645impl WordGap {
646 pub const ACCEPTED: &'static str = "legacy, adaptive, or a factor in (0, 4]";
648
649 pub fn parse(s: &str) -> Result<Self, String> {
652 let t = s.trim().to_ascii_lowercase();
653 match t.as_str() {
654 "legacy" => Ok(WordGap::Legacy),
655 "adaptive" | "auto" | "default" => Ok(WordGap::Adaptive),
656 _ => match t.parse::<f64>() {
657 Ok(f) if f.is_finite() && f > 0.0 && f <= 4.0 => Ok(WordGap::Factor(f)),
658 _ => Err(format!(
659 "pdf_word_gap must be {}, got {s:?}",
660 WordGap::ACCEPTED
661 )),
662 },
663 }
664 }
665
666 pub fn from_env() -> Self {
670 let Some(v) = docling_core::env::nonempty("DOCLING_RS_PDF_WORD_GAP") else {
671 return WordGap::default();
672 };
673 WordGap::parse(&v).unwrap_or_else(|e| {
674 static WARNED: std::sync::Once = std::sync::Once::new();
675 WARNED.call_once(|| {
676 eprintln!("docling-pdf: DOCLING_RS_PDF_WORD_GAP: {e}; using adaptive")
677 });
678 WordGap::default()
679 })
680 }
681}
682
683struct RunCell<'a> {
685 cell: &'a Cell,
686 ux: f64,
688 uy: f64,
689 advance: f64,
691 height: f64,
692 space: bool,
693}
694
695impl<'a> RunCell<'a> {
696 fn new(cell: &'a Cell) -> Self {
697 let (dx, dy) = (cell.rx1 - cell.rx0, cell.ry1 - cell.ry0);
698 let advance = dx.hypot(dy);
699 let (ux, uy) = if advance > 1e-9 {
700 (dx / advance, dy / advance)
701 } else {
702 (1.0, 0.0)
703 };
704 let h0 = (cell.rx3 - cell.rx0).hypot(cell.ry3 - cell.ry0);
705 let h1 = (cell.rx2 - cell.rx1).hypot(cell.ry2 - cell.ry1);
706 RunCell {
707 cell,
708 ux,
709 uy,
710 advance,
711 height: 0.5 * (h0 + h1),
712 space: cell.blank,
713 }
714 }
715
716 fn scale(&self) -> f64 {
719 if self.advance > 1e-6 {
720 self.advance
721 } else {
722 (0.5 * self.height).max(1e-6)
723 }
724 }
725}
726
727fn forward_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
736 let (l, r) = (lhs.cell, rhs.cell);
737 let (tx, ty) = (0.5 * (l.rx1 + l.rx2), 0.5 * (l.ry1 + l.ry2));
738 let (hx, hy) = (0.5 * (r.rx0 + r.rx3), 0.5 * (r.ry0 + r.ry3));
739 (hx - tx) * lhs.ux + (hy - ty) * lhs.uy
740}
741
742fn facing_edge_overlap(lhs: &RunCell, rhs: &RunCell) -> f64 {
745 let (l, r) = (lhs.cell, rhs.cell);
746 let (ux, uy) = if l.ltr {
747 (lhs.ux, lhs.uy)
748 } else {
749 (-lhs.ux, -lhs.uy)
750 };
751 let (nx, ny) = (-uy, ux);
752 let proj = |x: f64, y: f64| x * nx + y * ny;
753 let (a0, a1) = if l.ltr {
754 (proj(l.rx1, l.ry1), proj(l.rx2, l.ry2))
755 } else {
756 (proj(l.rx0, l.ry0), proj(l.rx3, l.ry3))
757 };
758 let (b0, b1) = if l.ltr {
759 (proj(r.rx0, r.ry0), proj(r.rx3, r.ry3))
760 } else {
761 (proj(r.rx1, r.ry1), proj(r.rx2, r.ry2))
762 };
763 a0.max(a1).min(b0.max(b1)) - a0.min(a1).max(b0.min(b1))
764}
765
766fn is_math_glyph(text: &str) -> bool {
770 const MATH: &str = "∑∏∫√∞∈∉≠≤≥⊂⊃⊆⊇⊥∪∩⎛⎜⎝⎞⎟⎠⎡⎢⎣⎤⎥⎦";
771 text.chars().any(|c| MATH.contains(c))
772}
773
774fn is_local_attachment(lhs: &RunCell, rhs: &RunCell) -> bool {
777 let scale = lhs.scale().max(rhs.scale());
778 if forward_gap(lhs, rhs) > 0.10 * scale {
779 return false;
780 }
781 let (off, (lh, rh)) = baseline_offset(lhs, rhs);
782 let math = |c: &RunCell| c.cell.math_font || is_math_glyph(&c.cell.text);
783 off <= 2.0 * lh.max(rh).max(1e-6) && (math(lhs) || math(rhs))
784}
785
786fn baseline_offset(lhs: &RunCell, rhs: &RunCell) -> (f64, (f64, f64)) {
794 let (nx, ny) = (-lhs.uy, lhs.ux);
795 match (lhs.cell.pen, rhs.cell.pen) {
796 (Some(a), Some(b)) => (
797 ((b[0] - a[0]) * nx + (b[1] - a[1]) * ny).abs(),
798 (a[2], b[2]),
799 ),
800 _ => (
801 ((rhs.cell.rx0 - lhs.cell.rx0) * nx + (rhs.cell.ry0 - lhs.cell.ry0) * ny).abs(),
802 (lhs.height, rhs.height),
803 ),
804 }
805}
806
807fn continues_line(lhs: &RunCell, rhs: &RunCell) -> bool {
811 if lhs.ux * rhs.ux + lhs.uy * rhs.uy < 0.985 {
812 return false;
813 }
814 let scale = lhs.scale().max(rhs.scale());
815 let gap = forward_gap(lhs, rhs);
816 if facing_edge_overlap(lhs, rhs) <= 1e-6 && !is_local_attachment(lhs, rhs) {
817 return false;
818 }
819 -scale <= gap && gap <= 4.0 * scale
820}
821
822fn baselines_compatible(lhs: &RunCell, rhs: &RunCell) -> bool {
826 let (off, (lh, rh)) = baseline_offset(lhs, rhs);
827 off <= 0.35 * lh.min(rh).max(1e-6) || is_local_attachment(lhs, rhs)
828}
829
830fn normalized_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
832 forward_gap(lhs, rhs).max(0.0) / (0.5 * (lhs.scale() + rhs.scale())).max(1e-6)
833}
834
835#[derive(Clone, Copy, PartialEq)]
837enum TrackClass {
838 Letter,
840 Dot,
842 Other,
843}
844
845fn track_class(text: &str) -> TrackClass {
846 if matches!(text, "." | "·" | "…") {
847 TrackClass::Dot
848 } else if !text.is_empty() && text.chars().all(char::is_alphanumeric) {
849 TrackClass::Letter
850 } else {
851 TrackClass::Other
852 }
853}
854
855fn tracking_tolerance(gap: f64) -> f64 {
859 (0.08 * gap).max(0.25)
860}
861
862fn tracked_gaps(run: &[RunCell]) -> Vec<bool> {
886 struct Gap {
887 left: usize,
888 right: usize,
889 pt: f64,
890 n: f64,
891 left_class: TrackClass,
892 right_class: TrackClass,
893 }
894 let mut gaps: Vec<Gap> = Vec::new();
895 let mut prev: Option<usize> = None;
896 let mut crossed_space = false;
897 for (i, c) in run.iter().enumerate() {
898 if c.space {
899 crossed_space = true;
900 continue;
901 }
902 if let (Some(p), false) = (prev, crossed_space) {
903 gaps.push(Gap {
904 left: p,
905 right: i,
906 pt: forward_gap(&run[p], c),
907 n: normalized_gap(&run[p], c),
908 left_class: track_class(&run[p].cell.text),
909 right_class: track_class(&c.cell.text),
910 });
911 }
912 prev = Some(i);
913 crossed_space = false;
914 }
915 let joined = |k: usize| gaps[k + 1].left == gaps[k].right;
917 let stretch = |k: usize, fits: &dyn Fn(&Gap) -> bool| {
919 let mut end = k;
920 while end < gaps.len() && fits(&gaps[end]) && (end == k || joined(end - 1)) {
921 end += 1;
922 }
923 end
924 };
925 let flanks_open = |k: usize, end: usize, floor: f64| {
927 let before = k > 0 && joined(k - 1) && gaps[k - 1].pt < floor;
928 let after = end < gaps.len() && joined(end - 1) && gaps[end].pt < floor;
929 !before && !after
930 };
931
932 let mut tracked = vec![false; run.len()];
933 let mut leader = vec![false; run.len()];
934 let mut letter_tracking: Vec<f64> = Vec::new();
935 let mut k = 0;
936 while k < gaps.len() {
937 let dots = |g: &Gap| {
938 g.left_class == TrackClass::Dot && g.right_class == TrackClass::Dot && g.n <= 1.0
939 };
940 let end = stretch(k, &dots);
941 if end - k >= 3 {
942 for g in &gaps[k..end] {
943 tracked[g.right] = true;
944 leader[g.left] = true;
945 leader[g.right] = true;
946 }
947 k = end;
948 continue;
949 }
950 let first = &gaps[k];
951 let letters = |g: &Gap| {
952 g.left_class == TrackClass::Letter
953 && g.right_class == TrackClass::Letter
954 && (0.1..=1.0).contains(&g.n)
955 };
956 if !letters(first) {
957 k += 1;
958 continue;
959 }
960 let (mut lo, mut hi) = (first.pt, first.pt);
961 let mut end = k + 1;
962 while end < gaps.len()
963 && joined(end - 1)
964 && letters(&gaps[end])
965 && hi.max(gaps[end].pt) - lo.min(gaps[end].pt) <= tracking_tolerance(lo)
966 {
967 lo = lo.min(gaps[end].pt);
968 hi = hi.max(gaps[end].pt);
969 end += 1;
970 }
971 let one_char = gaps[k..end]
974 .iter()
975 .all(|g| run[g.right].cell.text == run[first.left].cell.text);
976 if end - k >= 3 && !one_char && flanks_open(k, end, lo - tracking_tolerance(lo)) {
977 for g in &gaps[k..end] {
978 tracked[g.right] = true;
979 }
980 letter_tracking.push(0.5 * (lo + hi));
981 k = end;
982 } else {
983 k += 1;
984 }
985 }
986
987 for &t in &letter_tracking {
988 let tol = tracking_tolerance(t);
989 let same = |g: &Gap| {
990 (g.left_class == TrackClass::Letter || g.right_class == TrackClass::Letter)
991 && g.left_class != TrackClass::Dot
992 && g.right_class != TrackClass::Dot
993 && g.n <= 1.0
994 && (g.pt - t).abs() <= tol
995 };
996 let mut k = 0;
997 while k < gaps.len() {
998 let end = stretch(k, &same);
999 if end == k {
1000 k += 1;
1001 continue;
1002 }
1003 if flanks_open(k, end, t - tol) && !gaps[k..end].iter().any(|g| leader[g.left]) {
1004 for g in &gaps[k..end] {
1005 tracked[g.right] = true;
1006 }
1007 }
1008 k = end;
1009 }
1010 }
1011 tracked
1012}
1013
1014const GAP_CLUSTER_CLIP: f64 = 0.5;
1024
1025fn infer_word_gap(run: &[RunCell], tracked: &[bool]) -> f64 {
1033 let mut gaps = Vec::new();
1034 let mut prev: Option<&RunCell> = None;
1035 let mut crossed_space = false;
1036 for (i, c) in run.iter().enumerate() {
1037 if c.space {
1038 crossed_space = true;
1039 continue;
1040 }
1041 if let (Some(p), false, false) = (prev, crossed_space, tracked[i]) {
1042 gaps.push(normalized_gap(p, c).min(GAP_CLUSTER_CLIP));
1043 }
1044 prev = Some(c);
1045 crossed_space = false;
1046 }
1047 if gaps.len() < 2 {
1048 return 0.25;
1049 }
1050 let mut low = gaps.iter().copied().fold(f64::INFINITY, f64::min);
1051 let mut high = gaps.iter().copied().fold(f64::NEG_INFINITY, f64::max);
1052 if high < 0.18 || high - low < 0.08 {
1053 return 0.25;
1054 }
1055 for _ in 0..8 {
1056 let mid = 0.5 * (low + high);
1057 let (mut ls, mut ln, mut hs, mut hn) = (0.0, 0usize, 0.0, 0usize);
1058 for &g in &gaps {
1059 if g <= mid {
1060 ls += g;
1061 ln += 1;
1062 } else {
1063 hs += g;
1064 hn += 1;
1065 }
1066 }
1067 if ln == 0 || hn == 0 {
1068 return 0.25;
1069 }
1070 low = ls / ln as f64;
1071 high = hs / hn as f64;
1072 }
1073 if high < 0.18 || high - low < 0.08 {
1074 return 0.25;
1075 }
1076 (0.5 * (low + high)).max(0.18)
1077}
1078
1079struct Agg {
1081 text: String,
1082 ltr: bool,
1083 q: [f64; 8],
1084 glued: bool,
1091}
1092
1093impl Agg {
1094 fn of(c: &Cell, glued: bool) -> Self {
1095 Agg {
1096 text: c.text.clone(),
1097 ltr: c.ltr,
1098 q: [c.rx0, c.ry0, c.rx1, c.ry1, c.rx2, c.ry2, c.rx3, c.ry3],
1099 glued,
1100 }
1101 }
1102
1103 fn append(&mut self, text: &str, ltr: bool, q: &[f64; 8], space: bool) {
1107 if self.ltr && ltr {
1108 if space {
1109 self.text.push(' ');
1110 }
1111 self.text.push_str(text);
1112 } else {
1113 let sep = if space { " " } else { "" };
1114 self.text = format!("{text}{sep}{}", self.text);
1115 self.ltr = false;
1116 }
1117 let (mut ux, mut uy) = (self.q[2] - self.q[0], self.q[3] - self.q[1]);
1118 if ux.hypot(uy) <= 1e-9 {
1119 (ux, uy) = (q[2] - q[0], q[3] - q[1]);
1120 }
1121 let n = ux.hypot(uy);
1122 if n <= 1e-9 {
1123 return;
1124 }
1125 let (ux, uy) = (ux / n, uy / n);
1126 let (nx, ny) = (-uy, ux);
1127 let (mut u0, mut u1, mut n0, mut n1) = (
1128 f64::INFINITY,
1129 f64::NEG_INFINITY,
1130 f64::INFINITY,
1131 f64::NEG_INFINITY,
1132 );
1133 for k in 0..4 {
1134 for (x, y) in [(self.q[2 * k], self.q[2 * k + 1]), (q[2 * k], q[2 * k + 1])] {
1135 let (u, v) = (x * ux + y * uy, x * nx + y * ny);
1136 u0 = u0.min(u);
1137 u1 = u1.max(u);
1138 n0 = n0.min(v);
1139 n1 = n1.max(v);
1140 }
1141 }
1142 let pt = |u: f64, v: f64| (u * ux + v * nx, u * uy + v * ny);
1143 let (a, b, c, d) = (pt(u0, n0), pt(u1, n0), pt(u1, n1), pt(u0, n1));
1144 self.q = [a.0, a.1, b.0, b.1, c.0, c.1, d.0, d.1];
1145 }
1146
1147 fn into_cell(self, page_h: f32) -> TextCell {
1148 let xs = [self.q[0], self.q[2], self.q[4], self.q[6]];
1149 let ys = [self.q[1], self.q[3], self.q[5], self.q[7]];
1150 let (l, r) = (
1151 xs.iter().copied().fold(f64::INFINITY, f64::min),
1152 xs.iter().copied().fold(f64::NEG_INFINITY, f64::max),
1153 );
1154 let (b, t) = (
1155 ys.iter().copied().fold(f64::INFINITY, f64::min),
1156 ys.iter().copied().fold(f64::NEG_INFINITY, f64::max),
1157 );
1158 TextCell {
1159 text: self.text,
1160 l: l as f32,
1161 t: page_h - t as f32,
1162 r: r as f32,
1163 b: page_h - b as f32,
1164 }
1165 }
1166}
1167
1168fn page_draws_spaces(runs: &[Vec<RunCell>]) -> bool {
1175 let long = |r: &&Vec<RunCell>| r.iter().filter(|c| !c.space).count() >= 8;
1176 let lines = runs.iter().filter(long).count();
1177 let spaced = runs
1178 .iter()
1179 .filter(long)
1180 .filter(|r| r.iter().any(|c| c.space))
1181 .count();
1182 lines > 0 && 2 * spaced >= lines
1183}
1184
1185fn spaces_drawn_apart(run: &[RunCell], spaces: &[(f64, &Cell)]) -> bool {
1194 let mut visible = run.iter().filter(|c| !c.space);
1195 let Some(first) = visible.next() else {
1196 return false;
1197 };
1198 let (mut l, mut r, mut b, mut t) = bounds(first.cell);
1200 for c in visible.clone() {
1201 let (cl, cr, cb, ct) = bounds(c.cell);
1202 (l, r, b, t) = (l.min(cl), r.max(cr), b.min(cb), t.max(ct));
1203 }
1204 let (lo, hi) = (
1205 spaces.partition_point(|&(y, _)| y < b),
1206 spaces.partition_point(|&(y, _)| y <= t),
1207 );
1208 let inside: Vec<&Cell> = spaces[lo..hi]
1209 .iter()
1210 .map(|&(_, c)| c)
1211 .filter(|c| (l..=r).contains(&(0.5 * (c.b_l + c.b_r))))
1212 .collect();
1213 if inside.is_empty() {
1214 return false;
1215 }
1216 let (ux, uy) = (first.ux, first.uy);
1217 let along = |x: f64, y: f64| x * ux + y * uy;
1218 let across = |c: &Cell| {
1219 let v = [
1220 c.rx0 * -uy + c.ry0 * ux,
1221 c.rx1 * -uy + c.ry1 * ux,
1222 c.rx2 * -uy + c.ry2 * ux,
1223 c.rx3 * -uy + c.ry3 * ux,
1224 ];
1225 let lo = v.iter().copied().fold(f64::INFINITY, f64::min);
1226 let hi = v.iter().copied().fold(f64::NEG_INFINITY, f64::max);
1227 (lo, hi)
1228 };
1229 let mut gaps = Vec::new();
1233 let mut prev = first;
1234 for c in visible {
1235 let (lhs, rhs) = (prev.cell, c.cell);
1236 let tail = along(0.5 * (lhs.rx1 + lhs.rx2), 0.5 * (lhs.ry1 + lhs.ry2));
1237 let head = along(0.5 * (rhs.rx0 + rhs.rx3), 0.5 * (rhs.ry0 + rhs.ry3));
1238 if head > tail {
1239 let ((l0, l1), (r0, r1)) = (across(lhs), across(rhs));
1240 gaps.push((tail, head, (l0.min(r0), l1.max(r1))));
1241 }
1242 prev = c;
1243 }
1244 inside.iter().any(|c| {
1245 let mid = along(0.5 * (c.rx0 + c.rx2), 0.5 * (c.ry0 + c.ry2));
1246 let (s0, s1) = across(c);
1247 gaps.iter().any(|&(tail, head, (b0, b1))| {
1248 tail <= mid && mid <= head && s1.min(b1) - s0.max(b0) > 0.5 * (s1 - s0)
1249 })
1250 })
1251}
1252
1253fn contract_runs(cells: &[Cell], gap: WordGap, page_h: f32) -> (Vec<TextCell>, Vec<TextCell>) {
1257 let mut runs: Vec<Vec<RunCell>> = Vec::new();
1260 for c in cells.iter().filter(|c| !c.text.is_empty()) {
1261 let rc = RunCell::new(c);
1262 if rc.space {
1263 match runs.last_mut() {
1264 Some(run) => run.push(rc),
1265 None => runs.push(vec![rc]),
1266 }
1267 continue;
1268 }
1269 let starts = match runs.last().and_then(|r| r.iter().rev().find(|c| !c.space)) {
1270 Some(prev) => !continues_line(prev, &rc),
1271 None => runs.is_empty(),
1272 };
1273 if starts {
1274 runs.push(Vec::new());
1275 }
1276 runs.last_mut().expect("a run is open").push(rc);
1277 }
1278
1279 let (mut words_out, mut lines_out) = (Vec::new(), Vec::new());
1280 let page_spaced = page_draws_spaces(&runs);
1281 let mut spaces: Vec<(f64, &Cell)> = Vec::new();
1282 if page_spaced {
1283 spaces.extend(
1284 runs.iter()
1285 .flatten()
1286 .filter(|c| c.space)
1287 .map(|c| (0.5 * (c.cell.b_b + c.cell.b_t), c.cell)),
1288 );
1289 spaces.sort_by(|a, b| a.0.total_cmp(&b.0));
1290 }
1291 for run in &runs {
1292 let has_spaces =
1302 run.iter().any(|c| c.space) || (page_spaced && !spaces_drawn_apart(run, &spaces));
1303 let tracked = tracked_gaps(run);
1304 let threshold = match gap {
1311 WordGap::Factor(f) if has_spaces => f.max(0.35),
1312 WordGap::Factor(f) => f,
1313 _ => (if has_spaces {
1314 1.0
1315 } else {
1316 infer_word_gap(run, &tracked)
1317 })
1318 .min(0.35),
1319 };
1320 let mut words: Vec<Agg> = Vec::new();
1321 let mut prev: Option<&RunCell> = None;
1322 let mut boundary = false;
1323 for (i, c) in run.iter().enumerate() {
1324 if c.space {
1325 boundary = true;
1326 continue;
1327 }
1328 let mut starts = words.is_empty() || boundary;
1329 let mut glued = false;
1330 if !starts
1333 && c.cell.text == "."
1334 && i + 4 < run.len()
1335 && run[i + 1].space
1336 && run[i + 2].cell.text == "."
1337 && run[i + 3].space
1338 && run[i + 4].cell.text == "."
1339 && prev.is_some_and(|p| p.cell.text != ".")
1340 {
1341 starts = true;
1342 }
1343 if let (false, Some(p)) = (starts, prev) {
1344 let shifted = !baselines_compatible(p, c);
1345 let gapped = !tracked[i] && normalized_gap(p, c) > threshold;
1346 starts = shifted || gapped;
1347 let opens = |s: &str| matches!(s.chars().last(), Some('(' | '[' | '{'));
1359 let closes = |s: &str| matches!(s.chars().next(), Some(')' | ']' | '}'));
1360 glued = shifted
1361 && !gapped
1362 && (words.last().is_some_and(|w| opens(&w.text)) || closes(&c.cell.text));
1363 }
1364 if starts {
1365 words.push(Agg::of(c.cell, glued));
1366 } else {
1367 let q = [
1368 c.cell.rx0, c.cell.ry0, c.cell.rx1, c.cell.ry1, c.cell.rx2, c.cell.ry2,
1369 c.cell.rx3, c.cell.ry3,
1370 ];
1371 words.last_mut().expect("a word is open").append(
1372 &c.cell.text,
1373 c.cell.ltr,
1374 &q,
1375 false,
1376 );
1377 }
1378 prev = Some(c);
1379 boundary = false;
1380 }
1381 let mut it = words.into_iter();
1382 let Some(first) = it.next() else {
1383 continue;
1384 };
1385 let mut line = Agg {
1386 text: first.text.clone(),
1387 ltr: first.ltr,
1388 q: first.q,
1389 glued: false,
1390 };
1391 words_out.push(first.into_cell(page_h));
1392 for w in it {
1393 line.append(&w.text, w.ltr, &w.q, !w.glued);
1394 words_out.push(w.into_cell(page_h));
1395 }
1396 lines_out.push(line.into_cell(page_h));
1397 }
1398 (lines_out, words_out)
1399}
1400
1401#[cfg(test)]
1402mod tests {
1403 use super::*;
1404
1405 fn glyph(ch: char, l: f32, r: f32) -> Glyph {
1406 Glyph {
1407 ch,
1408 l,
1409 b: 100.0,
1410 r,
1411 t: 110.0,
1412 ll: l,
1413 lb: 98.0,
1414 lr: r,
1415 lt: 110.0,
1416 font: 0,
1417 quad: None,
1418 pen: None,
1419 math_font: false,
1420 invisible: false,
1421 }
1422 }
1423
1424 #[test]
1429 fn space_glyph_separates_tight_words() {
1430 let glyphs = [
1431 glyph('M', 137.66, 143.74),
1432 glyph('O', 143.74, 149.82),
1433 glyph('D', 149.82, 155.90),
1434 glyph('E', 155.90, 161.98),
1435 glyph(' ', 161.84, 164.09),
1436 glyph('t', 163.82, 166.60),
1437 glyph('o', 166.60, 171.60),
1438 ];
1439 let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1440 let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1441 assert_eq!(words, ["MODE", "to"]);
1442 assert_eq!(lines.len(), 1);
1443 assert_eq!(lines[0].text, "MODE to");
1444 }
1445
1446 #[test]
1451 fn stacked_glyphs_at_one_x_stay_separate_cells() {
1452 let at = |ch: char, b: f32| Glyph {
1453 lb: b,
1454 lt: b + 10.0,
1455 b,
1456 t: b + 10.0,
1457 ..glyph(ch, 98.0, 103.0)
1458 };
1459 let ticks: Vec<Glyph> = "345678"
1460 .chars()
1461 .enumerate()
1462 .map(|(k, ch)| at(ch, 316.0 + 25.92 * k as f32))
1463 .collect();
1464 let lines = line_cells(&ticks, 792.0, true);
1465 let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1466 assert_eq!(texts, ["3", "4", "5", "6", "7", "8"]);
1467 assert!(lines.windows(2).all(|w| w[0].t > w[1].t));
1468
1469 let lig = [glyph('f', 10.0, 16.0), glyph('i', 10.0, 16.0)];
1470 let lines = line_cells(&lig, 792.0, true);
1471 assert_eq!(lines.len(), 1);
1472 assert_eq!(lines[0].text, "fi");
1473 }
1474
1475 #[test]
1480 fn cells_do_not_keep_the_glyph_buffer() {
1481 let glyphs: Vec<Glyph> = (0..400)
1483 .map(|i| {
1484 let x = (i % 40) as f32 * 6.0;
1485 let ch = if i % 4 == 3 { ' ' } else { '7' };
1486 let mut g = glyph(ch, x, x + 6.0);
1487 let row = (i / 40) as f32 * 14.0;
1488 (g.b, g.t, g.lb, g.lt) = (100.0 + row, 110.0 + row, 98.0 + row, 110.0 + row);
1489 g
1490 })
1491 .collect();
1492 let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1493 assert_eq!((lines.len(), words.len()), (10, 100));
1494 assert_eq!(lines.capacity(), lines.len());
1495 assert_eq!(words.capacity(), words.len());
1496 }
1497
1498 fn und_dem_line() -> Vec<Glyph> {
1502 let at = |ch: char, l: f32, r: f32, font: u64| Glyph {
1503 ch,
1504 l,
1505 b: 682.056,
1506 r,
1507 t: 691.05,
1508 ll: l,
1509 lb: 682.056,
1510 lr: r,
1511 lt: 691.05,
1512 font,
1513 quad: None,
1514 pen: None,
1515 math_font: false,
1516 invisible: false,
1517 };
1518 let mut g = Vec::new();
1519 let mut run = |text: &str, edges: &[f32], font: u64| {
1520 for (i, ch) in text.chars().enumerate() {
1521 g.push(at(ch, edges[i], edges[i + 1], font));
1522 }
1523 };
1524 run(
1525 "schaft",
1526 &[
1527 328.976, 333.216, 338.572, 344.325, 350.486, 353.920, 357.248,
1528 ],
1529 1,
1530 );
1531 run("und", &[359.261, 365.121, 370.875, 377.035], 2);
1532 run("dem", &[378.990, 385.151, 390.701, 399.287], 2);
1533 run("Öst", &[401.214, 409.092, 413.332, 416.660], 1);
1534 g
1535 }
1536
1537 #[test]
1538 fn legacy_rule_keeps_the_borderline_und_dem_glued() {
1539 let (lines, words) = line_and_word_cells(&und_dem_line(), 792.0, true);
1543 assert!(lines.iter().any(|c| c.text == "unddem"), "{lines:?}");
1544 assert!(words.iter().any(|c| c.text == "unddem"), "{words:?}");
1545 }
1546
1547 #[test]
1548 fn line_local_word_gaps_split_und_dem() {
1549 for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1550 let (lines, words) = line_and_word_cells_with(&und_dem_line(), 792.0, true, gap);
1551 let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1552 assert_eq!(texts, ["schaft und dem Öst"], "{gap:?}");
1553 let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1554 assert_eq!(texts, ["schaft", "und", "dem", "Öst"], "{gap:?}");
1555 assert!((words[1].l - 359.261).abs() < 1e-3 && (words[1].r - 377.035).abs() < 1e-3);
1557 }
1558 let (lines, _) =
1560 line_and_word_cells_with(&und_dem_line(), 792.0, true, WordGap::Factor(0.5));
1561 assert_eq!(lines[0].text, "schaftunddemÖst");
1562 }
1563
1564 #[test]
1565 fn a_superscript_attaches_by_pen_origin_and_math_face() {
1566 let at = |ch: char, l: f32, y: f32, size: f32, math: bool, pen: bool| Glyph {
1570 lb: y - 0.2 * size,
1571 lt: y + 0.8 * size,
1572 b: y - 0.2 * size,
1573 t: y + 0.8 * size,
1574 pen: pen.then_some([l, y, size]),
1575 math_font: math,
1576 ..glyph(ch, l, l + 0.5 * size)
1577 };
1578 let line = |rise: f32, math: bool, pen: bool| {
1579 let mut g: Vec<Glyph> = "Lysak"
1580 .chars()
1581 .enumerate()
1582 .map(|(k, ch)| at(ch, 100.0 + 5.0 * k as f32, 600.0, 10.0, math, pen))
1583 .collect();
1584 g.extend(
1585 "[0000"
1586 .chars()
1587 .enumerate()
1588 .map(|(k, ch)| at(ch, 125.0 + 3.5 * k as f32, 600.0 + rise, 7.0, math, pen)),
1589 );
1590 let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1591 (
1592 lines[0].text.clone(),
1593 words.iter().map(|w| w.text.clone()).collect::<Vec<_>>(),
1594 )
1595 };
1596 let one = |s: &str| (s.to_string(), vec![s.to_string()]);
1597 let two = |s: &str| {
1598 (
1599 s.to_string(),
1600 vec!["Lysak".to_string(), "[0000".to_string()],
1601 )
1602 };
1603 assert_eq!(line(3.6, true, true), one("Lysak[0000"));
1609 assert_eq!(line(3.6, false, true), two("Lysak [0000"));
1610 assert_eq!(line(2.0, false, true), one("Lysak[0000"));
1613 assert_eq!(line(2.0, false, false), two("Lysak [0000"));
1614 }
1615
1616 #[test]
1623 fn a_touching_superscript_joins_the_line_text_inside_brackets_only() {
1624 let at = |ch: char, l: f32, w: f32, y: f32, size: f32| Glyph {
1625 lb: y - 0.2 * size,
1626 lt: y + 0.8 * size,
1627 b: y - 0.2 * size,
1628 t: y + 0.8 * size,
1629 pen: Some([l, y, size]),
1630 ..glyph(ch, l, l + w)
1631 };
1632 let g = [
1633 at('E', 100.0, 6.0, 600.0, 10.5),
1634 at('G', 106.0, 6.9, 600.0, 10.5),
1635 at('(', 115.3, 3.2, 600.0, 10.5),
1636 at('1', 118.5, 3.1, 603.5, 6.8),
1637 at(')', 121.6, 3.2, 600.0, 10.5),
1638 at('e', 127.2, 5.0, 600.0, 10.5),
1639 ];
1640 let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1641 assert_eq!(lines[0].text, "EG (1) e");
1642 let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1643 assert_eq!(words, ["EG", "(", "1", ")", "e"]);
1644 let g = [
1646 at('E', 100.0, 6.0, 600.0, 10.5),
1647 at('G', 106.0, 6.9, 600.0, 10.5),
1648 at('1', 112.9, 3.1, 603.5, 6.8),
1649 ];
1650 let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1651 assert_eq!(lines[0].text, "EG 1");
1652 }
1653
1654 #[test]
1655 fn a_factor_keeps_docling_parse_s_floor_on_lines_with_space_glyphs() {
1656 let mut g = Vec::new();
1661 let mut x = 100.0f32;
1662 let put = |g: &mut Vec<Glyph>, s: &str, x: &mut f32| {
1663 for ch in s.chars() {
1664 g.push(glyph(ch, *x, *x + 2.5));
1665 *x += 2.5;
1666 }
1667 };
1668 put(&mut g, "Die", &mut x);
1669 g.push(glyph(' ', x, x + 2.5));
1670 x += 2.5;
1671 put(&mut g, "Verpf", &mut x);
1672 x += 0.6;
1673 put(&mut g, "lichtungen", &mut x);
1674 let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Factor(0.2));
1675 assert_eq!(lines[0].text, "Die Verpflichtungen");
1676 let spaceless: Vec<Glyph> = g.into_iter().filter(|c| c.ch != ' ').collect();
1677 let (lines, _) = line_and_word_cells_with(&spaceless, 792.0, true, WordGap::Factor(0.2));
1678 assert_eq!(lines[0].text, "Die Verpf lichtungen");
1679 }
1680
1681 #[test]
1682 fn right_to_left_glyphs_in_visual_order_stay_one_line() {
1683 let mut g = Vec::new();
1688 let mut x = 100.0f32;
1689 for (k, word) in [
1690 "\u{0631}\u{0627}\u{0632}\u{0627}\u{0628}",
1691 "\u{0631}\u{062f}",
1692 ]
1693 .iter()
1694 .enumerate()
1695 {
1696 if k > 0 {
1697 x += 3.0;
1698 }
1699 for ch in word.chars() {
1700 g.push(glyph(ch, x, x + 5.0));
1701 x += 5.0;
1702 }
1703 }
1704 for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1705 let (lines, words) = line_and_word_cells_with(&g, 792.0, true, gap);
1706 assert_eq!(
1707 lines.len(),
1708 1,
1709 "{gap:?}: {:?}",
1710 lines.iter().map(|c| &c.text).collect::<Vec<_>>()
1711 );
1712 assert_eq!(words.len(), 2, "{gap:?}");
1713 }
1714 }
1715
1716 #[test]
1717 fn letter_spacing_stays_one_word_under_the_adaptive_rule() {
1718 let mut g = Vec::new();
1721 let mut x = 100.0f32;
1722 for (k, word) in ["Allgemeine", "Bestimmungen"].iter().enumerate() {
1723 if k > 0 {
1724 x += 6.0;
1725 }
1726 for ch in word.chars() {
1727 g.push(glyph(ch, x, x + 5.0));
1728 x += 5.0 + 1.5;
1729 }
1730 x -= 1.5;
1731 }
1732 let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1733 assert_eq!(lines[0].text, "Allgemeine Bestimmungen");
1734 }
1735
1736 fn set_line(pieces: &[(&str, f32)], y: f32) -> Vec<Glyph> {
1739 let mut g = Vec::new();
1740 let mut x = 100.0f32;
1741 for (text, gap) in pieces {
1742 x += gap;
1743 for ch in text.chars() {
1744 g.push(Glyph {
1745 b: y,
1746 t: y + 10.0,
1747 lb: y - 2.0,
1748 lt: y + 10.0,
1749 ..glyph(ch, x, x + 2.5)
1750 });
1751 x += 2.5;
1752 }
1753 }
1754 g
1755 }
1756
1757 #[test]
1758 fn one_wide_gap_does_not_raise_the_line_s_word_gap() {
1759 let g = set_line(
1764 &[
1765 ("jedoch", 0.0),
1766 ("werden", 0.8),
1767 ("weiterlaufende", 0.8),
1768 ("Quartierkosten", 8.0),
1769 ],
1770 600.0,
1771 );
1772 let (_, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1773 let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1774 assert_eq!(
1775 texts,
1776 ["jedoch", "werden", "weiterlaufende", "Quartierkosten"]
1777 );
1778 }
1779
1780 #[test]
1781 fn a_lone_word_on_a_page_that_draws_spaces_keeps_its_kerning() {
1782 let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1787 let spaced = |y| {
1788 set_line(
1789 &[
1790 ("Die", 0.0),
1791 (" ", 0.0),
1792 ("Taxonomie", 0.0),
1793 (" ", 0.0),
1794 ("gilt", 0.0),
1795 ],
1796 y,
1797 )
1798 };
1799 let mut page = lone();
1800 page.extend(spaced(600.0));
1801 page.extend(spaced(620.0));
1802 let texts = |g: &[Glyph]| {
1803 let (lines, _) = line_and_word_cells_with(g, 792.0, true, WordGap::Adaptive);
1804 lines.into_iter().map(|c| c.text).collect::<Vec<_>>()
1805 };
1806 assert!(texts(&page).contains(&"Offenlegungspflichten".to_string()));
1807 assert_eq!(texts(&lone()), ["Offenlegungspf lichten"]);
1808 }
1809
1810 #[test]
1811 fn a_line_whose_spaces_are_drawn_before_its_letters_infers_its_gap() {
1812 let mut page = set_line(&[("The", 0.0), (" ", 0.0), ("manual", 0.0)], 600.0);
1818 page.extend(set_line(
1819 &[("For", 0.0), (" ", 0.0), ("safety", 0.0)],
1820 620.0,
1821 ));
1822 let words = ["نشكرك", "على", "شراء"];
1823 let (mut spaces, mut letters) = (Vec::new(), Vec::new());
1824 let mut x = 100.0f32;
1825 for (k, word) in words.iter().rev().enumerate() {
1826 if k > 0 {
1827 spaces.push(glyph(' ', x, x + 1.7));
1828 x += 1.7;
1829 }
1830 for ch in word.chars().rev() {
1831 letters.push(glyph(ch, x, x + 5.0));
1832 x += 5.0;
1833 }
1834 }
1835 page.extend(spaces);
1836 page.extend(letters);
1837 let (lines, _) = line_and_word_cells_with(&page, 792.0, true, WordGap::Adaptive);
1838 let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1839 assert!(texts.contains(&"نشكرك على شراء"), "{texts:?}");
1840 }
1841
1842 #[test]
1843 fn a_lone_word_beside_another_line_s_space_keeps_its_kerning() {
1844 let spaced = |y| {
1851 set_line(
1852 &[
1853 ("Die", 0.0),
1854 (" ", 0.0),
1855 ("Taxonomie", 0.0),
1856 (" ", 0.0),
1857 ("gilt", 0.0),
1858 ],
1859 y,
1860 )
1861 };
1862 let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1864 let space = |l: f32, r: f32, y: f32| Glyph {
1865 b: y,
1866 t: y + 10.0,
1867 lb: y - 2.0,
1868 lt: y + 10.0,
1869 ..glyph(' ', l, r)
1870 };
1871 let line_with = |stray: Glyph| {
1872 let mut page = spaced(600.0);
1873 page.extend(spaced(620.0));
1874 page.push(stray);
1875 page.extend(lone());
1876 let (lines, _) = line_and_word_cells_with(&page, 792.0, true, WordGap::Adaptive);
1877 lines
1878 .into_iter()
1879 .map(|c| c.text)
1880 .find(|t| t.starts_with("Offen"))
1881 .expect("the lone word's line")
1882 };
1883 assert_eq!(
1884 line_with(space(154.0, 155.7, 500.0)),
1885 "Offenlegungspflichten"
1886 );
1887 assert_eq!(
1888 line_with(space(135.0, 135.8, 494.0)),
1889 "Offenlegungspflichten"
1890 );
1891 assert_eq!(
1892 line_with(space(135.0, 135.8, 500.0)),
1893 "Offenlegungspf lichten"
1894 );
1895 }
1896
1897 #[test]
1898 fn a_space_drawn_apart_is_judged_on_both_glyphs_beside_it() {
1899 let mark = Glyph {
1903 lb: 104.0,
1904 ..glyph('\u{064b}', 100.0, 103.0)
1905 };
1906 let cells = build_cells(
1907 &[
1908 mark,
1909 glyph('\u{0644}', 105.0, 110.0),
1910 glyph(' ', 103.2, 104.8),
1911 ],
1912 true,
1913 );
1914 let run: Vec<RunCell> = cells[..2].iter().map(RunCell::new).collect();
1915 let spaces = [(0.5 * (cells[2].b_b + cells[2].b_t), &cells[2])];
1916 assert!(spaces_drawn_apart(&run, &spaces));
1917 }
1918
1919 #[test]
1920 fn word_gap_spellings() {
1921 assert_eq!(WordGap::parse("adaptive"), Ok(WordGap::Adaptive));
1922 assert_eq!(WordGap::parse(" Legacy "), Ok(WordGap::Legacy));
1923 assert_eq!(WordGap::parse("0.2"), Ok(WordGap::Factor(0.2)));
1924 for bad in ["0", "-1", "5", "nan", "wide"] {
1925 assert!(WordGap::parse(bad).is_err(), "{bad}");
1926 }
1927 }
1928}