use alloc::string::{String, ToString};
use alloc::vec::Vec;
use alloc::collections::BTreeMap;
use crate::document::Document;
use crate::encoding::Encoding;
use crate::error::{Error, Result};
use crate::lexer::Token;
use crate::object::{Dictionary, Object};
use crate::page::Page;
use crate::page::Rect;
use crate::parser::Parser;
const WORD_GAP: f64 = 200.0;
const LINE_TOLERANCE: f64 = 0.01;
#[derive(Debug, Default)]
struct Line {
x: f64,
y: f64,
text: String,
matrix: Matrix,
size: f64,
advance: f64,
}
#[derive(Debug, Clone, Copy, PartialEq, Default)]
struct Matrix {
a: f64,
b: f64,
c: f64,
d: f64,
e: f64,
f: f64,
}
impl Matrix {
const IDENTITY: Self = Self {
a: 1.0,
b: 0.0,
c: 0.0,
d: 1.0,
e: 0.0,
f: 0.0,
};
fn multiply(self, other: Self) -> Self {
Self {
a: self.a * other.a + self.b * other.c,
b: self.a * other.b + self.b * other.d,
c: self.c * other.a + self.d * other.c,
d: self.c * other.b + self.d * other.d,
e: self.e * other.a + self.f * other.c + other.e,
f: self.e * other.b + self.f * other.d + other.f,
}
}
fn apply(self, x: f64, y: f64) -> (f64, f64) {
(
self.a * x + self.c * y + self.e,
self.b * x + self.d * y + self.f,
)
}
}
#[derive(Debug, Clone)]
pub(crate) enum CodeMap {
ToUnicode(crate::cmap::ToUnicode),
Predefined(crate::cmap::Predefined),
}
impl CodeMap {
fn text(&self, code: u32, length: u8) -> Option<alloc::string::String> {
match self {
Self::ToUnicode(map) => map.text(code, length).map(alloc::borrow::ToOwned::to_owned),
Self::Predefined(map) => map.text(code, length).map(|text| {
let mut buffer = alloc::string::String::new();
buffer.push(text);
buffer
}),
}
}
fn code_lengths(&self) -> &[u8] {
match self {
Self::ToUnicode(map) => map.code_lengths(),
Self::Predefined(map) => map.code_lengths(),
}
}
fn max_code_length(&self) -> u8 {
match self {
Self::ToUnicode(map) => map.max_code_length(),
Self::Predefined(map) => map.max_code_length(),
}
}
}
#[derive(Debug, Clone, Default)]
struct Widths {
default: f64,
runs: Vec<(u32, u32, Vec<f64>)>,
}
impl Widths {
fn width(&self, cid: u32) -> f64 {
for (first, last, widths) in &self.runs {
if cid >= *first && cid <= *last {
let index = usize::try_from(cid - first).unwrap_or(usize::MAX);
if let Some(width) = widths.get(index) {
return *width;
}
}
}
self.default
}
}
#[derive(Debug, Clone)]
enum Font {
Simple {
encoding: Encoding,
},
Composite {
map: CodeMap,
widths: Widths,
},
}
impl Font {
fn decode(&self, bytes: &[u8]) -> (String, f64) {
let Self::Composite { map, widths } = self else {
let Self::Simple { encoding } = self else {
return (String::new(), 0.0);
};
return (
bytes
.iter()
.filter_map(|code| encoding.character(*code))
.collect(),
0.0,
);
};
let mut text = String::new();
let mut advance = 0.0;
let lengths = map.code_lengths();
let narrowest = lengths.first().map_or(1, |length| usize::from(*length));
let widest = usize::from(map.max_code_length());
let mut position = 0;
while position < bytes.len() {
let mut consumed = 0;
let mut width = if lengths.len() == 1 {
narrowest
} else {
widest
};
while width >= narrowest {
if position + width <= bytes.len() {
let code = pack(&bytes[position..position + width]);
let matched = lengths.len() == 1
|| map.text(code, u8::try_from(width).unwrap_or(2)).is_some();
if matched {
consumed = width;
break;
}
}
if width == narrowest {
break;
}
width -= 1;
}
if consumed == 0 {
if position + narrowest > bytes.len() {
break;
}
position += narrowest;
continue;
}
let code = pack(&bytes[position..position + consumed]);
if let Some(mapped) = map.text(code, u8::try_from(consumed).unwrap_or(2)) {
text.push_str(&mapped);
}
advance += widths.width(code);
position += consumed;
}
(text, advance / 1000.0)
}
fn tracks_advances(&self) -> bool {
matches!(self, Self::Composite { .. })
}
}
fn pack(bytes: &[u8]) -> u32 {
bytes
.iter()
.fold(0_u32, |value, &byte| (value << 8) | u32::from(byte))
}
struct TextInterpreter<'a> {
document: &'a Document,
resources: Option<Dictionary>,
fonts: BTreeMap<Vec<u8>, Font>,
font: Option<Font>,
leading: f64,
size: f64,
line_x: f64,
line_y: f64,
pen_x: f64,
pen_tracked: bool,
lines: Vec<Line>,
ctm: Matrix,
ctm_stack: Vec<Matrix>,
text_matrix: Matrix,
captures: Vec<Option<Capture>>,
}
struct Capture {
line: Option<usize>,
offset: usize,
text: String,
}
impl<'a> TextInterpreter<'a> {
fn new(document: &'a Document, resources: Option<Dictionary>) -> Self {
Self {
document,
resources,
fonts: BTreeMap::new(),
font: None,
leading: 0.0,
size: 0.0,
line_x: 0.0,
line_y: 0.0,
pen_x: 0.0,
pen_tracked: false,
lines: Vec::new(),
ctm: Matrix::IDENTITY,
ctm_stack: Vec::new(),
text_matrix: Matrix::IDENTITY,
captures: Vec::new(),
}
}
fn run(mut self, content: &[u8]) -> Result<Vec<Line>> {
let mut parser = Parser::new(content);
let mut operands: Vec<Object> = Vec::new();
loop {
match parser.peek_token()? {
Token::Eof => break,
Token::Keyword(_) => {
let keyword = match parser.next_token()? {
Token::Keyword(keyword) => keyword,
_ => return Err(Error::malformed("content-stream operator")),
};
self.execute(&keyword, &mut operands, &mut parser)?;
operands.clear();
}
_ => {
let object = parser.parse_object()?;
operands.push(object);
}
}
}
Ok(self.ordered_lines())
}
fn ordered_lines(mut self) -> Vec<Line> {
self.lines.retain(|line| !line.text.is_empty());
self.lines.sort_by(|left, right| {
right
.y
.partial_cmp(&left.y)
.unwrap_or(core::cmp::Ordering::Equal)
.then(
left.x
.partial_cmp(&right.x)
.unwrap_or(core::cmp::Ordering::Equal),
)
});
self.lines
}
fn line(&mut self) -> &mut Line {
if let Some(index) = self
.lines
.iter()
.position(|line| difference(line.y, self.line_y) <= LINE_TOLERANCE)
{
return &mut self.lines[index];
}
self.lines.push(Line {
x: self.line_x,
y: self.line_y,
text: String::new(),
matrix: self.text_matrix.multiply(self.ctm),
size: self.size,
advance: 0.0,
});
#[allow(clippy::unwrap_used)]
self.lines.last_mut().unwrap()
}
fn enter_marked(&mut self, properties: Option<&Object>) -> Result<()> {
let mut capture = None;
if let Some(properties) = properties {
let resolved = self
.document
.resolve(Some(properties))?
.unwrap_or(Object::Null);
if let Object::Dictionary(dict) = resolved
&& let Some(Object::String(text)) = dict.get(b"ActualText")
{
capture = Some(Capture {
line: None,
offset: 0,
text: String::from_utf8_lossy(text.as_bytes()).into_owned(),
});
}
}
self.captures.push(capture);
Ok(())
}
fn leave_marked(&mut self) {
let Some(capture) = self.captures.pop().flatten() else {
return;
};
let Some(index) = capture.line else {
return;
};
let Some(line) = self.lines.get_mut(index) else {
return;
};
let at = char_to_byte(&line.text, capture.offset);
line.text.insert_str(at, &capture.text);
}
fn execute(
&mut self,
operator: &[u8],
operands: &mut [Object],
parser: &mut Parser<'_>,
) -> Result<()> {
match operator {
b"BT" => {
self.line_x = 0.0;
self.line_y = 0.0;
}
b"ET" => {}
b"Tf" => {
let name = match operands.first() {
Some(Object::Name(name)) => name.clone(),
_ => return Err(Error::malformed("/Tf needs a font name")),
};
self.size = number(operands.get(1));
self.font = Some(self.load_font(&name)?);
self.pen_tracked = self.font.as_ref().is_some_and(Font::tracks_advances);
self.pen_x = self.line_x;
}
b"Td" | b"TD" => {
let tx = number(operands.first());
let ty = number(operands.get(1));
let previous_y = self.line_y;
self.line_x += tx;
self.line_y += ty;
self.text_matrix = Matrix {
e: self.text_matrix.e + tx * self.text_matrix.a + ty * self.text_matrix.c,
f: self.text_matrix.f + tx * self.text_matrix.b + ty * self.text_matrix.d,
..self.text_matrix
};
if difference(previous_y, self.line_y) > LINE_TOLERANCE {
self.pen_x = self.line_x;
}
if operator == b"TD" {
self.leading = -ty;
}
}
b"T*" => {
self.line_y -= self.leading;
self.pen_x = self.line_x;
self.text_matrix = Matrix {
e: self.text_matrix.e - self.leading * self.text_matrix.c,
f: self.text_matrix.f - self.leading * self.text_matrix.d,
..self.text_matrix
};
}
b"TL" => {
self.leading = number(operands.first());
}
b"q" => self.ctm_stack.push(self.ctm),
b"Q" => {
if let Some(saved) = self.ctm_stack.pop() {
self.ctm = saved;
}
}
b"cm" => {
let matrix = Matrix {
a: number(operands.first()),
b: number(operands.get(1)),
c: number(operands.get(2)),
d: number(operands.get(3)),
e: number(operands.get(4)),
f: number(operands.get(5)),
};
self.ctm = self.ctm.multiply(matrix);
}
b"Tm" => {
self.text_matrix = Matrix {
a: number(operands.first()),
b: number(operands.get(1)),
c: number(operands.get(2)),
d: number(operands.get(3)),
e: number(operands.get(4)),
f: number(operands.get(5)),
};
let previous_y = self.line_y;
self.line_x = number(operands.get(4));
self.line_y = number(operands.get(5));
if difference(previous_y, self.line_y) > LINE_TOLERANCE {
self.pen_x = self.line_x;
}
}
b"Tc" | b"Tw" | b"Tz" | b"Ts" => {}
b"Tj" => {
if let Some(Object::String(string)) = operands.first() {
self.show(string.as_bytes());
}
}
b"'" => {
self.line_y -= self.leading;
self.pen_x = self.line_x;
if let Some(Object::String(string)) = operands.first() {
self.show(string.as_bytes());
}
}
b"\"" => {
self.line_y -= self.leading;
self.pen_x = self.line_x;
if let Some(Object::String(string)) = operands.get(2) {
self.show(string.as_bytes());
}
}
b"TJ" => {
if let Some(Object::Array(items)) = operands.first() {
for item in items {
match item {
Object::String(string) => self.show(string.as_bytes()),
Object::Integer(adjustment) => self.adjust(*adjustment as f64),
Object::Real(adjustment) => self.adjust(*adjustment),
_ => return Err(Error::malformed("unsupported /TJ array entry")),
}
}
}
}
b"BDC" | b"BMC" => {
let properties = if operator == b"BDC" {
operands.get(1)
} else {
None
};
self.enter_marked(properties)?;
}
b"EMC" => self.leave_marked(),
b"BI" => {
skip_inline_image(parser)?;
}
_ => {}
}
Ok(())
}
fn adjust(&mut self, adjustment: f64) {
if -adjustment < WORD_GAP {
return;
}
let line = self.line();
if !line.text.is_empty() && !line.text.ends_with(' ') {
line.text.push(' ');
}
if self.pen_tracked {
self.pen_x -= adjustment / 1000.0 * self.size;
}
}
fn show(&mut self, bytes: &[u8]) {
let Some(font) = &self.font else {
return;
};
let (run, advance) = font.decode(bytes);
let gap =
self.pen_tracked && self.size > 0.0 && self.line_x > self.pen_x + 0.25 * self.size;
let inside_has_line = self
.captures
.iter()
.rev()
.find_map(|capture| capture.as_ref())
.is_some_and(|capture| capture.line.is_some());
let capturing = self
.captures
.iter()
.rev()
.find_map(|capture| capture.as_ref())
.is_some();
if capturing {
self.line();
let index = self.lines.len() - 1;
let offset = self.lines[index].text.len();
if !inside_has_line
&& let Some(slot) = self
.captures
.iter_mut()
.rev()
.find_map(|capture| capture.as_mut())
{
slot.line = Some(index);
slot.offset = offset;
}
if self.pen_tracked {
self.pen_x = self.line_x + advance * self.size;
}
return;
}
let line = self.line();
if gap && !line.text.is_empty() && !line.text.ends_with(' ') {
line.text.push(' ');
}
line.text.push_str(&run);
let tracked = self.pen_tracked;
if tracked {
self.pen_x = self.line_x + advance * self.size;
let start = self.line_x;
if let Some(line) = self.lines.last_mut() {
line.advance = self.pen_x - start;
}
}
}
fn load_font(&mut self, name: &[u8]) -> Result<Font> {
if let Some(font) = self.fonts.get(name) {
return Ok(font.clone());
}
let font = self.read_font(name)?;
self.fonts.insert(name.to_vec(), font.clone());
Ok(font)
}
fn read_font(&self, name: &[u8]) -> Result<Font> {
let font = match self
.resources
.as_ref()
.and_then(|resources| resources.get(b"Font"))
{
Some(fonts) => {
let fonts = self.document.resolve(Some(fonts))?.unwrap_or(Object::Null);
match fonts {
Object::Dictionary(fonts) => fonts.get(name).cloned(),
_ => None,
}
}
None => None,
};
let Some(font) = font else {
return Err(Error::Malformed {
what: "content stream selects a font the page does not declare",
offset: None,
});
};
let font = self.document.resolve(Some(&font))?.unwrap_or(Object::Null);
let Object::Dictionary(dict) = font else {
return Err(Error::Malformed {
what: "font resource is not a dictionary",
offset: None,
});
};
if let Some(Object::Name(subtype)) = dict.get(b"Subtype")
&& subtype == b"Type0"
{
return self.composite_font(&dict);
}
Ok(Font::Simple {
encoding: self.encoding_of(&dict)?,
})
}
fn composite_font(&self, dict: &Dictionary) -> Result<Font> {
match dict.get(b"Encoding") {
Some(Object::Name(name)) if name == b"Identity-H" => {}
Some(Object::Name(name)) if name == b"Identity-V" => {
return Err(Error::Unsupported {
what: "vertical composite (Type0) fonts",
});
}
Some(Object::Name(name)) => {
if let Some(predefined) = crate::cmap::Predefined::by_name(name) {
return Ok(Font::Composite {
map: CodeMap::Predefined(predefined),
widths: self.widths_of(dict)?,
});
}
return Err(Error::Unsupported {
what: "CMap-encoded composite (Type0) fonts",
});
}
Some(Object::Reference(_)) | Some(Object::Stream(_)) => {
return Err(Error::Unsupported {
what: "embedded CMap-encoded composite (Type0) fonts",
});
}
_ => {
return Err(Error::Unsupported {
what: "composite (Type0) fonts without an /Encoding",
});
}
}
let Some(to_unicode) = dict.get(b"ToUnicode") else {
return Err(Error::Unsupported {
what: "composite (Type0) fonts without a /ToUnicode map",
});
};
let Object::Reference(id) = to_unicode else {
return Err(Error::Unsupported {
what: "a direct /ToUnicode stream",
});
};
let map = crate::cmap::ToUnicode::parse(&self.document.stream_data(*id)?)?;
Ok(Font::Composite {
map: CodeMap::ToUnicode(map),
widths: self.widths_of(dict)?,
})
}
fn widths_of(&self, dict: &Dictionary) -> Result<Widths> {
let mut widths = Widths {
default: 1000.0,
runs: Vec::new(),
};
let Some(descendants) = dict.get(b"DescendantFonts") else {
return Ok(widths);
};
let descendants = self
.document
.resolve(Some(descendants))?
.unwrap_or(Object::Null);
let Object::Array(descendants) = descendants else {
return Err(Error::Malformed {
what: "/DescendantFonts must be an array",
offset: None,
});
};
let Some(first) = descendants.first() else {
return Ok(widths);
};
let first = self.document.resolve(Some(first))?.unwrap_or(Object::Null);
let Object::Dictionary(descendant) = first else {
return Ok(widths);
};
if let Some(default) = descendant.get(b"DW") {
widths.default = number(Some(default));
}
let Some(w_array) = descendant.get(b"W") else {
return Ok(widths);
};
let w_array = self
.document
.resolve(Some(w_array))?
.unwrap_or(Object::Null);
let Object::Array(items) = w_array else {
return Err(Error::Malformed {
what: "/W must be an array",
offset: None,
});
};
let mut index = 0;
while index < items.len() {
let Some(Object::Integer(first)) = items.get(index) else {
return Err(Error::Malformed {
what: "/W entries start with a CID",
offset: None,
});
};
let first = u32::try_from(*first).map_err(|_| Error::Malformed {
what: "/W CIDs must not be negative",
offset: None,
})?;
match items.get(index + 1) {
Some(Object::Array(list)) => {
let run: Vec<f64> = list.iter().map(|item| number(Some(item))).collect();
let last = first.saturating_add(
u32::try_from(run.len().saturating_sub(1)).unwrap_or(u32::MAX),
);
widths.runs.push((first, last, run));
index += 2;
}
Some(Object::Integer(last)) => {
let width = number(items.get(index + 2));
let last = u32::try_from(*last).map_err(|_| Error::Malformed {
what: "/W CIDs must not be negative",
offset: None,
})?;
widths.runs.push((first, last, alloc::vec![width]));
index += 3;
}
_ => {
return Err(Error::Malformed {
what: "/W entry is neither an array nor a range",
offset: None,
});
}
}
}
Ok(widths)
}
fn encoding_of(&self, dict: &Dictionary) -> Result<Encoding> {
let Some(encoding_object) = dict.get(b"Encoding") else {
return Ok(Encoding::standard());
};
let encoding_object = self
.document
.resolve(Some(encoding_object))?
.unwrap_or(Object::Null);
let mut encoding = Encoding::from_object(Some(&encoding_object))?;
if let Object::Dictionary(differences) = &encoding_object
&& let Some(differences) = differences.get(b"Differences")
{
let differences = self
.document
.resolve(Some(differences))?
.unwrap_or(Object::Null);
let Object::Array(items) = differences else {
return Err(Error::Malformed {
what: "/Differences must be an array",
offset: None,
});
};
encoding.apply_differences(&items)?;
}
Ok(encoding)
}
}
fn skip_inline_image(parser: &mut Parser<'_>) -> Result<()> {
let search = parser.raw_position();
let found = parser
.content()
.get(search..)
.and_then(|rest| find_operator(rest, b"EI"))
.ok_or(Error::malformed("inline image without a closing EI"))?;
parser.seek(search + found + 2);
Ok(())
}
fn find_operator(haystack: &[u8], needle: &[u8]) -> Option<usize> {
let mut index = 0;
while index + needle.len() <= haystack.len() {
if &haystack[index..index + needle.len()] == needle {
let before_ok = index == 0
|| crate::lexer::is_whitespace(haystack[index - 1])
|| crate::lexer::is_delimiter(haystack[index - 1]);
let after = index + needle.len();
let after_ok = after >= haystack.len()
|| crate::lexer::is_whitespace(haystack[after])
|| crate::lexer::is_delimiter(haystack[after]);
if before_ok && after_ok {
return Some(index);
}
}
index += 1;
}
None
}
fn difference(left: f64, right: f64) -> f64 {
if left >= right {
left - right
} else {
right - left
}
}
fn number(operand: Option<&Object>) -> f64 {
match operand {
Some(Object::Integer(value)) => *value as f64,
Some(Object::Real(value)) => *value,
_ => 0.0,
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct TextSpan {
pub text: String,
pub bounds: Rect,
}
#[derive(Debug, Clone, PartialEq)]
pub struct PageHits {
pub page: usize,
pub hits: Vec<SearchHit>,
}
#[derive(Debug, Clone, PartialEq)]
pub struct SearchHit {
pub text: String,
pub bounds: Rect,
}
impl Line {
fn bounds(&self) -> Rect {
let matrix = self.matrix;
let (x0, y0) = matrix.apply(0.0, 0.0);
let advance = if self.advance > 0.0 {
self.advance
} else {
self.size * 0.5 * self.text.chars().count() as f64
};
let (x1, y1) = matrix.apply(advance, 0.0);
let (x2, y2) = matrix.apply(0.0, self.size);
let (x3, y3) = matrix.apply(advance, self.size);
Rect::new(
x0.min(x1).min(x2).min(x3),
y0.min(y1).min(y2).min(y3),
x0.max(x1).max(x2).max(x3),
y0.max(y1).max(y2).max(y3),
)
}
}
impl Document {
pub fn extract_text(&self, page: &Page) -> Result<String> {
let content = self.page_content(page)?;
self.extract_text_from(&content, page.resources.as_ref())
}
pub fn extract_text_from(
&self,
content: &[u8],
resources: Option<&Dictionary>,
) -> Result<String> {
let lines = TextInterpreter::new(self, resources.cloned()).run(content)?;
Ok(lines
.iter()
.map(|line| line.text.as_str())
.collect::<Vec<_>>()
.join("\n"))
}
pub fn spans(&self, page: &Page) -> Result<Vec<TextSpan>> {
let content = self.page_content(page)?;
self.spans_from(&content, page.resources.as_ref())
}
pub fn search(&self, needle: &str) -> Result<Vec<PageHits>> {
let folded = needle.to_lowercase();
let mut found = Vec::new();
if folded.is_empty() {
return Ok(found);
}
for (index, page) in self.pages()?.iter().enumerate() {
let content = self.page_content(page)?;
let mut hits = Vec::new();
for span in self.spans_from(&content, page.resources.as_ref())? {
let haystack = span.text.to_lowercase();
let mut from = 0;
while let Some(at) = haystack[from..].find(&folded) {
let start = from + at;
let end = start + folded.len();
let first = char_boundary(&span.text, start);
let last = char_boundary(&span.text, end);
let text = span
.text
.get(first..last)
.unwrap_or(span.text.as_str())
.to_string();
hits.push(SearchHit {
text,
bounds: span.bounds,
});
from = end;
}
}
if !hits.is_empty() {
found.push(PageHits { page: index, hits });
}
}
Ok(found)
}
pub fn spans_from(
&self,
content: &[u8],
resources: Option<&Dictionary>,
) -> Result<Vec<TextSpan>> {
let lines = TextInterpreter::new(self, resources.cloned()).run(content)?;
Ok(lines
.into_iter()
.map(|line| TextSpan {
bounds: line.bounds(),
text: line.text,
})
.collect())
}
}
fn char_to_byte(text: &str, characters: usize) -> usize {
text.char_indices()
.nth(characters)
.map_or(text.len(), |(at, _)| at)
}
fn char_boundary(text: &str, offset: usize) -> usize {
let mut at = offset.min(text.len());
while at > 0 && !text.is_char_boundary(at) {
at -= 1;
}
at
}
#[cfg(test)]
mod tests {
use super::find_operator;
#[test]
fn inline_image_terminator_must_be_a_whole_operator() {
assert_eq!(find_operator(b"abc EI more", b"EI"), Some(4));
assert_eq!(find_operator(b"EI", b"EI"), Some(0));
assert_eq!(
find_operator(b"tailEIx", b"EI"),
None,
"EI inside a word is not the operator"
);
assert_eq!(find_operator(b"no terminator", b"EI"), None);
}
}