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 line_and_word_cells_cut(glyphs, page_h, euclidean, gap, zero_advance_run())
476}
477
478fn zero_advance_run() -> bool {
486 static ON: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
487 *ON.get_or_init(|| docling_core::env::flag("DOCLING_RS_PDF_ZERO_ADVANCE_RUN"))
488}
489
490fn line_and_word_cells_cut(
492 glyphs: &[Glyph],
493 page_h: f32,
494 euclidean: bool,
495 gap: WordGap,
496 zero_advance_run: bool,
497) -> (Vec<TextCell>, Vec<TextCell>) {
498 let built = build_cells(glyphs, euclidean);
499 if gap != WordGap::Legacy {
500 return contract_runs(&built, gap, page_h, zero_advance_run);
501 }
502 let to_text_cell = |c: Cell| {
503 let l = c.rx0.min(c.rx1).min(c.rx2).min(c.rx3) as f32;
504 let r = c.rx0.max(c.rx1).max(c.rx2).max(c.rx3) as f32;
505 let top = c.ry0.max(c.ry1).max(c.ry2).max(c.ry3) as f32;
506 let bot = c.ry0.min(c.ry1).min(c.ry2).min(c.ry3) as f32;
507 TextCell {
508 text: c.text,
509 l,
510 t: page_h - top,
511 r,
512 b: page_h - bot,
513 }
514 };
515 let mut word_run: Vec<Cell> = built.clone();
524 let mut cells = built;
525 contract(&mut cells, euclidean, LINE_FACTORS);
526 let lines = to_text_cells(cells, to_text_cell);
527 contract(&mut word_run, euclidean, WORD_FACTORS);
528 word_run.retain(|c| !c.text.trim().is_empty());
529 let words = to_text_cells(word_run, to_text_cell);
530 (lines, words)
531}
532
533fn to_text_cells(cells: Vec<Cell>, f: impl Fn(Cell) -> TextCell) -> Vec<TextCell> {
543 let mut out = Vec::with_capacity(cells.len());
544 out.extend(cells.into_iter().map(f));
545 out
546}
547
548fn is_rtl_char(c: char) -> bool {
549 let ch = c as u32;
550 (0x0600..=0x06FF).contains(&ch)
551 || (0x0750..=0x077F).contains(&ch)
552 || (0x08A0..=0x08FF).contains(&ch)
553 || (0xFB50..=0xFDFF).contains(&ch)
554 || (0xFE70..=0xFEFF).contains(&ch)
555 || (0x0590..=0x05FF).contains(&ch)
556 || (0xFB1D..=0xFB4F).contains(&ch)
557 || (0x0700..=0x074F).contains(&ch)
558 || (0x0780..=0x07BF).contains(&ch)
559 || (0x07C0..=0x07FF).contains(&ch)
560}
561
562fn is_right_to_left(s: &str) -> bool {
564 !s.is_empty() && s.chars().all(is_rtl_char)
565}
566
567fn is_punct_or_space(s: &str) -> bool {
569 let mut chars = s.chars();
570 let (Some(c), None) = (chars.next(), chars.next()) else {
571 return false;
572 };
573 if matches!(
574 c,
575 ' ' | '\t'
576 | '\n'
577 | '\r'
578 | '\u{0c}'
579 | '\u{0b}'
580 | '.'
581 | ','
582 | ';'
583 | ':'
584 | '!'
585 | '?'
586 | '('
587 | ')'
588 | '['
589 | ']'
590 | '{'
591 | '}'
592 | '\''
593 | '"'
594 | '`'
595 | '\u{2018}'
596 | '\u{2019}'
597 | '\u{201c}'
598 | '\u{201d}'
599 | '-'
600 | '\u{2013}'
601 | '\u{2014}'
602 | '_'
603 | '/'
604 | '\\'
605 | '|'
606 | '@'
607 | '#'
608 | '%'
609 | '&'
610 | '*'
611 | '+'
612 | '='
613 | '<'
614 | '>'
615 ) {
616 return true;
617 }
618 let ch = c as u32;
619 (0x2000..=0x206F).contains(&ch)
620 || (0x3000..=0x303F).contains(&ch)
621 || (0xFE50..=0xFE6F).contains(&ch)
622 || (0xFF00..=0xFF0F).contains(&ch)
623 || (0xFF1A..=0xFF1F).contains(&ch)
624 || (0xFF3B..=0xFF5E).contains(&ch)
625}
626
627fn is_ligature(s: &str) -> bool {
629 matches!(s, "ff" | "fi" | "fl" | "ffi" | "ffl")
630 || s.chars().any(|c| (0xFB00..=0xFB06).contains(&(c as u32)))
631}
632
633#[derive(Clone, Copy, Debug, Default, PartialEq)]
656pub enum WordGap {
657 Legacy,
659 Factor(f64),
661 #[default]
665 Adaptive,
666}
667
668impl WordGap {
669 pub const ACCEPTED: &'static str = "legacy, adaptive, or a factor in (0, 4]";
671
672 pub fn parse(s: &str) -> Result<Self, String> {
675 let t = s.trim().to_ascii_lowercase();
676 match t.as_str() {
677 "legacy" => Ok(WordGap::Legacy),
678 "adaptive" | "auto" | "default" => Ok(WordGap::Adaptive),
679 _ => match t.parse::<f64>() {
680 Ok(f) if f.is_finite() && f > 0.0 && f <= 4.0 => Ok(WordGap::Factor(f)),
681 _ => Err(format!(
682 "pdf_word_gap must be {}, got {s:?}",
683 WordGap::ACCEPTED
684 )),
685 },
686 }
687 }
688
689 pub fn from_env() -> Self {
693 let Some(v) = docling_core::env::nonempty("DOCLING_RS_PDF_WORD_GAP") else {
694 return WordGap::default();
695 };
696 WordGap::parse(&v).unwrap_or_else(|e| {
697 static WARNED: std::sync::Once = std::sync::Once::new();
698 WARNED.call_once(|| {
699 eprintln!("docling-pdf: DOCLING_RS_PDF_WORD_GAP: {e}; using adaptive")
700 });
701 WordGap::default()
702 })
703 }
704}
705
706const NO_AXIS: f64 = 1e-9;
711
712struct RunCell<'a> {
714 cell: &'a Cell,
715 ux: f64,
717 uy: f64,
718 advance: f64,
720 height: f64,
721 space: bool,
722}
723
724impl<'a> RunCell<'a> {
725 fn new(cell: &'a Cell) -> Self {
726 let (dx, dy) = (cell.rx1 - cell.rx0, cell.ry1 - cell.ry0);
727 let advance = dx.hypot(dy);
728 let (ux, uy) = if advance > NO_AXIS {
729 (dx / advance, dy / advance)
730 } else {
731 (1.0, 0.0)
732 };
733 let h0 = (cell.rx3 - cell.rx0).hypot(cell.ry3 - cell.ry0);
734 let h1 = (cell.rx2 - cell.rx1).hypot(cell.ry2 - cell.ry1);
735 RunCell {
736 cell,
737 ux,
738 uy,
739 advance,
740 height: 0.5 * (h0 + h1),
741 space: cell.blank,
742 }
743 }
744
745 fn scale(&self) -> f64 {
748 if self.advance > 1e-6 {
749 self.advance
750 } else {
751 (0.5 * self.height).max(1e-6)
752 }
753 }
754}
755
756fn forward_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
765 let (l, r) = (lhs.cell, rhs.cell);
766 let (tx, ty) = (0.5 * (l.rx1 + l.rx2), 0.5 * (l.ry1 + l.ry2));
767 let (hx, hy) = (0.5 * (r.rx0 + r.rx3), 0.5 * (r.ry0 + r.ry3));
768 (hx - tx) * lhs.ux + (hy - ty) * lhs.uy
769}
770
771fn facing_edge_overlap(lhs: &RunCell, rhs: &RunCell, zero_advance_run: bool) -> f64 {
774 let (l, r) = (lhs.cell, rhs.cell);
775 if zero_advance_run && lhs.advance <= NO_AXIS {
780 return 0.0;
781 }
782 let (ux, uy) = if l.ltr {
783 (lhs.ux, lhs.uy)
784 } else {
785 (-lhs.ux, -lhs.uy)
786 };
787 let (nx, ny) = (-uy, ux);
788 let proj = |x: f64, y: f64| x * nx + y * ny;
789 let (a0, a1) = if l.ltr {
790 (proj(l.rx1, l.ry1), proj(l.rx2, l.ry2))
791 } else {
792 (proj(l.rx0, l.ry0), proj(l.rx3, l.ry3))
793 };
794 let (b0, b1) = if l.ltr {
795 (proj(r.rx0, r.ry0), proj(r.rx3, r.ry3))
796 } else {
797 (proj(r.rx1, r.ry1), proj(r.rx2, r.ry2))
798 };
799 a0.max(a1).min(b0.max(b1)) - a0.min(a1).max(b0.min(b1))
800}
801
802fn is_math_glyph(text: &str) -> bool {
806 const MATH: &str = "∑∏∫√∞∈∉≠≤≥⊂⊃⊆⊇⊥∪∩⎛⎜⎝⎞⎟⎠⎡⎢⎣⎤⎥⎦";
807 text.chars().any(|c| MATH.contains(c))
808}
809
810fn is_local_attachment(lhs: &RunCell, rhs: &RunCell) -> bool {
813 let scale = lhs.scale().max(rhs.scale());
814 if forward_gap(lhs, rhs) > 0.10 * scale {
815 return false;
816 }
817 let (off, (lh, rh)) = baseline_offset(lhs, rhs);
818 let math = |c: &RunCell| c.cell.math_font || is_math_glyph(&c.cell.text);
819 off <= 2.0 * lh.max(rh).max(1e-6) && (math(lhs) || math(rhs))
820}
821
822fn baseline_offset(lhs: &RunCell, rhs: &RunCell) -> (f64, (f64, f64)) {
830 let (nx, ny) = (-lhs.uy, lhs.ux);
831 match (lhs.cell.pen, rhs.cell.pen) {
832 (Some(a), Some(b)) => (
833 ((b[0] - a[0]) * nx + (b[1] - a[1]) * ny).abs(),
834 (a[2], b[2]),
835 ),
836 _ => (
837 ((rhs.cell.rx0 - lhs.cell.rx0) * nx + (rhs.cell.ry0 - lhs.cell.ry0) * ny).abs(),
838 (lhs.height, rhs.height),
839 ),
840 }
841}
842
843fn continues_line(lhs: &RunCell, rhs: &RunCell, zero_advance_run: bool) -> bool {
847 if lhs.ux * rhs.ux + lhs.uy * rhs.uy < 0.985 {
848 return false;
849 }
850 let scale = lhs.scale().max(rhs.scale());
851 let gap = forward_gap(lhs, rhs);
852 if facing_edge_overlap(lhs, rhs, zero_advance_run) <= 1e-6 && !is_local_attachment(lhs, rhs) {
853 return false;
854 }
855 -scale <= gap && gap <= 4.0 * scale
856}
857
858fn baselines_compatible(lhs: &RunCell, rhs: &RunCell) -> bool {
862 let (off, (lh, rh)) = baseline_offset(lhs, rhs);
863 off <= 0.35 * lh.min(rh).max(1e-6) || is_local_attachment(lhs, rhs)
864}
865
866fn normalized_gap(lhs: &RunCell, rhs: &RunCell) -> f64 {
868 forward_gap(lhs, rhs).max(0.0) / (0.5 * (lhs.scale() + rhs.scale())).max(1e-6)
869}
870
871#[derive(Clone, Copy, PartialEq)]
873enum TrackClass {
874 Letter,
876 Dot,
878 Other,
879}
880
881fn track_class(text: &str) -> TrackClass {
882 if matches!(text, "." | "·" | "…") {
883 TrackClass::Dot
884 } else if !text.is_empty() && text.chars().all(char::is_alphanumeric) {
885 TrackClass::Letter
886 } else {
887 TrackClass::Other
888 }
889}
890
891fn tracking_tolerance(gap: f64) -> f64 {
895 (0.08 * gap).max(0.25)
896}
897
898fn tracked_gaps(run: &[RunCell]) -> Vec<bool> {
922 struct Gap {
923 left: usize,
924 right: usize,
925 pt: f64,
926 n: f64,
927 left_class: TrackClass,
928 right_class: TrackClass,
929 }
930 let mut gaps: Vec<Gap> = Vec::new();
931 let mut prev: Option<usize> = None;
932 let mut crossed_space = false;
933 for (i, c) in run.iter().enumerate() {
934 if c.space {
935 crossed_space = true;
936 continue;
937 }
938 if let (Some(p), false) = (prev, crossed_space) {
939 gaps.push(Gap {
940 left: p,
941 right: i,
942 pt: forward_gap(&run[p], c),
943 n: normalized_gap(&run[p], c),
944 left_class: track_class(&run[p].cell.text),
945 right_class: track_class(&c.cell.text),
946 });
947 }
948 prev = Some(i);
949 crossed_space = false;
950 }
951 let joined = |k: usize| gaps[k + 1].left == gaps[k].right;
953 let stretch = |k: usize, fits: &dyn Fn(&Gap) -> bool| {
955 let mut end = k;
956 while end < gaps.len() && fits(&gaps[end]) && (end == k || joined(end - 1)) {
957 end += 1;
958 }
959 end
960 };
961 let flanks_open = |k: usize, end: usize, floor: f64| {
963 let before = k > 0 && joined(k - 1) && gaps[k - 1].pt < floor;
964 let after = end < gaps.len() && joined(end - 1) && gaps[end].pt < floor;
965 !before && !after
966 };
967
968 let mut tracked = vec![false; run.len()];
969 let mut leader = vec![false; run.len()];
970 let mut letter_tracking: Vec<f64> = Vec::new();
971 let mut k = 0;
972 while k < gaps.len() {
973 let dots = |g: &Gap| {
974 g.left_class == TrackClass::Dot && g.right_class == TrackClass::Dot && g.n <= 1.0
975 };
976 let end = stretch(k, &dots);
977 if end - k >= 3 {
978 for g in &gaps[k..end] {
979 tracked[g.right] = true;
980 leader[g.left] = true;
981 leader[g.right] = true;
982 }
983 k = end;
984 continue;
985 }
986 let first = &gaps[k];
987 let letters = |g: &Gap| {
988 g.left_class == TrackClass::Letter
989 && g.right_class == TrackClass::Letter
990 && (0.1..=1.0).contains(&g.n)
991 };
992 if !letters(first) {
993 k += 1;
994 continue;
995 }
996 let (mut lo, mut hi) = (first.pt, first.pt);
997 let mut end = k + 1;
998 while end < gaps.len()
999 && joined(end - 1)
1000 && letters(&gaps[end])
1001 && hi.max(gaps[end].pt) - lo.min(gaps[end].pt) <= tracking_tolerance(lo)
1002 {
1003 lo = lo.min(gaps[end].pt);
1004 hi = hi.max(gaps[end].pt);
1005 end += 1;
1006 }
1007 let one_char = gaps[k..end]
1010 .iter()
1011 .all(|g| run[g.right].cell.text == run[first.left].cell.text);
1012 if end - k >= 3 && !one_char && flanks_open(k, end, lo - tracking_tolerance(lo)) {
1013 for g in &gaps[k..end] {
1014 tracked[g.right] = true;
1015 }
1016 letter_tracking.push(0.5 * (lo + hi));
1017 k = end;
1018 } else {
1019 k += 1;
1020 }
1021 }
1022
1023 for &t in &letter_tracking {
1024 let tol = tracking_tolerance(t);
1025 let same = |g: &Gap| {
1026 (g.left_class == TrackClass::Letter || g.right_class == TrackClass::Letter)
1027 && g.left_class != TrackClass::Dot
1028 && g.right_class != TrackClass::Dot
1029 && g.n <= 1.0
1030 && (g.pt - t).abs() <= tol
1031 };
1032 let mut k = 0;
1033 while k < gaps.len() {
1034 let end = stretch(k, &same);
1035 if end == k {
1036 k += 1;
1037 continue;
1038 }
1039 if flanks_open(k, end, t - tol) && !gaps[k..end].iter().any(|g| leader[g.left]) {
1040 for g in &gaps[k..end] {
1041 tracked[g.right] = true;
1042 }
1043 }
1044 k = end;
1045 }
1046 }
1047 tracked
1048}
1049
1050const GAP_CLUSTER_CLIP: f64 = 0.5;
1060
1061fn infer_word_gap(run: &[RunCell], tracked: &[bool]) -> f64 {
1069 let mut gaps = Vec::new();
1070 let mut prev: Option<&RunCell> = None;
1071 let mut crossed_space = false;
1072 for (i, c) in run.iter().enumerate() {
1073 if c.space {
1074 crossed_space = true;
1075 continue;
1076 }
1077 if let (Some(p), false, false) = (prev, crossed_space, tracked[i]) {
1078 gaps.push(normalized_gap(p, c).min(GAP_CLUSTER_CLIP));
1079 }
1080 prev = Some(c);
1081 crossed_space = false;
1082 }
1083 if gaps.len() < 2 {
1084 return 0.25;
1085 }
1086 let mut low = gaps.iter().copied().fold(f64::INFINITY, f64::min);
1087 let mut high = gaps.iter().copied().fold(f64::NEG_INFINITY, f64::max);
1088 if high < 0.18 || high - low < 0.08 {
1089 return 0.25;
1090 }
1091 for _ in 0..8 {
1092 let mid = 0.5 * (low + high);
1093 let (mut ls, mut ln, mut hs, mut hn) = (0.0, 0usize, 0.0, 0usize);
1094 for &g in &gaps {
1095 if g <= mid {
1096 ls += g;
1097 ln += 1;
1098 } else {
1099 hs += g;
1100 hn += 1;
1101 }
1102 }
1103 if ln == 0 || hn == 0 {
1104 return 0.25;
1105 }
1106 low = ls / ln as f64;
1107 high = hs / hn as f64;
1108 }
1109 if high < 0.18 || high - low < 0.08 {
1110 return 0.25;
1111 }
1112 (0.5 * (low + high)).max(0.18)
1113}
1114
1115struct Agg {
1117 text: String,
1118 ltr: bool,
1119 q: [f64; 8],
1120 glued: bool,
1127}
1128
1129impl Agg {
1130 fn of(c: &Cell, glued: bool) -> Self {
1131 Agg {
1132 text: c.text.clone(),
1133 ltr: c.ltr,
1134 q: [c.rx0, c.ry0, c.rx1, c.ry1, c.rx2, c.ry2, c.rx3, c.ry3],
1135 glued,
1136 }
1137 }
1138
1139 fn append(&mut self, text: &str, ltr: bool, q: &[f64; 8], space: bool) {
1143 if self.ltr && ltr {
1144 if space {
1145 self.text.push(' ');
1146 }
1147 self.text.push_str(text);
1148 } else {
1149 let sep = if space { " " } else { "" };
1150 self.text = format!("{text}{sep}{}", self.text);
1151 self.ltr = false;
1152 }
1153 let (mut ux, mut uy) = (self.q[2] - self.q[0], self.q[3] - self.q[1]);
1154 if ux.hypot(uy) <= 1e-9 {
1155 (ux, uy) = (q[2] - q[0], q[3] - q[1]);
1156 }
1157 let n = ux.hypot(uy);
1158 if n <= 1e-9 {
1159 return;
1160 }
1161 let (ux, uy) = (ux / n, uy / n);
1162 let (nx, ny) = (-uy, ux);
1163 let (mut u0, mut u1, mut n0, mut n1) = (
1164 f64::INFINITY,
1165 f64::NEG_INFINITY,
1166 f64::INFINITY,
1167 f64::NEG_INFINITY,
1168 );
1169 for k in 0..4 {
1170 for (x, y) in [(self.q[2 * k], self.q[2 * k + 1]), (q[2 * k], q[2 * k + 1])] {
1171 let (u, v) = (x * ux + y * uy, x * nx + y * ny);
1172 u0 = u0.min(u);
1173 u1 = u1.max(u);
1174 n0 = n0.min(v);
1175 n1 = n1.max(v);
1176 }
1177 }
1178 let pt = |u: f64, v: f64| (u * ux + v * nx, u * uy + v * ny);
1179 let (a, b, c, d) = (pt(u0, n0), pt(u1, n0), pt(u1, n1), pt(u0, n1));
1180 self.q = [a.0, a.1, b.0, b.1, c.0, c.1, d.0, d.1];
1181 }
1182
1183 fn into_cell(self, page_h: f32) -> TextCell {
1184 let xs = [self.q[0], self.q[2], self.q[4], self.q[6]];
1185 let ys = [self.q[1], self.q[3], self.q[5], self.q[7]];
1186 let (l, r) = (
1187 xs.iter().copied().fold(f64::INFINITY, f64::min),
1188 xs.iter().copied().fold(f64::NEG_INFINITY, f64::max),
1189 );
1190 let (b, t) = (
1191 ys.iter().copied().fold(f64::INFINITY, f64::min),
1192 ys.iter().copied().fold(f64::NEG_INFINITY, f64::max),
1193 );
1194 TextCell {
1195 text: self.text,
1196 l: l as f32,
1197 t: page_h - t as f32,
1198 r: r as f32,
1199 b: page_h - b as f32,
1200 }
1201 }
1202}
1203
1204fn page_draws_spaces(runs: &[Vec<RunCell>]) -> bool {
1211 let long = |r: &&Vec<RunCell>| r.iter().filter(|c| !c.space).count() >= 8;
1212 let lines = runs.iter().filter(long).count();
1213 let spaced = runs
1214 .iter()
1215 .filter(long)
1216 .filter(|r| r.iter().any(|c| c.space))
1217 .count();
1218 lines > 0 && 2 * spaced >= lines
1219}
1220
1221fn spaces_drawn_apart(run: &[RunCell], spaces: &[(f64, &Cell)]) -> bool {
1230 let mut visible = run.iter().filter(|c| !c.space);
1231 let Some(first) = visible.next() else {
1232 return false;
1233 };
1234 let (mut l, mut r, mut b, mut t) = bounds(first.cell);
1236 for c in visible.clone() {
1237 let (cl, cr, cb, ct) = bounds(c.cell);
1238 (l, r, b, t) = (l.min(cl), r.max(cr), b.min(cb), t.max(ct));
1239 }
1240 let (lo, hi) = (
1241 spaces.partition_point(|&(y, _)| y < b),
1242 spaces.partition_point(|&(y, _)| y <= t),
1243 );
1244 let inside: Vec<&Cell> = spaces[lo..hi]
1245 .iter()
1246 .map(|&(_, c)| c)
1247 .filter(|c| (l..=r).contains(&(0.5 * (c.b_l + c.b_r))))
1248 .collect();
1249 if inside.is_empty() {
1250 return false;
1251 }
1252 let (ux, uy) = (first.ux, first.uy);
1253 let along = |x: f64, y: f64| x * ux + y * uy;
1254 let across = |c: &Cell| {
1255 let v = [
1256 c.rx0 * -uy + c.ry0 * ux,
1257 c.rx1 * -uy + c.ry1 * ux,
1258 c.rx2 * -uy + c.ry2 * ux,
1259 c.rx3 * -uy + c.ry3 * ux,
1260 ];
1261 let lo = v.iter().copied().fold(f64::INFINITY, f64::min);
1262 let hi = v.iter().copied().fold(f64::NEG_INFINITY, f64::max);
1263 (lo, hi)
1264 };
1265 let mut gaps = Vec::new();
1269 let mut prev = first;
1270 for c in visible {
1271 let (lhs, rhs) = (prev.cell, c.cell);
1272 let tail = along(0.5 * (lhs.rx1 + lhs.rx2), 0.5 * (lhs.ry1 + lhs.ry2));
1273 let head = along(0.5 * (rhs.rx0 + rhs.rx3), 0.5 * (rhs.ry0 + rhs.ry3));
1274 if head > tail {
1275 let ((l0, l1), (r0, r1)) = (across(lhs), across(rhs));
1276 gaps.push((tail, head, (l0.min(r0), l1.max(r1))));
1277 }
1278 prev = c;
1279 }
1280 inside.iter().any(|c| {
1281 let mid = along(0.5 * (c.rx0 + c.rx2), 0.5 * (c.ry0 + c.ry2));
1282 let (s0, s1) = across(c);
1283 gaps.iter().any(|&(tail, head, (b0, b1))| {
1284 tail <= mid && mid <= head && s1.min(b1) - s0.max(b0) > 0.5 * (s1 - s0)
1285 })
1286 })
1287}
1288
1289fn contract_runs(
1293 cells: &[Cell],
1294 gap: WordGap,
1295 page_h: f32,
1296 zero_advance_run: bool,
1297) -> (Vec<TextCell>, Vec<TextCell>) {
1298 let mut runs: Vec<Vec<RunCell>> = Vec::new();
1301 for c in cells.iter().filter(|c| !c.text.is_empty()) {
1302 let rc = RunCell::new(c);
1303 if rc.space {
1304 match runs.last_mut() {
1305 Some(run) => run.push(rc),
1306 None => runs.push(vec![rc]),
1307 }
1308 continue;
1309 }
1310 let starts = match runs.last().and_then(|r| r.iter().rev().find(|c| !c.space)) {
1311 Some(prev) => !continues_line(prev, &rc, zero_advance_run),
1312 None => runs.is_empty(),
1313 };
1314 if starts {
1315 runs.push(Vec::new());
1316 }
1317 runs.last_mut().expect("a run is open").push(rc);
1318 }
1319
1320 let (mut words_out, mut lines_out) = (Vec::new(), Vec::new());
1321 let page_spaced = page_draws_spaces(&runs);
1322 let mut spaces: Vec<(f64, &Cell)> = Vec::new();
1323 if page_spaced {
1324 spaces.extend(
1325 runs.iter()
1326 .flatten()
1327 .filter(|c| c.space)
1328 .map(|c| (0.5 * (c.cell.b_b + c.cell.b_t), c.cell)),
1329 );
1330 spaces.sort_by(|a, b| a.0.total_cmp(&b.0));
1331 }
1332 for run in &runs {
1333 let has_spaces =
1343 run.iter().any(|c| c.space) || (page_spaced && !spaces_drawn_apart(run, &spaces));
1344 let tracked = tracked_gaps(run);
1345 let threshold = match gap {
1352 WordGap::Factor(f) if has_spaces => f.max(0.35),
1353 WordGap::Factor(f) => f,
1354 _ => (if has_spaces {
1355 1.0
1356 } else {
1357 infer_word_gap(run, &tracked)
1358 })
1359 .min(0.35),
1360 };
1361 let mut words: Vec<Agg> = Vec::new();
1362 let mut prev: Option<&RunCell> = None;
1363 let mut boundary = false;
1364 for (i, c) in run.iter().enumerate() {
1365 if c.space {
1366 boundary = true;
1367 continue;
1368 }
1369 let mut starts = words.is_empty() || boundary;
1370 let mut glued = false;
1371 if !starts
1374 && c.cell.text == "."
1375 && i + 4 < run.len()
1376 && run[i + 1].space
1377 && run[i + 2].cell.text == "."
1378 && run[i + 3].space
1379 && run[i + 4].cell.text == "."
1380 && prev.is_some_and(|p| p.cell.text != ".")
1381 {
1382 starts = true;
1383 }
1384 if let (false, Some(p)) = (starts, prev) {
1385 let shifted = !baselines_compatible(p, c);
1386 let gapped = !tracked[i] && normalized_gap(p, c) > threshold;
1387 starts = shifted || gapped;
1388 let opens = |s: &str| matches!(s.chars().last(), Some('(' | '[' | '{'));
1400 let closes = |s: &str| matches!(s.chars().next(), Some(')' | ']' | '}'));
1401 glued = shifted
1402 && !gapped
1403 && (words.last().is_some_and(|w| opens(&w.text)) || closes(&c.cell.text));
1404 }
1405 if starts {
1406 words.push(Agg::of(c.cell, glued));
1407 } else {
1408 let q = [
1409 c.cell.rx0, c.cell.ry0, c.cell.rx1, c.cell.ry1, c.cell.rx2, c.cell.ry2,
1410 c.cell.rx3, c.cell.ry3,
1411 ];
1412 words.last_mut().expect("a word is open").append(
1413 &c.cell.text,
1414 c.cell.ltr,
1415 &q,
1416 false,
1417 );
1418 }
1419 prev = Some(c);
1420 boundary = false;
1421 }
1422 let mut it = words.into_iter();
1423 let Some(first) = it.next() else {
1424 continue;
1425 };
1426 let mut line = Agg {
1427 text: first.text.clone(),
1428 ltr: first.ltr,
1429 q: first.q,
1430 glued: false,
1431 };
1432 words_out.push(first.into_cell(page_h));
1433 for w in it {
1434 line.append(&w.text, w.ltr, &w.q, !w.glued);
1435 words_out.push(w.into_cell(page_h));
1436 }
1437 lines_out.push(line.into_cell(page_h));
1438 }
1439 (lines_out, words_out)
1440}
1441
1442#[cfg(test)]
1443mod tests {
1444 use super::*;
1445
1446 fn glyph(ch: char, l: f32, r: f32) -> Glyph {
1447 Glyph {
1448 ch,
1449 l,
1450 b: 100.0,
1451 r,
1452 t: 110.0,
1453 ll: l,
1454 lb: 98.0,
1455 lr: r,
1456 lt: 110.0,
1457 font: 0,
1458 quad: None,
1459 pen: None,
1460 math_font: false,
1461 invisible: false,
1462 }
1463 }
1464
1465 #[test]
1470 fn space_glyph_separates_tight_words() {
1471 let glyphs = [
1472 glyph('M', 137.66, 143.74),
1473 glyph('O', 143.74, 149.82),
1474 glyph('D', 149.82, 155.90),
1475 glyph('E', 155.90, 161.98),
1476 glyph(' ', 161.84, 164.09),
1477 glyph('t', 163.82, 166.60),
1478 glyph('o', 166.60, 171.60),
1479 ];
1480 let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1481 let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1482 assert_eq!(words, ["MODE", "to"]);
1483 assert_eq!(lines.len(), 1);
1484 assert_eq!(lines[0].text, "MODE to");
1485 }
1486
1487 #[test]
1492 fn stacked_glyphs_at_one_x_stay_separate_cells() {
1493 let at = |ch: char, b: f32| Glyph {
1494 lb: b,
1495 lt: b + 10.0,
1496 b,
1497 t: b + 10.0,
1498 ..glyph(ch, 98.0, 103.0)
1499 };
1500 let ticks: Vec<Glyph> = "345678"
1501 .chars()
1502 .enumerate()
1503 .map(|(k, ch)| at(ch, 316.0 + 25.92 * k as f32))
1504 .collect();
1505 let lines = line_cells(&ticks, 792.0, true);
1506 let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1507 assert_eq!(texts, ["3", "4", "5", "6", "7", "8"]);
1508 assert!(lines.windows(2).all(|w| w[0].t > w[1].t));
1509
1510 let lig = [glyph('f', 10.0, 16.0), glyph('i', 10.0, 16.0)];
1511 let lines = line_cells(&lig, 792.0, true);
1512 assert_eq!(lines.len(), 1);
1513 assert_eq!(lines[0].text, "fi");
1514 }
1515
1516 #[test]
1521 fn cells_do_not_keep_the_glyph_buffer() {
1522 let glyphs: Vec<Glyph> = (0..400)
1524 .map(|i| {
1525 let x = (i % 40) as f32 * 6.0;
1526 let ch = if i % 4 == 3 { ' ' } else { '7' };
1527 let mut g = glyph(ch, x, x + 6.0);
1528 let row = (i / 40) as f32 * 14.0;
1529 (g.b, g.t, g.lb, g.lt) = (100.0 + row, 110.0 + row, 98.0 + row, 110.0 + row);
1530 g
1531 })
1532 .collect();
1533 let (lines, words) = line_and_word_cells(&glyphs, 792.0, true);
1534 assert_eq!((lines.len(), words.len()), (10, 100));
1535 assert_eq!(lines.capacity(), lines.len());
1536 assert_eq!(words.capacity(), words.len());
1537 }
1538
1539 fn und_dem_line() -> Vec<Glyph> {
1543 let at = |ch: char, l: f32, r: f32, font: u64| Glyph {
1544 ch,
1545 l,
1546 b: 682.056,
1547 r,
1548 t: 691.05,
1549 ll: l,
1550 lb: 682.056,
1551 lr: r,
1552 lt: 691.05,
1553 font,
1554 quad: None,
1555 pen: None,
1556 math_font: false,
1557 invisible: false,
1558 };
1559 let mut g = Vec::new();
1560 let mut run = |text: &str, edges: &[f32], font: u64| {
1561 for (i, ch) in text.chars().enumerate() {
1562 g.push(at(ch, edges[i], edges[i + 1], font));
1563 }
1564 };
1565 run(
1566 "schaft",
1567 &[
1568 328.976, 333.216, 338.572, 344.325, 350.486, 353.920, 357.248,
1569 ],
1570 1,
1571 );
1572 run("und", &[359.261, 365.121, 370.875, 377.035], 2);
1573 run("dem", &[378.990, 385.151, 390.701, 399.287], 2);
1574 run("Öst", &[401.214, 409.092, 413.332, 416.660], 1);
1575 g
1576 }
1577
1578 #[test]
1579 fn legacy_rule_keeps_the_borderline_und_dem_glued() {
1580 let (lines, words) = line_and_word_cells(&und_dem_line(), 792.0, true);
1584 assert!(lines.iter().any(|c| c.text == "unddem"), "{lines:?}");
1585 assert!(words.iter().any(|c| c.text == "unddem"), "{words:?}");
1586 }
1587
1588 #[test]
1589 fn line_local_word_gaps_split_und_dem() {
1590 for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1591 let (lines, words) = line_and_word_cells_with(&und_dem_line(), 792.0, true, gap);
1592 let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1593 assert_eq!(texts, ["schaft und dem Öst"], "{gap:?}");
1594 let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1595 assert_eq!(texts, ["schaft", "und", "dem", "Öst"], "{gap:?}");
1596 assert!((words[1].l - 359.261).abs() < 1e-3 && (words[1].r - 377.035).abs() < 1e-3);
1598 }
1599 let (lines, _) =
1601 line_and_word_cells_with(&und_dem_line(), 792.0, true, WordGap::Factor(0.5));
1602 assert_eq!(lines[0].text, "schaftunddemÖst");
1603 }
1604
1605 #[test]
1606 fn a_superscript_attaches_by_pen_origin_and_math_face() {
1607 let at = |ch: char, l: f32, y: f32, size: f32, math: bool, pen: bool| Glyph {
1611 lb: y - 0.2 * size,
1612 lt: y + 0.8 * size,
1613 b: y - 0.2 * size,
1614 t: y + 0.8 * size,
1615 pen: pen.then_some([l, y, size]),
1616 math_font: math,
1617 ..glyph(ch, l, l + 0.5 * size)
1618 };
1619 let line = |rise: f32, math: bool, pen: bool| {
1620 let mut g: Vec<Glyph> = "Lysak"
1621 .chars()
1622 .enumerate()
1623 .map(|(k, ch)| at(ch, 100.0 + 5.0 * k as f32, 600.0, 10.0, math, pen))
1624 .collect();
1625 g.extend(
1626 "[0000"
1627 .chars()
1628 .enumerate()
1629 .map(|(k, ch)| at(ch, 125.0 + 3.5 * k as f32, 600.0 + rise, 7.0, math, pen)),
1630 );
1631 let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1632 (
1633 lines[0].text.clone(),
1634 words.iter().map(|w| w.text.clone()).collect::<Vec<_>>(),
1635 )
1636 };
1637 let one = |s: &str| (s.to_string(), vec![s.to_string()]);
1638 let two = |s: &str| {
1639 (
1640 s.to_string(),
1641 vec!["Lysak".to_string(), "[0000".to_string()],
1642 )
1643 };
1644 assert_eq!(line(3.6, true, true), one("Lysak[0000"));
1650 assert_eq!(line(3.6, false, true), two("Lysak [0000"));
1651 assert_eq!(line(2.0, false, true), one("Lysak[0000"));
1654 assert_eq!(line(2.0, false, false), two("Lysak [0000"));
1655 }
1656
1657 #[test]
1664 fn a_touching_superscript_joins_the_line_text_inside_brackets_only() {
1665 let at = |ch: char, l: f32, w: f32, y: f32, size: f32| Glyph {
1666 lb: y - 0.2 * size,
1667 lt: y + 0.8 * size,
1668 b: y - 0.2 * size,
1669 t: y + 0.8 * size,
1670 pen: Some([l, y, size]),
1671 ..glyph(ch, l, l + w)
1672 };
1673 let g = [
1674 at('E', 100.0, 6.0, 600.0, 10.5),
1675 at('G', 106.0, 6.9, 600.0, 10.5),
1676 at('(', 115.3, 3.2, 600.0, 10.5),
1677 at('1', 118.5, 3.1, 603.5, 6.8),
1678 at(')', 121.6, 3.2, 600.0, 10.5),
1679 at('e', 127.2, 5.0, 600.0, 10.5),
1680 ];
1681 let (lines, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1682 assert_eq!(lines[0].text, "EG (1) e");
1683 let words: Vec<&str> = words.iter().map(|w| w.text.as_str()).collect();
1684 assert_eq!(words, ["EG", "(", "1", ")", "e"]);
1685 let g = [
1687 at('E', 100.0, 6.0, 600.0, 10.5),
1688 at('G', 106.0, 6.9, 600.0, 10.5),
1689 at('1', 112.9, 3.1, 603.5, 6.8),
1690 ];
1691 let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1692 assert_eq!(lines[0].text, "EG 1");
1693 }
1694
1695 #[test]
1696 fn a_factor_keeps_docling_parse_s_floor_on_lines_with_space_glyphs() {
1697 let mut g = Vec::new();
1702 let mut x = 100.0f32;
1703 let put = |g: &mut Vec<Glyph>, s: &str, x: &mut f32| {
1704 for ch in s.chars() {
1705 g.push(glyph(ch, *x, *x + 2.5));
1706 *x += 2.5;
1707 }
1708 };
1709 put(&mut g, "Die", &mut x);
1710 g.push(glyph(' ', x, x + 2.5));
1711 x += 2.5;
1712 put(&mut g, "Verpf", &mut x);
1713 x += 0.6;
1714 put(&mut g, "lichtungen", &mut x);
1715 let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Factor(0.2));
1716 assert_eq!(lines[0].text, "Die Verpflichtungen");
1717 let spaceless: Vec<Glyph> = g.into_iter().filter(|c| c.ch != ' ').collect();
1718 let (lines, _) = line_and_word_cells_with(&spaceless, 792.0, true, WordGap::Factor(0.2));
1719 assert_eq!(lines[0].text, "Die Verpf lichtungen");
1720 }
1721
1722 #[test]
1723 fn right_to_left_glyphs_in_visual_order_stay_one_line() {
1724 let mut g = Vec::new();
1729 let mut x = 100.0f32;
1730 for (k, word) in [
1731 "\u{0631}\u{0627}\u{0632}\u{0627}\u{0628}",
1732 "\u{0631}\u{062f}",
1733 ]
1734 .iter()
1735 .enumerate()
1736 {
1737 if k > 0 {
1738 x += 3.0;
1739 }
1740 for ch in word.chars() {
1741 g.push(glyph(ch, x, x + 5.0));
1742 x += 5.0;
1743 }
1744 }
1745 for gap in [WordGap::Adaptive, WordGap::Factor(0.2)] {
1746 let (lines, words) = line_and_word_cells_with(&g, 792.0, true, gap);
1747 assert_eq!(
1748 lines.len(),
1749 1,
1750 "{gap:?}: {:?}",
1751 lines.iter().map(|c| &c.text).collect::<Vec<_>>()
1752 );
1753 assert_eq!(words.len(), 2, "{gap:?}");
1754 }
1755 }
1756
1757 fn line_texts(glyphs: &[Glyph], zero_advance_run: bool) -> Vec<String> {
1760 line_and_word_cells_cut(glyphs, 792.0, true, WordGap::Adaptive, zero_advance_run)
1761 .0
1762 .into_iter()
1763 .map(|c| c.text)
1764 .collect()
1765 }
1766
1767 fn set(chars: &[(char, f32)]) -> Vec<Glyph> {
1769 let mut x = 100.0f32;
1770 chars
1771 .iter()
1772 .map(|&(ch, w)| {
1773 let g = glyph(ch, x, x + w);
1774 x += w;
1775 g
1776 })
1777 .collect()
1778 }
1779
1780 #[test]
1781 fn a_zero_advance_glyph_cuts_the_line_only_when_asked() {
1782 let line = |mark_advance: f32| {
1788 set(&[
1789 ('\u{0627}', 3.0),
1790 ('\u{064b}', mark_advance),
1791 ('\u{0645}', 6.0),
1792 ('\u{0626}', 3.0),
1793 ('\u{0627}', 3.0),
1794 ('\u{062f}', 5.0),
1795 ])
1796 };
1797 let whole = "\u{062f}\u{0627}\u{0626}\u{0645}\u{064b}\u{0627}";
1798 assert_eq!(line_texts(&line(0.0), false), [whole]);
1799 assert_eq!(
1800 line_texts(&line(0.0), true),
1801 ["\u{064b}\u{0627}", "\u{062f}\u{0627}\u{0626}\u{0645}"]
1802 );
1803 assert_eq!(line_texts(&line(0.5), true), [whole]);
1805 }
1806
1807 #[test]
1808 fn zero_advance_glyphs_of_other_scripts_stay_in_their_line() {
1809 let accent = set(&[
1813 ('c', 5.0),
1814 ('a', 5.0),
1815 ('f', 3.0),
1816 ('e', 5.0),
1817 ('\u{0301}', 0.0),
1818 ('s', 4.0),
1819 ]);
1820 assert_eq!(line_texts(&accent, false), ["cafe\u{0301}s"]);
1821 assert_eq!(line_texts(&accent, true), ["cafe\u{0301}", "s"]);
1822 let one_spot = set(&[('a', 0.0), ('b', 0.0), ('c', 0.0)]);
1827 assert_eq!(line_texts(&one_spot, false), ["abc"]);
1828 assert_eq!(line_texts(&one_spot, true), ["abc"]);
1829 let set_apart = vec![
1836 glyph('a', 100.0, 100.0),
1837 glyph('b', 103.0, 103.0),
1838 glyph('c', 106.0, 106.0),
1839 ];
1840 assert_eq!(line_texts(&set_apart, false), ["a b c"]);
1841 assert_eq!(line_texts(&set_apart, true), ["a", "b", "c"]);
1842 }
1843
1844 #[test]
1845 fn letter_spacing_stays_one_word_under_the_adaptive_rule() {
1846 let mut g = Vec::new();
1849 let mut x = 100.0f32;
1850 for (k, word) in ["Allgemeine", "Bestimmungen"].iter().enumerate() {
1851 if k > 0 {
1852 x += 6.0;
1853 }
1854 for ch in word.chars() {
1855 g.push(glyph(ch, x, x + 5.0));
1856 x += 5.0 + 1.5;
1857 }
1858 x -= 1.5;
1859 }
1860 let (lines, _) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1861 assert_eq!(lines[0].text, "Allgemeine Bestimmungen");
1862 }
1863
1864 fn set_line(pieces: &[(&str, f32)], y: f32) -> Vec<Glyph> {
1867 let mut g = Vec::new();
1868 let mut x = 100.0f32;
1869 for (text, gap) in pieces {
1870 x += gap;
1871 for ch in text.chars() {
1872 g.push(Glyph {
1873 b: y,
1874 t: y + 10.0,
1875 lb: y - 2.0,
1876 lt: y + 10.0,
1877 ..glyph(ch, x, x + 2.5)
1878 });
1879 x += 2.5;
1880 }
1881 }
1882 g
1883 }
1884
1885 #[test]
1886 fn one_wide_gap_does_not_raise_the_line_s_word_gap() {
1887 let g = set_line(
1892 &[
1893 ("jedoch", 0.0),
1894 ("werden", 0.8),
1895 ("weiterlaufende", 0.8),
1896 ("Quartierkosten", 8.0),
1897 ],
1898 600.0,
1899 );
1900 let (_, words) = line_and_word_cells_with(&g, 792.0, true, WordGap::Adaptive);
1901 let texts: Vec<&str> = words.iter().map(|c| c.text.as_str()).collect();
1902 assert_eq!(
1903 texts,
1904 ["jedoch", "werden", "weiterlaufende", "Quartierkosten"]
1905 );
1906 }
1907
1908 #[test]
1909 fn a_lone_word_on_a_page_that_draws_spaces_keeps_its_kerning() {
1910 let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1915 let spaced = |y| {
1916 set_line(
1917 &[
1918 ("Die", 0.0),
1919 (" ", 0.0),
1920 ("Taxonomie", 0.0),
1921 (" ", 0.0),
1922 ("gilt", 0.0),
1923 ],
1924 y,
1925 )
1926 };
1927 let mut page = lone();
1928 page.extend(spaced(600.0));
1929 page.extend(spaced(620.0));
1930 let texts = |g: &[Glyph]| {
1931 let (lines, _) = line_and_word_cells_with(g, 792.0, true, WordGap::Adaptive);
1932 lines.into_iter().map(|c| c.text).collect::<Vec<_>>()
1933 };
1934 assert!(texts(&page).contains(&"Offenlegungspflichten".to_string()));
1935 assert_eq!(texts(&lone()), ["Offenlegungspf lichten"]);
1936 }
1937
1938 #[test]
1939 fn a_line_whose_spaces_are_drawn_before_its_letters_infers_its_gap() {
1940 let mut page = set_line(&[("The", 0.0), (" ", 0.0), ("manual", 0.0)], 600.0);
1946 page.extend(set_line(
1947 &[("For", 0.0), (" ", 0.0), ("safety", 0.0)],
1948 620.0,
1949 ));
1950 let words = ["نشكرك", "على", "شراء"];
1951 let (mut spaces, mut letters) = (Vec::new(), Vec::new());
1952 let mut x = 100.0f32;
1953 for (k, word) in words.iter().rev().enumerate() {
1954 if k > 0 {
1955 spaces.push(glyph(' ', x, x + 1.7));
1956 x += 1.7;
1957 }
1958 for ch in word.chars().rev() {
1959 letters.push(glyph(ch, x, x + 5.0));
1960 x += 5.0;
1961 }
1962 }
1963 page.extend(spaces);
1964 page.extend(letters);
1965 let (lines, _) = line_and_word_cells_with(&page, 792.0, true, WordGap::Adaptive);
1966 let texts: Vec<&str> = lines.iter().map(|c| c.text.as_str()).collect();
1967 assert!(texts.contains(&"نشكرك على شراء"), "{texts:?}");
1968 }
1969
1970 #[test]
1971 fn a_lone_word_beside_another_line_s_space_keeps_its_kerning() {
1972 let spaced = |y| {
1979 set_line(
1980 &[
1981 ("Die", 0.0),
1982 (" ", 0.0),
1983 ("Taxonomie", 0.0),
1984 (" ", 0.0),
1985 ("gilt", 0.0),
1986 ],
1987 y,
1988 )
1989 };
1990 let lone = || set_line(&[("Offenlegungspf", 0.0), ("lichten", 0.8)], 500.0);
1992 let space = |l: f32, r: f32, y: f32| Glyph {
1993 b: y,
1994 t: y + 10.0,
1995 lb: y - 2.0,
1996 lt: y + 10.0,
1997 ..glyph(' ', l, r)
1998 };
1999 let line_with = |stray: Glyph| {
2000 let mut page = spaced(600.0);
2001 page.extend(spaced(620.0));
2002 page.push(stray);
2003 page.extend(lone());
2004 let (lines, _) = line_and_word_cells_with(&page, 792.0, true, WordGap::Adaptive);
2005 lines
2006 .into_iter()
2007 .map(|c| c.text)
2008 .find(|t| t.starts_with("Offen"))
2009 .expect("the lone word's line")
2010 };
2011 assert_eq!(
2012 line_with(space(154.0, 155.7, 500.0)),
2013 "Offenlegungspflichten"
2014 );
2015 assert_eq!(
2016 line_with(space(135.0, 135.8, 494.0)),
2017 "Offenlegungspflichten"
2018 );
2019 assert_eq!(
2020 line_with(space(135.0, 135.8, 500.0)),
2021 "Offenlegungspf lichten"
2022 );
2023 }
2024
2025 #[test]
2026 fn a_space_drawn_apart_is_judged_on_both_glyphs_beside_it() {
2027 let mark = Glyph {
2031 lb: 104.0,
2032 ..glyph('\u{064b}', 100.0, 103.0)
2033 };
2034 let cells = build_cells(
2035 &[
2036 mark,
2037 glyph('\u{0644}', 105.0, 110.0),
2038 glyph(' ', 103.2, 104.8),
2039 ],
2040 true,
2041 );
2042 let run: Vec<RunCell> = cells[..2].iter().map(RunCell::new).collect();
2043 let spaces = [(0.5 * (cells[2].b_b + cells[2].b_t), &cells[2])];
2044 assert!(spaces_drawn_apart(&run, &spaces));
2045 }
2046
2047 #[test]
2048 fn word_gap_spellings() {
2049 assert_eq!(WordGap::parse("adaptive"), Ok(WordGap::Adaptive));
2050 assert_eq!(WordGap::parse(" Legacy "), Ok(WordGap::Legacy));
2051 assert_eq!(WordGap::parse("0.2"), Ok(WordGap::Factor(0.2)));
2052 for bad in ["0", "-1", "5", "nan", "wide"] {
2053 assert!(WordGap::parse(bad).is_err(), "{bad}");
2054 }
2055 }
2056}