991 lines
34 KiB
Odin
991 lines
34 KiB
Odin
package pdf
|
|
|
|
import "core:math"
|
|
import "core:mem"
|
|
import "core:slice"
|
|
import "core:strings"
|
|
import "core:unicode/utf8"
|
|
|
|
// The text-extraction Device (ISO 32000-2, 9.4.4 for the geometry it undoes).
|
|
//
|
|
// A PDF has no notion of a word, a line or a paragraph. It has glyphs at
|
|
// coordinates, emitted in whatever order suited the producer -- every column
|
|
// of a table first, or a whole page of body text with each word positioned
|
|
// individually and not one space character in the file. Reconstructing reading
|
|
// order from that is the entire job of this file; drawing is somebody else's.
|
|
//
|
|
// WHAT ARRIVES
|
|
//
|
|
// One `Text` per text-showing operator, each item carrying `trm`, the complete
|
|
// glyph-space-to-device-space matrix, and `unicode`, which font.odin has
|
|
// already resolved through /ToUnicode, the glyph name and the CMap. Three
|
|
// hooks feed the same collector: `fill_text`, `stroke_text` (render mode 1 is
|
|
// real text) and `ignore_text` -- mode 3 is invisible, and invisible is
|
|
// exactly how a scanned page stores its OCR layer, which is the text a user
|
|
// most wants. `clip_text` feeds it too, so that mode 7 is not lost; a run that
|
|
// arrives twice because its render mode both fills and clips is recognised and
|
|
// counted once.
|
|
//
|
|
// One glyph can stand for several characters -- "ffi" is one glyph and three
|
|
// letters -- and `unicode`, being one rune, reports the first. The producer
|
|
// said the rest in /ToUnicode, so this file asks for it: without that,
|
|
// "Specification" extracts as "Specifcation", which is what the corpus does.
|
|
//
|
|
// HOW A GLYPH IS PLACED
|
|
//
|
|
// `trm` maps glyph space, which is the font program's own unit system, to
|
|
// device space. Undoing the font matrix,
|
|
//
|
|
// T = font_matrix(f)^-1 * trm
|
|
//
|
|
// gives text space to device space, and that is the frame everything here
|
|
// works in: T's translation is the pen, |(T.a, T.b)| is one em along the
|
|
// writing direction (with the horizontal scale folded in, which is what
|
|
// advances are measured against) and |(T.c, T.d)| is one em vertically, which
|
|
// is the font size a caller wants reported. Deriving both from the matrix is
|
|
// what makes rotated, skewed and mirrored text come out in the right order
|
|
// without a special case: "left to right" is along T's x axis, never along
|
|
// device x.
|
|
//
|
|
// A glyph's advance is taken from the Font rather than from `Text_Item.advance`
|
|
// on purpose. The interpreter positioned the next glyph with the width out of
|
|
// that same Font, so measuring against it is self-consistent by construction:
|
|
// a font whose /Widths are all zero piles its glyphs on one spot and yields no
|
|
// gaps, instead of yielding a gap between every pair.
|
|
//
|
|
// THE THRESHOLDS, AND WHY THEY ARE WHAT THEY ARE
|
|
//
|
|
// All of them are fractions of the em, so they hold at any font size.
|
|
//
|
|
// space 0.20 A gap wider than this becomes a space. Kerning pairs
|
|
// are tightenings -- negative gaps -- and the widest
|
|
// positive kern in a real font is around 0.05 em; a
|
|
// word space is 0.25 to 0.33 em. 0.20 sits in the empty
|
|
// band between the two.
|
|
// tracking cap 0.15 Letter-spacing (Tc) widens every gap in a run
|
|
// equally. The smallest gap in a run is subtracted from
|
|
// all of them, capped here so that a table row emitted
|
|
// as one widely-spaced TJ keeps its spaces.
|
|
// same line 0.35 Baseline separation, incrementally, and 0.80 in
|
|
// total, so a subscript joins its line and two lines of
|
|
// text never merge -- leading below a third of the font
|
|
// size does not exist.
|
|
// new block 1.60 Baseline step that ends a paragraph. Normal leading
|
|
// is 1.0 to 1.5 em.
|
|
// duplicate 0.10 The same character re-drawn within a tenth of an em
|
|
// is a producer faking bold by overprinting, not a
|
|
// repeated letter.
|
|
//
|
|
// Nothing here is a Document operation, so there is no `add_repair` to call;
|
|
// damage shows up as `Text_Device.truncated` or is simply skipped.
|
|
|
|
// Gap, as a fraction of the em, that becomes a space.
|
|
@(private)
|
|
TEXT_SPACE_EM :: 0.20
|
|
// Most letter-spacing that will be compensated away, in ems.
|
|
@(private)
|
|
TEXT_TRACK_EM :: 0.15
|
|
// Smallest tracking worth compensating for, in ems.
|
|
@(private)
|
|
TEXT_TRACK_MIN_EM :: 0.05
|
|
// Adjacent pairs a run needs before its tracking is estimated at all.
|
|
@(private)
|
|
TEXT_TRACK_PAIRS :: 3
|
|
// Baseline separation that keeps two glyphs on one line: step to step, and
|
|
// over the whole line.
|
|
@(private)
|
|
TEXT_LINE_EM :: 0.35
|
|
@(private)
|
|
TEXT_LINE_SPREAD_EM :: 0.80
|
|
// Baseline step that starts a new block.
|
|
@(private)
|
|
TEXT_BLOCK_EM :: 1.60
|
|
// Distance within which a repeat of the same character is fake bold.
|
|
@(private)
|
|
TEXT_DUP_EM :: 0.10
|
|
// Em box used for a glyph's rectangle, in the absence of real per-glyph
|
|
// bounding boxes: a typical ascent and descent.
|
|
@(private)
|
|
TEXT_ASCENT_EM :: 0.80
|
|
@(private)
|
|
TEXT_DESCENT_EM :: 0.20
|
|
// Glyphs kept from one page. A page of dense CJK holds a few thousand; this
|
|
// is three orders of magnitude above any real page and bounds the memory a
|
|
// hostile content stream can make us hold.
|
|
@(private)
|
|
MAX_TEXT_GLYPHS :: 1 << 18
|
|
// Bytes of /ToUnicode text one glyph may stand for. A ligature is three or
|
|
// four; a producer that maps a glyph to a paragraph is not describing a glyph.
|
|
@(private)
|
|
MAX_TEXT_UNICODE_BYTES :: 64
|
|
// An advance is clamped to this many ems. /Widths is attacker-controlled and
|
|
// font.odin's own clamp still allows 10 000 ems.
|
|
@(private)
|
|
MAX_TEXT_ADVANCE_EM :: 100.0
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Structured output
|
|
// ---------------------------------------------------------------------------
|
|
|
|
// Text_Span is a run of characters on one line in one font at one size.
|
|
// `rect` is in device space -- the space the CTM handed to the interpreter
|
|
// maps into -- and covers the em boxes of the span's glyphs.
|
|
Text_Span :: struct {
|
|
text: string,
|
|
rect: Rect,
|
|
font: ^Font,
|
|
size: f64,
|
|
}
|
|
|
|
// Text_Line is one baseline's worth of spans, ordered along the writing
|
|
// direction.
|
|
Text_Line :: struct {
|
|
spans: []Text_Span,
|
|
rect: Rect,
|
|
}
|
|
|
|
// Text_Block is a run of lines with no unusual vertical gap between them: a
|
|
// paragraph, as far as coordinates can tell.
|
|
Text_Block :: struct {
|
|
lines: []Text_Line,
|
|
rect: Rect,
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// The device
|
|
// ---------------------------------------------------------------------------
|
|
|
|
// Text_Glyph is one placed character, in device space and in the frame of its
|
|
// own writing direction.
|
|
@(private)
|
|
Text_Glyph :: struct {
|
|
// Pen position, and where the pen lands after this glyph's advance.
|
|
pen, end: Point,
|
|
// Unit writing direction, unit "up" (the em's y axis), and the unit normal
|
|
// pointing the way successive lines advance.
|
|
dir, up, n: Point,
|
|
// One em along the writing direction, and one em vertically.
|
|
em, size: f64,
|
|
// pen projected on n and on dir, in the canonical frame of the glyph's
|
|
// angle bucket. Filled in at layout time.
|
|
u, v: f64,
|
|
r: rune,
|
|
// The whole of what the glyph stands for, when that is more than one code
|
|
// point; empty otherwise, and `r` is the character. A view into the font's
|
|
// /ToUnicode CMap, which the Document owns.
|
|
text: string,
|
|
font: ^Font,
|
|
// Emission order: the last tiebreak in every sort, so the result is
|
|
// deterministic, and the order in which equally-placed glyphs are joined.
|
|
seq: int,
|
|
// Writing angle in whole degrees, 0..359, and its rank in reading order.
|
|
bucket: int,
|
|
border: int,
|
|
}
|
|
|
|
// Text_Run_Sig identifies a glyph run closely enough to recognise the same run
|
|
// arriving twice. Render mode 2 fills and strokes, and modes 4 to 6 also clip,
|
|
// so a device that implements every text hook sees one run two or three times.
|
|
@(private)
|
|
Text_Run_Sig :: struct {
|
|
count: int,
|
|
font: ^Font,
|
|
first, last: Matrix,
|
|
r0, r1: rune,
|
|
}
|
|
|
|
Text_Device :: struct {
|
|
dev: Device,
|
|
allocator: mem.Allocator,
|
|
glyphs: [dynamic]Text_Glyph,
|
|
seq: int,
|
|
// Set when MAX_TEXT_GLYPHS was reached and glyphs were dropped.
|
|
truncated: bool,
|
|
sig: Text_Run_Sig,
|
|
have_sig: bool,
|
|
}
|
|
|
|
// text_device_make builds a device that collects text instead of pixels.
|
|
// Everything it allocates comes from `allocator` and is released by
|
|
// text_device_destroy.
|
|
text_device_make :: proc(allocator := context.allocator) -> (^Text_Device, Error) {
|
|
td, err := new(Text_Device, allocator)
|
|
if err != nil || td == nil {
|
|
return nil, .Out_Of_Memory
|
|
}
|
|
td.allocator = allocator
|
|
gs, gerr := make([dynamic]Text_Glyph, 0, 256, allocator)
|
|
if gerr != nil {
|
|
free(td, allocator)
|
|
return nil, .Out_Of_Memory
|
|
}
|
|
td.glyphs = gs
|
|
|
|
td.dev.user = td
|
|
// Text sits on top of photographs and gradients constantly, and decoding
|
|
// either to extract it is pure waste. No outlines either: this device
|
|
// never draws a glyph, only places it -- which for a Type 3 font also
|
|
// spares the interpreter running one content stream per character. And no
|
|
// tiling: a pattern cell is replayed once per placement, so a watermark
|
|
// lattice with a word in it arrives once per tile.
|
|
//
|
|
// The transparency hooks are deliberately nil rather than suppressing
|
|
// what is drawn between them. Text with a gradient fill is drawn INTO a
|
|
// luminosity soft mask and the colour painted through it, so a device
|
|
// that ignored mask content would lose exactly that text.
|
|
td.dev.hints = {.Ignore_Image, .Ignore_Shade, .No_Glyph_Outlines, .No_Tiling}
|
|
td.dev.fill_text = text_dev_fill_text
|
|
td.dev.stroke_text = text_dev_stroke_text
|
|
td.dev.ignore_text = text_dev_ignore_text
|
|
td.dev.clip_text = text_dev_clip_text
|
|
return td, .None
|
|
}
|
|
|
|
text_device_destroy :: proc(td: ^Text_Device) {
|
|
if td == nil {
|
|
return
|
|
}
|
|
allocator := td.allocator
|
|
delete(td.glyphs)
|
|
td^ = {}
|
|
free(td, allocator)
|
|
}
|
|
|
|
// text_device_as_device hands the interpreter the vtable. The Device is
|
|
// embedded in the Text_Device, so the two share a lifetime.
|
|
text_device_as_device :: proc(td: ^Text_Device) -> ^Device {
|
|
if td == nil {
|
|
return nil
|
|
}
|
|
return &td.dev
|
|
}
|
|
|
|
@(private)
|
|
text_dev_self :: proc(dev: ^Device) -> ^Text_Device {
|
|
if dev == nil {
|
|
return nil
|
|
}
|
|
return cast(^Text_Device)dev.user
|
|
}
|
|
|
|
@(private)
|
|
text_dev_fill_text :: proc(dev: ^Device, text: ^Text, ctm: Matrix, paint: Paint) {
|
|
text_dev_collect(text_dev_self(dev), text)
|
|
}
|
|
|
|
@(private)
|
|
text_dev_stroke_text :: proc(dev: ^Device, text: ^Text, stroke: ^Stroke_State, ctm: Matrix, paint: Paint) {
|
|
text_dev_collect(text_dev_self(dev), text)
|
|
}
|
|
|
|
@(private)
|
|
text_dev_ignore_text :: proc(dev: ^Device, text: ^Text, ctm: Matrix) {
|
|
text_dev_collect(text_dev_self(dev), text)
|
|
}
|
|
|
|
// clip_text is implemented so that render mode 7 -- text used only as a clip,
|
|
// which is how some producers letter shapes over an image -- is still
|
|
// extracted. It pushes no clip: this device has no clip stack, and pop_clip
|
|
// stays nil.
|
|
@(private)
|
|
text_dev_clip_text :: proc(dev: ^Device, text: ^Text, ctm: Matrix) {
|
|
text_dev_collect(text_dev_self(dev), text)
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Collecting
|
|
// ---------------------------------------------------------------------------
|
|
|
|
@(private)
|
|
text_run_sig :: proc(text: ^Text) -> (sig: Text_Run_Sig) {
|
|
n := len(text.items)
|
|
sig.count = n
|
|
sig.font = text.font
|
|
if n > 0 {
|
|
sig.first = text.items[0].trm
|
|
sig.last = text.items[n - 1].trm
|
|
sig.r0 = text.items[0].unicode
|
|
sig.r1 = text.items[n - 1].unicode
|
|
}
|
|
return
|
|
}
|
|
|
|
@(private)
|
|
text_dev_collect :: proc(td: ^Text_Device, text: ^Text) {
|
|
if td == nil || text == nil || len(text.items) == 0 {
|
|
return
|
|
}
|
|
// The same run reaching us twice is the render mode drawing it twice, not
|
|
// the page saying it twice: identical glyphs at identical positions are
|
|
// one piece of text however many times they are inked.
|
|
sig := text_run_sig(text)
|
|
if td.have_sig && sig == td.sig {
|
|
return
|
|
}
|
|
td.have_sig = true
|
|
td.sig = sig
|
|
|
|
f := text.font
|
|
fm := font_matrix(f)
|
|
fm_inv, inv_ok := matrix_invert(fm)
|
|
if !inv_ok {
|
|
// A singular font matrix draws nothing, but the text is still there to
|
|
// be read; assume the 1/1000 glyph space everything but Type3 uses.
|
|
fm_inv = Matrix{1000, 0, 0, 1000, 0, 0}
|
|
}
|
|
vertical := text.wmode == 1
|
|
|
|
start := len(td.glyphs)
|
|
for &it in text.items {
|
|
if len(td.glyphs) >= MAX_TEXT_GLYPHS {
|
|
td.truncated = true
|
|
break
|
|
}
|
|
if !matrix_is_finite(it.trm) {
|
|
continue
|
|
}
|
|
t := matrix_mul(fm_inv, it.trm)
|
|
if !matrix_is_finite(t) {
|
|
continue
|
|
}
|
|
|
|
g: Text_Glyph
|
|
g.pen = Point{t.e, t.f}
|
|
hvec := Point{t.a, t.b}
|
|
vvec := Point{t.c, t.d}
|
|
hlen := text_len(hvec)
|
|
vlen := text_len(vvec)
|
|
if hlen < 1e-9 && vlen < 1e-9 {
|
|
// A matrix that collapses to a point places nothing anywhere.
|
|
continue
|
|
}
|
|
// One axis flattened still positions text, so the surviving axis
|
|
// stands in for the other: it gives the missing size, and turning it
|
|
// a quarter turn gives the missing direction. Upright text has the
|
|
// x axis to the right and the y axis up the page, which in a y-down
|
|
// device space is (1, 0) and (0, -1) -- that is the turn taken here.
|
|
hdir := hlen > 1e-9 ? Point{hvec.x / hlen, hvec.y / hlen} : Point{}
|
|
up := vlen > 1e-9 ? Point{vvec.x / vlen, vvec.y / vlen} : Point{}
|
|
if hlen < 1e-9 {
|
|
hdir = Point{-up.y, up.x}
|
|
hlen = vlen
|
|
} else if vlen < 1e-9 {
|
|
up = Point{hdir.y, -hdir.x}
|
|
vlen = hlen
|
|
}
|
|
if vertical {
|
|
// A vertical font writes down text space's -y, and its columns
|
|
// advance along -x (9.7.4.3).
|
|
g.dir = Point{-up.x, -up.y}
|
|
g.n = text_perp_towards(g.dir, Point{-hdir.x, -hdir.y})
|
|
g.em = vlen
|
|
} else {
|
|
g.dir = hdir
|
|
g.n = text_perp_towards(g.dir, Point{-up.x, -up.y})
|
|
g.em = hlen
|
|
}
|
|
g.up = up
|
|
g.size = vlen
|
|
g.font = f
|
|
g.r = text_rune_of(it.unicode)
|
|
g.text = text_glyph_text(f, &it)
|
|
|
|
adv := text_em_advance(f, &it, vertical) * g.em
|
|
g.end = Point{g.pen.x + g.dir.x * adv, g.pen.y + g.dir.y * adv}
|
|
if !is_finite(g.end.x) || !is_finite(g.end.y) {
|
|
// An advance that overflows says nothing about where the next
|
|
// glyph starts; a zero-width glyph is the honest reading.
|
|
g.end = g.pen
|
|
}
|
|
|
|
deg := math.atan2(g.dir.y, g.dir.x) * 180 / math.PI
|
|
if !is_finite(deg) {
|
|
continue
|
|
}
|
|
b := int(math.round(deg)) % 360
|
|
if b < 0 { b += 360 }
|
|
g.bucket = b
|
|
|
|
g.seq = td.seq
|
|
td.seq += 1
|
|
append(&td.glyphs, g)
|
|
}
|
|
|
|
text_run_track(td.glyphs[start:])
|
|
}
|
|
|
|
// text_run_track compensates for letter-spacing. Tc widens the gap after every
|
|
// glyph in a run by the same amount, which at 0.2 em and up would otherwise
|
|
// put a space between every pair of letters in a tracked heading. The smallest
|
|
// gap in the run is the one least likely to be a word break, so it is taken as
|
|
// the tracking and removed from all of them.
|
|
//
|
|
// The cap is what keeps this safe: a table row emitted as one TJ with huge
|
|
// gaps between the cells has a large "smallest gap", and without the cap the
|
|
// spaces between its cells would be compensated away.
|
|
@(private)
|
|
text_run_track :: proc(gs: []Text_Glyph) {
|
|
if len(gs) < TEXT_TRACK_PAIRS + 1 {
|
|
return
|
|
}
|
|
least := math.INF_F64
|
|
pairs := 0
|
|
for i in 0 ..< len(gs) - 1 {
|
|
a := &gs[i]
|
|
b := &gs[i + 1]
|
|
if a.em <= 0 || a.bucket != b.bucket {
|
|
continue
|
|
}
|
|
d := Point{b.pen.x - a.end.x, b.pen.y - a.end.y}
|
|
// Only pairs that sit on one baseline say anything about tracking.
|
|
if abs(d.x * a.n.x + d.y * a.n.y) > TEXT_LINE_EM * a.em {
|
|
continue
|
|
}
|
|
gap := (d.x * a.dir.x + d.y * a.dir.y) / a.em
|
|
least = min(least, gap)
|
|
pairs += 1
|
|
}
|
|
if pairs < TEXT_TRACK_PAIRS || !is_finite(least) || least < TEXT_TRACK_MIN_EM {
|
|
return
|
|
}
|
|
track := min(least, TEXT_TRACK_EM)
|
|
for &g in gs {
|
|
g.end.x += g.dir.x * track * g.em
|
|
g.end.y += g.dir.y * track * g.em
|
|
}
|
|
}
|
|
|
|
// text_em_advance is the glyph's advance in text space, where 1 is an em.
|
|
@(private)
|
|
text_em_advance :: proc(f: ^Font, it: ^Text_Item, vertical: bool) -> f64 {
|
|
if f == nil {
|
|
return 0
|
|
}
|
|
w: f64
|
|
if f.kind == .Type0 {
|
|
w = font_cid_width(f, it.cid)
|
|
if vertical {
|
|
w1y, _, _ := font_cid_vmetric(f, it.cid, w)
|
|
// The writing direction points along text space -y, so the
|
|
// displacement -- negative by convention -- is a positive distance
|
|
// along it.
|
|
return is_finite(w1y) ? text_clamp_em(-w1y / 1000) : 0
|
|
}
|
|
} else if it.code < FONT_CODES {
|
|
w = f.code_width[it.code]
|
|
}
|
|
if !is_finite(w) {
|
|
return 0
|
|
}
|
|
if f.kind == .Type3 {
|
|
// A Type3 width is in the font's own glyph space and only its
|
|
// /FontMatrix says how big that is (9.6.4).
|
|
v := transform_vector(font_matrix(f), Point{w, 0})
|
|
return is_finite(v.x) ? text_clamp_em(v.x) : 0
|
|
}
|
|
// Every other width in a PDF is thousandths of text space (9.6.2.2).
|
|
return text_clamp_em(w / 1000)
|
|
}
|
|
|
|
@(private)
|
|
text_clamp_em :: proc(x: f64) -> f64 {
|
|
return clamp(x, -MAX_TEXT_ADVANCE_EM, MAX_TEXT_ADVANCE_EM)
|
|
}
|
|
|
|
// text_rune_of maps what the font resolved to a character to put in the
|
|
// output. A glyph the font offers no Unicode for becomes U+FFFD: dropping it
|
|
// silently would join the words either side of it, and the caller cannot tell
|
|
// that happened.
|
|
@(private)
|
|
text_rune_of :: proc(r: rune) -> rune {
|
|
switch {
|
|
case r <= 0:
|
|
// font.odin uses -1 for "none"; 0 is not a character a glyph maps to.
|
|
return 0xFFFD
|
|
case r < 0x20:
|
|
// A control code is not a glyph. Producers emit them through a broken
|
|
// /ToUnicode; a space keeps the line structure this file imposes.
|
|
return ' '
|
|
case r > 0x10FFFF, r >= 0xD800 && r <= 0xDFFF:
|
|
return 0xFFFD
|
|
}
|
|
return r
|
|
}
|
|
|
|
// text_glyph_text is the several code points a glyph stands for, when it
|
|
// stands for more than one.
|
|
//
|
|
// Font_Code.unicode is a single rune -- the frozen shape of the struct -- so
|
|
// an "ffi" ligature arrives as 'f' and the word loses two letters. That is not
|
|
// font.odin being wrong: its own tests say the first character is what the
|
|
// field reports and "the whole string is cmap_lookup_text's to give". This is
|
|
// the caller asking for the rest of it.
|
|
//
|
|
// The result is only used when its first code point is the one font.odin
|
|
// chose. A disagreement means /ToUnicode was not the route it took -- a
|
|
// mapping it rejected as malformed, say -- and its answer wins.
|
|
@(private)
|
|
text_glyph_text :: proc(f: ^Font, it: ^Text_Item) -> string {
|
|
if f == nil || f.to_unicode == nil || it.unicode < 0 {
|
|
return ""
|
|
}
|
|
txt, ok := cmap_lookup_text(f.to_unicode, it.code)
|
|
if !ok || len(txt) < 2 || len(txt) > MAX_TEXT_UNICODE_BYTES {
|
|
return ""
|
|
}
|
|
r0, size := utf8.decode_rune_in_string(txt)
|
|
if r0 != it.unicode || size >= len(txt) {
|
|
return ""
|
|
}
|
|
return txt
|
|
}
|
|
|
|
@(private)
|
|
text_len :: proc(p: Point) -> f64 {
|
|
return math.sqrt(p.x * p.x + p.y * p.y)
|
|
}
|
|
|
|
// text_perp_towards is the unit normal of `dir`, turned to agree with `want`.
|
|
// Taking the sign from a vector out of the same matrix is what keeps mirrored
|
|
// text -- and a page whose base matrix flips y -- ordered the right way round.
|
|
@(private)
|
|
text_perp_towards :: proc(dir, want: Point) -> Point {
|
|
p := Point{-dir.y, dir.x}
|
|
if p.x * want.x + p.y * want.y < 0 {
|
|
return Point{-p.x, -p.y}
|
|
}
|
|
return p
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Layout: glyphs to lines to blocks
|
|
// ---------------------------------------------------------------------------
|
|
|
|
@(private)
|
|
Text_Layout_Line :: struct {
|
|
first, last: int, // half-open range of glyphs
|
|
u: f64, // baseline, in the bucket's frame
|
|
size: f64, // largest em on the line
|
|
dir, n: Point,
|
|
border: int,
|
|
block: int,
|
|
}
|
|
|
|
@(private)
|
|
Text_Layout :: struct {
|
|
glyphs: []Text_Glyph,
|
|
lines: [dynamic]Text_Layout_Line,
|
|
blocks: int,
|
|
allocator: mem.Allocator,
|
|
}
|
|
|
|
@(private)
|
|
text_layout_destroy :: proc(lay: ^Text_Layout) {
|
|
if lay == nil {
|
|
return
|
|
}
|
|
delete(lay.glyphs, lay.allocator)
|
|
delete(lay.lines)
|
|
lay^ = {}
|
|
}
|
|
|
|
@(private)
|
|
Text_Bucket_Rank :: struct {
|
|
seq, bucket: int,
|
|
}
|
|
|
|
@(private)
|
|
text_layout :: proc(td: ^Text_Device, allocator: mem.Allocator) -> (lay: Text_Layout) {
|
|
lay.allocator = allocator
|
|
if td == nil || len(td.glyphs) == 0 {
|
|
return
|
|
}
|
|
gs, err := make([]Text_Glyph, len(td.glyphs), allocator)
|
|
if err != nil {
|
|
return
|
|
}
|
|
copy(gs, td.glyphs[:])
|
|
lay.glyphs = gs
|
|
|
|
// One canonical frame per whole degree of writing angle. Projecting every
|
|
// glyph in a bucket on one frame -- rather than each on its own -- is what
|
|
// makes the baseline coordinate comparable: half a degree of disagreement
|
|
// is seven points of drift across a line of text, which is a whole line
|
|
// height of error.
|
|
first_seq: [360]int
|
|
dirs, norms: [360]Point
|
|
for i in 0 ..< 360 {
|
|
first_seq[i] = max(int)
|
|
}
|
|
for g in gs {
|
|
if g.seq < first_seq[g.bucket] {
|
|
first_seq[g.bucket] = g.seq
|
|
dirs[g.bucket] = g.dir
|
|
norms[g.bucket] = g.n
|
|
}
|
|
}
|
|
// Buckets are read in the order they were first drawn, so that a rotated
|
|
// caption on an upright page lands where the producer put it rather than
|
|
// at an angle-sorted position nobody chose.
|
|
ranks: [360]Text_Bucket_Rank
|
|
nranks := 0
|
|
for i in 0 ..< 360 {
|
|
if first_seq[i] != max(int) {
|
|
ranks[nranks] = {first_seq[i], i}
|
|
nranks += 1
|
|
}
|
|
}
|
|
slice.sort_by(ranks[:nranks], proc(a, b: Text_Bucket_Rank) -> bool {
|
|
return a.seq < b.seq
|
|
})
|
|
order: [360]int
|
|
for e, i in ranks[:nranks] {
|
|
order[e.bucket] = i
|
|
}
|
|
for &g in gs {
|
|
d := dirs[g.bucket]
|
|
n := norms[g.bucket]
|
|
g.u = g.pen.x * n.x + g.pen.y * n.y
|
|
g.v = g.pen.x * d.x + g.pen.y * d.y
|
|
g.border = order[g.bucket]
|
|
}
|
|
text_layout_rescale(gs)
|
|
|
|
slice.sort_by(gs, proc(a, b: Text_Glyph) -> bool {
|
|
if a.border != b.border { return a.border < b.border }
|
|
if a.u != b.u { return a.u < b.u }
|
|
if a.v != b.v { return a.v < b.v }
|
|
return a.seq < b.seq
|
|
})
|
|
|
|
lay.lines = make([dynamic]Text_Layout_Line, 0, 32, allocator)
|
|
i := 0
|
|
for i < len(gs) {
|
|
anchor := gs[i].u
|
|
prev := gs[i].u
|
|
size := gs[i].size
|
|
j := i + 1
|
|
for j < len(gs) {
|
|
g := gs[j]
|
|
if g.border != gs[i].border {
|
|
break
|
|
}
|
|
limit := max(size, g.size)
|
|
if g.u - prev > TEXT_LINE_EM * limit || g.u - anchor > TEXT_LINE_SPREAD_EM * limit {
|
|
break
|
|
}
|
|
prev = g.u
|
|
size = max(size, g.size)
|
|
j += 1
|
|
}
|
|
// Reading order along the baseline. The emission order is the
|
|
// tiebreak, so glyphs stacked at one point keep the order they were
|
|
// drawn in.
|
|
slice.sort_by(gs[i:j], proc(a, b: Text_Glyph) -> bool {
|
|
if a.v != b.v { return a.v < b.v }
|
|
return a.seq < b.seq
|
|
})
|
|
append(&lay.lines, Text_Layout_Line{
|
|
first = i,
|
|
last = j,
|
|
u = anchor,
|
|
size = size,
|
|
dir = dirs[gs[i].bucket],
|
|
n = norms[gs[i].bucket],
|
|
border = gs[i].border,
|
|
})
|
|
i = j
|
|
}
|
|
|
|
nblocks := 0
|
|
for &ln, k in lay.lines {
|
|
if k > 0 {
|
|
p := lay.lines[k - 1]
|
|
if ln.border != p.border || ln.u - p.u > TEXT_BLOCK_EM * max(ln.size, p.size) {
|
|
nblocks += 1
|
|
}
|
|
}
|
|
ln.block = nblocks
|
|
}
|
|
lay.blocks = len(lay.lines) > 0 ? nblocks + 1 : 0
|
|
return
|
|
}
|
|
|
|
// text_layout_rescale is a guard, not a feature. Text_Item.trm is contracted
|
|
// to map glyph space to device space, and this file divides the font matrix
|
|
// back out of it to recover text space. A producer of Text_Items that handed
|
|
// us the text-space matrix instead would leave every em a thousand times too
|
|
// large, and a thousand-point em turns a page of text into one unreadable
|
|
// line with no spaces in it.
|
|
//
|
|
// That is detectable without ambiguity: if every glyph on the page fits inside
|
|
// a small fraction of a single em, the matrices cannot mean what they claim.
|
|
// Only a page with enough glyphs to be sure is touched, and a page that really
|
|
// does stack all its text on one spot has nothing to lose either way.
|
|
@(private)
|
|
text_layout_rescale :: proc(gs: []Text_Glyph) {
|
|
if len(gs) < 16 {
|
|
return
|
|
}
|
|
lo := gs[0].pen
|
|
hi := gs[0].pen
|
|
em := 0.0
|
|
for g in gs {
|
|
lo.x = min(lo.x, g.pen.x); lo.y = min(lo.y, g.pen.y)
|
|
hi.x = max(hi.x, g.pen.x); hi.y = max(hi.y, g.pen.y)
|
|
em = max(em, g.em, g.size)
|
|
}
|
|
extent := text_len(Point{hi.x - lo.x, hi.y - lo.y})
|
|
if em <= 20 * extent {
|
|
return
|
|
}
|
|
for &g in gs {
|
|
s := matrix_expansion(font_matrix(g.font))
|
|
if !is_finite(s) || s <= 0 || s >= 1 {
|
|
continue
|
|
}
|
|
g.em *= s
|
|
g.size *= s
|
|
g.end.x = g.pen.x + (g.end.x - g.pen.x) * s
|
|
g.end.y = g.pen.y + (g.end.y - g.pen.y) * s
|
|
}
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Rendering the layout
|
|
// ---------------------------------------------------------------------------
|
|
|
|
@(private)
|
|
Text_Rect_Acc :: struct {
|
|
r: Rect,
|
|
have: bool,
|
|
}
|
|
|
|
@(private)
|
|
text_acc_point :: proc(acc: ^Text_Rect_Acc, p: Point) {
|
|
if !is_finite(p.x) || !is_finite(p.y) {
|
|
return
|
|
}
|
|
if !acc.have {
|
|
acc.r = Rect{p.x, p.y, p.x, p.y}
|
|
acc.have = true
|
|
return
|
|
}
|
|
acc.r.x0 = min(acc.r.x0, p.x)
|
|
acc.r.y0 = min(acc.r.y0, p.y)
|
|
acc.r.x1 = max(acc.r.x1, p.x)
|
|
acc.r.y1 = max(acc.r.y1, p.y)
|
|
}
|
|
|
|
@(private)
|
|
text_acc_rect :: proc(acc: ^Text_Rect_Acc, r: Rect, have: bool) {
|
|
if !have {
|
|
return
|
|
}
|
|
text_acc_point(acc, Point{r.x0, r.y0})
|
|
text_acc_point(acc, Point{r.x1, r.y1})
|
|
}
|
|
|
|
// text_glyph_box is the em box the glyph occupies, as a device-space
|
|
// rectangle. Real per-glyph bounding boxes would need the outlines this device
|
|
// asks the interpreter not to load, and a selection rectangle wants the line's
|
|
// full height anyway.
|
|
@(private)
|
|
text_glyph_box :: proc(g: ^Text_Glyph, acc: ^Text_Rect_Acc) {
|
|
a := g.up * (TEXT_ASCENT_EM * g.size)
|
|
d := g.up * (TEXT_DESCENT_EM * g.size)
|
|
text_acc_point(acc, g.pen + a)
|
|
text_acc_point(acc, g.pen - d)
|
|
text_acc_point(acc, g.end + a)
|
|
text_acc_point(acc, g.end - d)
|
|
}
|
|
|
|
// text_device_blocks returns the page's text as blocks of lines of spans.
|
|
//
|
|
// The blocks, the lines, the spans and every string in them are allocated with
|
|
// `allocator` and belong to the caller: release them with text_blocks_destroy.
|
|
// Calling this twice is fine; nothing is consumed.
|
|
text_device_blocks :: proc(td: ^Text_Device, allocator := context.allocator) -> []Text_Block {
|
|
if td == nil {
|
|
return nil
|
|
}
|
|
lay := text_layout(td, td.allocator)
|
|
defer text_layout_destroy(&lay)
|
|
if len(lay.lines) == 0 {
|
|
return nil
|
|
}
|
|
|
|
blocks := make([dynamic]Text_Block, 0, lay.blocks, allocator)
|
|
lines := make([dynamic]Text_Line, 0, 8, allocator)
|
|
spans := make([dynamic]Text_Span, 0, 4, allocator)
|
|
sb := strings.builder_make(td.allocator)
|
|
defer strings.builder_destroy(&sb)
|
|
|
|
block_acc: Text_Rect_Acc
|
|
line_acc: Text_Rect_Acc
|
|
span_acc: Text_Rect_Acc
|
|
|
|
cur_block := 0
|
|
for ln, li in lay.lines {
|
|
if li > 0 && ln.block != cur_block {
|
|
if len(lines) > 0 {
|
|
append(&blocks, Text_Block{lines = slice.clone(lines[:], allocator), rect = block_acc.r})
|
|
clear(&lines)
|
|
}
|
|
block_acc = {}
|
|
cur_block = ln.block
|
|
}
|
|
|
|
clear(&spans)
|
|
line_acc = {}
|
|
span_acc = {}
|
|
strings.builder_reset(&sb)
|
|
span_font: ^Font
|
|
span_size: f64
|
|
have_span := false
|
|
prev: ^Text_Glyph
|
|
|
|
for k in ln.first ..< ln.last {
|
|
g := &lay.glyphs[k]
|
|
if prev != nil && g.r == prev.r && g.text == prev.text &&
|
|
text_len(Point{g.pen.x - prev.pen.x, g.pen.y - prev.pen.y}) <= TEXT_DUP_EM * max(g.em, prev.em) {
|
|
// The same character re-inked in the same place: fake bold.
|
|
continue
|
|
}
|
|
space := false
|
|
if prev != nil {
|
|
d := Point{g.pen.x - prev.end.x, g.pen.y - prev.end.y}
|
|
gap := d.x * ln.dir.x + d.y * ln.dir.y
|
|
space = gap > TEXT_SPACE_EM * max(g.em, prev.em)
|
|
}
|
|
// A space is only ever a separator, so it never opens a line and
|
|
// never doubles one that is already there.
|
|
if space && (!have_span || text_builder_ends_space(&sb)) {
|
|
space = false
|
|
}
|
|
if have_span && (g.font != span_font || abs(g.size - span_size) > 0.01 * max(g.size, span_size)) {
|
|
if space {
|
|
strings.write_byte(&sb, ' ')
|
|
space = false
|
|
}
|
|
text_flush_span(&spans, &sb, span_font, span_size, &span_acc, allocator)
|
|
text_acc_rect(&line_acc, span_acc.r, span_acc.have)
|
|
span_acc = {}
|
|
have_span = false
|
|
}
|
|
if !have_span {
|
|
span_font = g.font
|
|
span_size = g.size
|
|
have_span = true
|
|
}
|
|
if space {
|
|
strings.write_byte(&sb, ' ')
|
|
}
|
|
if g.r == ' ' && len(g.text) == 0 && strings.builder_len(sb) == 0 && len(spans) == 0 {
|
|
// Leading space glyphs carry nothing the rectangle does not.
|
|
continue
|
|
}
|
|
if len(g.text) > 0 {
|
|
for r in g.text {
|
|
strings.write_rune(&sb, text_rune_of(r))
|
|
}
|
|
} else {
|
|
strings.write_rune(&sb, g.r)
|
|
}
|
|
text_glyph_box(g, &span_acc)
|
|
prev = g
|
|
}
|
|
// Trailing spaces are producer noise, not content.
|
|
text_builder_trim_right(&sb)
|
|
if have_span && strings.builder_len(sb) > 0 {
|
|
text_flush_span(&spans, &sb, span_font, span_size, &span_acc, allocator)
|
|
text_acc_rect(&line_acc, span_acc.r, span_acc.have)
|
|
}
|
|
if len(spans) == 0 {
|
|
continue
|
|
}
|
|
append(&lines, Text_Line{spans = slice.clone(spans[:], allocator), rect = line_acc.r})
|
|
text_acc_rect(&block_acc, line_acc.r, line_acc.have)
|
|
}
|
|
if len(lines) > 0 {
|
|
append(&blocks, Text_Block{lines = slice.clone(lines[:], allocator), rect = block_acc.r})
|
|
}
|
|
delete(lines)
|
|
delete(spans)
|
|
return blocks[:]
|
|
}
|
|
|
|
@(private)
|
|
text_flush_span :: proc(spans: ^[dynamic]Text_Span, sb: ^strings.Builder, font: ^Font, size: f64,
|
|
acc: ^Text_Rect_Acc, allocator: mem.Allocator) {
|
|
if strings.builder_len(sb^) == 0 {
|
|
return
|
|
}
|
|
append(spans, Text_Span{
|
|
text = strings.clone(strings.to_string(sb^), allocator),
|
|
rect = acc.r,
|
|
font = font,
|
|
size = size,
|
|
})
|
|
strings.builder_reset(sb)
|
|
}
|
|
|
|
@(private)
|
|
text_builder_ends_space :: proc(sb: ^strings.Builder) -> bool {
|
|
n := len(sb.buf)
|
|
return n > 0 && sb.buf[n - 1] == ' '
|
|
}
|
|
|
|
@(private)
|
|
text_builder_trim_right :: proc(sb: ^strings.Builder) {
|
|
for len(sb.buf) > 0 && sb.buf[len(sb.buf) - 1] == ' ' {
|
|
pop(&sb.buf)
|
|
}
|
|
}
|
|
|
|
// text_blocks_destroy releases what text_device_blocks returned. `allocator`
|
|
// must be the one it was given.
|
|
text_blocks_destroy :: proc(blocks: []Text_Block, allocator := context.allocator) {
|
|
for b in blocks {
|
|
for l in b.lines {
|
|
for s in l.spans {
|
|
delete(s.text, allocator)
|
|
}
|
|
delete(l.spans, allocator)
|
|
}
|
|
delete(b.lines, allocator)
|
|
}
|
|
delete(blocks, allocator)
|
|
}
|
|
|
|
// text_device_result is the page's text as one string: spans joined with
|
|
// nothing, lines with a newline, blocks with a blank line. There is no
|
|
// trailing newline, so a caller stitching pages together decides its own
|
|
// separator.
|
|
//
|
|
// The string is allocated with `allocator` and belongs to the caller; release
|
|
// it with `delete(s, allocator)`. It is built from exactly the same layout
|
|
// text_device_blocks returns, so the two can never disagree.
|
|
text_device_result :: proc(td: ^Text_Device, allocator := context.allocator) -> string {
|
|
b := strings.builder_make(allocator)
|
|
if td == nil {
|
|
return strings.to_string(b)
|
|
}
|
|
blocks := text_device_blocks(td, td.allocator)
|
|
defer text_blocks_destroy(blocks, td.allocator)
|
|
for blk, bi in blocks {
|
|
if bi > 0 {
|
|
strings.write_string(&b, "\n\n")
|
|
}
|
|
for ln, li in blk.lines {
|
|
if li > 0 {
|
|
strings.write_byte(&b, '\n')
|
|
}
|
|
for sp in ln.spans {
|
|
strings.write_string(&b, sp.text)
|
|
}
|
|
}
|
|
}
|
|
return strings.to_string(b)
|
|
}
|