spectre_pdf 1.0.0

//! Positional text extraction: content-stream interpreter that emits text
//! runs annotated with bounding boxes in PDF user space.
//!
//! Maintains the graphics state stack (CTM + text state per PDF §9) and
//! emits one [`TextSpan`] per text-showing operator. The pre-existing
//! `extract_text` / `extract_pages` / `extract_tables` callers do not
//! route through this layer.
//!
//! # Bbox accuracy
//!
//! We do not parse `/Widths`, `/MissingWidth`, or Type 3 glyph procedures;
//! glyph advance is approximated as `0.5 × fontSize`. Character-level
//! bboxes are ~5% off on fixed-width fonts; word-level error averages out.
//! Vertical writing mode (`/WMode 1`) still advances horizontally — CJK
//! text decodes correctly but may stack bboxes.

use crate::geom::{Matrix, Rect};
use crate::structure::decode_pdf_string;
use crate::ExtractError;
use spectre_parse::{resolve_page_encodings, Content, Document, Encoding, Object, ObjectId};
use std::collections::BTreeMap;

/// One positioned text fragment emitted by a single text-showing operator
/// (`Tj` / `TJ` / `'` / `"`).
#[derive(Debug, Clone, PartialEq)]
pub struct TextSpan {
    pub text: String,
    pub bbox: Rect,
    pub page: u32,
    pub font: String,
    pub font_size: f32,
}

/// Whitespace-delimited token with its own bbox. Bbox is built by
/// proportioning the containing span's bbox by character count.
#[derive(Debug, Clone, PartialEq)]
pub struct Word {
    pub text: String,
    pub bbox: Rect,
    pub page: u32,
    pub block_no: u32,
    pub line_no: u32,
    pub word_no: u32,
}

/// Cluster of [`TextSpan`]s grouped by spatial proximity.
#[derive(Debug, Clone, PartialEq)]
pub struct TextBlock {
    pub text: String,
    pub bbox: Rect,
    pub page: u32,
    pub block_no: u32,
    pub lines: Vec<TextLine>,
}

#[derive(Debug, Clone, PartialEq)]
pub struct TextLine {
    pub text: String,
    pub bbox: Rect,
    pub spans: Vec<TextSpan>,
}

/// Per-page positioned spans plus a re-assembled plain-text string.
#[derive(Debug, Clone, PartialEq)]
pub struct PositionedPage {
    pub page: u32,
    pub text: String,
    pub spans: Vec<TextSpan>,
}

// ── Public entry points ─────────────────────────────────────────────────────

pub fn extract_text_positioned_impl(
    pdf_bytes: &[u8],
    page_filter: Option<u32>,
) -> Result<Vec<PositionedPage>, ExtractError> {
    let doc = crate::document::open_sp_with_password(pdf_bytes, b"")?;
    extract_text_positioned_from_doc(&doc, page_filter)
}

pub(crate) fn extract_text_positioned_from_doc(
    doc: &Document,
    page_filter: Option<u32>,
) -> Result<Vec<PositionedPage>, ExtractError> {
    let mut pages: Vec<(u32, ObjectId)> = doc.get_pages().into_iter().collect();
    pages.sort_by_key(|(n, _)| *n);
    let mut out = Vec::with_capacity(pages.len());
    for (num, _id) in &pages {
        if let Some(filter) = page_filter {
            if filter != *num {
                continue;
            }
        }
        let raw_spans = collect_spans_for_page(doc, *num)?;
        // Kerning-heavy / vector-renderer PDFs emit one Tj per glyph; without
        // this merge, word_count blows out 5×+.
        let spans = merge_adjacent_spans(&raw_spans);
        let text = assemble_reading_order(&spans);
        out.push(PositionedPage {
            page: *num,
            text,
            spans,
        });
    }
    Ok(out)
}

pub fn extract_words_impl(
    pdf_bytes: &[u8],
    page_filter: Option<u32>,
) -> Result<Vec<Word>, ExtractError> {
    let doc = crate::document::open_sp_with_password(pdf_bytes, b"")?;
    extract_words_from_doc(&doc, page_filter)
}

pub(crate) fn extract_words_from_doc(
    doc: &Document,
    page_filter: Option<u32>,
) -> Result<Vec<Word>, ExtractError> {
    let pages = extract_text_positioned_from_doc(doc, page_filter)?;
    let mut words = Vec::new();
    for p in &pages {
        let blocks = group_into_blocks(&p.spans);
        for (block_no, block) in blocks.iter().enumerate() {
            for (line_no, line) in block.lines.iter().enumerate() {
                let mut word_no = 0u32;
                for span in &line.spans {
                    for w in split_span_into_words(span) {
                        words.push(Word {
                            text: w.text,
                            bbox: w.bbox,
                            page: p.page,
                            block_no: block_no as u32,
                            line_no: line_no as u32,
                            word_no,
                        });
                        word_no += 1;
                    }
                }
            }
        }
    }
    Ok(words)
}

pub fn extract_blocks_impl(
    pdf_bytes: &[u8],
    page_filter: Option<u32>,
) -> Result<Vec<TextBlock>, ExtractError> {
    let doc = crate::document::open_sp_with_password(pdf_bytes, b"")?;
    extract_blocks_from_doc(&doc, page_filter)
}

/// Block formation without the column pre-pass — headings often span
/// horizontally across body columns, so partitioning by x cuts them into
/// pieces. Used for markdown rendering; the public `blocks()` surface
/// keeps the column pre-pass for token-F1 on multi-column layouts.
pub(crate) fn extract_blocks_streaming_from_doc(
    doc: &Document,
    page_filter: Option<u32>,
) -> Result<Vec<TextBlock>, ExtractError> {
    let pages = extract_text_positioned_from_doc(doc, page_filter)?;
    let mut all_blocks = Vec::new();
    for p in &pages {
        let initial = group_into_blocks(&p.spans);
        let blocks = paragraph_break_post_pass(initial);
        let page_h = p.spans.iter().map(|s| s.bbox.y1).fold(0.0f32, f32::max);
        let blocks = header_footer_split(blocks, page_h);
        for (block_no, b) in blocks.into_iter().enumerate() {
            all_blocks.push(TextBlock {
                text: b.text,
                bbox: b.bbox,
                page: p.page,
                block_no: block_no as u32,
                lines: b.lines,
            });
        }
    }
    Ok(all_blocks)
}

pub(crate) fn extract_blocks_from_doc(
    doc: &Document,
    page_filter: Option<u32>,
) -> Result<Vec<TextBlock>, ExtractError> {
    let pages = extract_text_positioned_from_doc(doc, page_filter)?;
    let mut all_blocks = Vec::new();
    for p in &pages {
        // Two-stage segmentation: (1) partition by detected column gutters
        // so multi-column pages don't cross-stream tokens between columns;
        // (2) run the streaming per-span segmenter within each column.
        let columns = partition_into_columns(&p.spans);
        let mut blocks: Vec<AssembledBlock> = Vec::new();
        for col_spans in columns {
            let initial = group_into_blocks(&col_spans);
            blocks.extend(paragraph_break_post_pass(initial));
        }
        let page_h = p
            .spans
            .iter()
            .map(|s| s.bbox.y1)
            .fold(0.0f32, f32::max);
        let blocks = header_footer_split(blocks, page_h);
        for (block_no, b) in blocks.into_iter().enumerate() {
            all_blocks.push(TextBlock {
                text: b.text,
                bbox: b.bbox,
                page: p.page,
                block_no: block_no as u32,
                lines: b.lines,
            });
        }
    }
    Ok(all_blocks)
}

// ── Content-stream interpreter ──────────────────────────────────────────────

/// Walk one page's content stream, maintaining graphics + text state, and
/// emit one [`TextSpan`] per text-showing operator.
fn collect_spans_for_page(doc: &Document, page_num: u32) -> Result<Vec<TextSpan>, ExtractError> {
    let pages = doc.get_pages();
    let page_id = match pages.get(&page_num) {
        Some(id) => *id,
        None => return Ok(Vec::new()),
    };

    // Missing/failing font encodings degrade silently — layout/search
    // callers still benefit from knowing *where* something is.
    let fonts = doc.get_page_fonts(page_id).unwrap_or_default();
    let encodings: BTreeMap<Vec<u8>, Encoding> = resolve_page_encodings(doc, &fonts);

    let content_data = match doc.get_page_content(page_id) {
        Ok(d) => d,
        Err(_) => return Ok(Vec::new()),
    };
    let content = match Content::decode(&content_data) {
        Ok(c) => c,
        Err(_) => return Ok(Vec::new()),
    };

    let mut state = InterpreterState::new(page_num);
    let mut graphics_stack: Vec<GraphicsState> = Vec::new();

    for op in &content.operations {
        match op.operator.as_str() {
            "q" => graphics_stack.push(state.graphics.clone()),
            "Q" => {
                if let Some(g) = graphics_stack.pop() {
                    state.graphics = g;
                }
            }
            "cm" => {
                if let Some(m) = read_matrix(&op.operands) {
                    state.graphics.ctm = state.graphics.ctm.premultiply(m);
                }
            }
            "BT" => {
                // PDF §9.4.2: `BT` resets ONLY the text + line matrices.
                // Font, font size, spacing, h-scale, leading, and rise
                // persist across text objects. Resetting them would
                // collapse every following span's bbox to a point.
                state.text.text_matrix = Matrix::IDENTITY;
                state.text.line_matrix = Matrix::IDENTITY;
            }
            "ET" => {}
            "Tf" => {
                if op.operands.len() >= 2 {
                    if let Ok(name) = op.operands[0].as_name() {
                        state.text.font_name = Some(name.to_vec());
                    }
                    if let Ok(size) = op.operands[1].as_float() {
                        state.text.font_size = size;
                    }
                }
            }
            "Tm" => {
                if let Some(m) = read_matrix(&op.operands) {
                    state.text.text_matrix = m;
                    state.text.line_matrix = m;
                }
            }
            "Td" => {
                let (tx, ty) = read_xy(&op.operands).unwrap_or((0.0, 0.0));
                let m = Matrix::translation(tx, ty);
                state.text.line_matrix = state.text.line_matrix.premultiply(m);
                state.text.text_matrix = state.text.line_matrix;
            }
            "TD" => {
                let (tx, ty) = read_xy(&op.operands).unwrap_or((0.0, 0.0));
                state.text.leading = -ty;
                let m = Matrix::translation(tx, ty);
                state.text.line_matrix = state.text.line_matrix.premultiply(m);
                state.text.text_matrix = state.text.line_matrix;
            }
            "T*" => {
                let m = Matrix::translation(0.0, -state.text.leading);
                state.text.line_matrix = state.text.line_matrix.premultiply(m);
                state.text.text_matrix = state.text.line_matrix;
            }
            "TL" => {
                if let Some(v) = op.operands.first().and_then(|o| o.as_float().ok()) {
                    state.text.leading = v;
                }
            }
            "Tc" => {
                if let Some(v) = op.operands.first().and_then(|o| o.as_float().ok()) {
                    state.text.char_space = v;
                }
            }
            "Tw" => {
                if let Some(v) = op.operands.first().and_then(|o| o.as_float().ok()) {
                    state.text.word_space = v;
                }
            }
            "Tz" => {
                if let Some(v) = op.operands.first().and_then(|o| o.as_float().ok()) {
                    state.text.h_scale = v / 100.0;
                }
            }
            "Ts" => {
                if let Some(v) = op.operands.first().and_then(|o| o.as_float().ok()) {
                    state.text.rise = v;
                }
            }
            "Tj" => {
                if let Some(span) = emit_string_op(&state, &op.operands, &encodings) {
                    advance_after_emit(&mut state, &span.text, &span);
                    state.spans.push(span);
                }
            }
            "'" => {
                // Move to next line, then show string.
                let m = Matrix::translation(0.0, -state.text.leading);
                state.text.line_matrix = state.text.line_matrix.premultiply(m);
                state.text.text_matrix = state.text.line_matrix;
                if let Some(span) = emit_string_op(&state, &op.operands, &encodings) {
                    advance_after_emit(&mut state, &span.text, &span);
                    state.spans.push(span);
                }
            }
            "\"" => {
                // aw Tw ac Tc T* string Tj — operands [aw, ac, string].
                if op.operands.len() >= 3 {
                    if let Ok(aw) = op.operands[0].as_float() {
                        state.text.word_space = aw;
                    }
                    if let Ok(ac) = op.operands[1].as_float() {
                        state.text.char_space = ac;
                    }
                    let m = Matrix::translation(0.0, -state.text.leading);
                    state.text.line_matrix = state.text.line_matrix.premultiply(m);
                    state.text.text_matrix = state.text.line_matrix;
                    let single = std::slice::from_ref(&op.operands[2]);
                    if let Some(span) = emit_string_op(&state, single, &encodings) {
                        advance_after_emit(&mut state, &span.text, &span);
                        state.spans.push(span);
                    }
                }
            }
            "TJ" => {
                // Array of strings interleaved with numeric kerning offsets
                // (each numeric subtracts `(value/1000) * fontSize` from
                // advance). We emit one span per TJ — intra-array offsets
                // are typically intra-word kerning.
                if let Some(Object::Array(items)) = op.operands.first() {
                    let mut buf = String::new();
                    let mut bbox: Option<Rect> = None;
                    let font_name = state
                        .text
                        .font_name
                        .as_ref()
                        .map(|b| String::from_utf8_lossy(b).into_owned())
                        .unwrap_or_default();
                    for item in items {
                        match item {
                            Object::String(bytes, _) => {
                                let text = decode_with_encoding(
                                    &state.text.font_name,
                                    &encodings,
                                    bytes.as_slice(),
                                );
                                let span_bbox = compute_span_bbox(&state, text.chars().count());
                                advance_after_text(&mut state, text.chars().count());
                                bbox = Some(match bbox {
                                    Some(b) => b.union(span_bbox),
                                    None => span_bbox,
                                });
                                buf.push_str(&text);
                            }
                            other => {
                                if let Ok(adj) = other.as_float() {
                                    // PDF §9.4.3: positive adj moves left.
                                    let dx = -(adj / 1000.0)
                                        * state.text.font_size
                                        * state.text.h_scale;
                                    let m = Matrix::translation(dx, 0.0);
                                    state.text.text_matrix =
                                        state.text.text_matrix.premultiply(m);
                                }
                            }
                        }
                    }
                    if !buf.is_empty() {
                        state.spans.push(TextSpan {
                            text: buf,
                            bbox: bbox.unwrap_or(Rect::ZERO),
                            page: page_num,
                            font: font_name,
                            font_size: effective_font_size(&state),
                        });
                    }
                }
            }
            _ => {}
        }
    }
    Ok(state.spans)
}

// ── Interpreter helpers ─────────────────────────────────────────────────────

struct InterpreterState {
    page: u32,
    graphics: GraphicsState,
    text: TextState,
    spans: Vec<TextSpan>,
}

#[derive(Clone)]
struct GraphicsState {
    ctm: Matrix,
}

#[derive(Clone)]
struct TextState {
    text_matrix: Matrix,
    line_matrix: Matrix,
    font_name: Option<Vec<u8>>,
    font_size: f32,
    char_space: f32,
    word_space: f32,
    h_scale: f32,
    leading: f32,
    rise: f32,
}

impl Default for TextState {
    fn default() -> Self {
        Self {
            text_matrix: Matrix::IDENTITY,
            line_matrix: Matrix::IDENTITY,
            font_name: None,
            font_size: 0.0,
            char_space: 0.0,
            word_space: 0.0,
            h_scale: 1.0,
            leading: 0.0,
            rise: 0.0,
        }
    }
}

impl InterpreterState {
    fn new(page: u32) -> Self {
        Self {
            page,
            graphics: GraphicsState {
                ctm: Matrix::IDENTITY,
            },
            text: TextState::default(),
            spans: Vec::new(),
        }
    }
}

fn read_matrix(ops: &[Object]) -> Option<Matrix> {
    if ops.len() < 6 {
        return None;
    }
    let a = ops[0].as_float().ok()?;
    let b = ops[1].as_float().ok()?;
    let c = ops[2].as_float().ok()?;
    let d = ops[3].as_float().ok()?;
    let e = ops[4].as_float().ok()?;
    let f = ops[5].as_float().ok()?;
    Some(Matrix::new(a, b, c, d, e, f))
}

fn read_xy(ops: &[Object]) -> Option<(f32, f32)> {
    if ops.len() < 2 {
        return None;
    }
    Some((ops[0].as_float().ok()?, ops[1].as_float().ok()?))
}

fn emit_string_op(
    state: &InterpreterState,
    operands: &[Object],
    encodings: &BTreeMap<Vec<u8>, Encoding>,
) -> Option<TextSpan> {
    let bytes = operands.first().and_then(|o| match o {
        Object::String(b, _) => Some(b.as_slice()),
        _ => None,
    })?;
    let text = decode_with_encoding(&state.text.font_name, encodings, bytes);
    if text.is_empty() {
        return None;
    }
    let bbox = compute_span_bbox(state, text.chars().count());
    let font_name = state
        .text
        .font_name
        .as_ref()
        .map(|b| String::from_utf8_lossy(b).into_owned())
        .unwrap_or_default();
    Some(TextSpan {
        text,
        bbox,
        page: state.page,
        font: font_name,
        font_size: effective_font_size(state),
    })
}

fn decode_with_encoding(
    font_name: &Option<Vec<u8>>,
    encodings: &BTreeMap<Vec<u8>, Encoding>,
    bytes: &[u8],
) -> String {
    if let Some(name) = font_name {
        if let Some(enc) = encodings.get(name) {
            if let Ok(s) = enc.bytes_to_string(bytes) {
                return s;
            }
        }
    }
    // Fallback for PDFs whose font lookup misses but whose bytes are
    // PDFDocEncoding-clean (a superset of ASCII).
    decode_pdf_string(bytes)
}

/// Axis-aligned bbox of a span in user space.
///
/// Transforms the four text-space corners `(0, rise)`, `(w, rise)`,
/// `(0, rise + fontSize)`, `(w, rise + fontSize)` through `Tm · CTM`.
/// Per-glyph width is the proportional-font average `0.5 × fontSize`
/// (we don't parse `/Widths`).
fn compute_span_bbox(state: &InterpreterState, glyph_count: usize) -> Rect {
    let combined = state.graphics.ctm.premultiply(state.text.text_matrix);
    let avg_advance = 0.5;
    let text_w = state.text.font_size * state.text.h_scale * avg_advance * glyph_count as f32;
    let text_h = state.text.font_size;
    let rise = state.text.rise;
    let p0 = combined.transform_point(0.0, rise);
    let p1 = combined.transform_point(text_w, rise);
    let p2 = combined.transform_point(0.0, rise + text_h);
    let p3 = combined.transform_point(text_w, rise + text_h);
    let xs = [p0.0, p1.0, p2.0, p3.0];
    let ys = [p0.1, p1.1, p2.1, p3.1];
    let x0 = xs.iter().copied().fold(f32::INFINITY, f32::min);
    let x1 = xs.iter().copied().fold(f32::NEG_INFINITY, f32::max);
    let y0 = ys.iter().copied().fold(f32::INFINITY, f32::min);
    let y1 = ys.iter().copied().fold(f32::NEG_INFINITY, f32::max);
    Rect::new(x0, y0, x1, y1)
}

fn effective_font_size(state: &InterpreterState) -> f32 {
    let combined = state.graphics.ctm.premultiply(state.text.text_matrix);
    state.text.font_size * combined.scale_y()
}

fn advance_after_text(state: &mut InterpreterState, glyph_count: usize) {
    let avg_advance = 0.5 * state.text.font_size;
    // Word-space (PDF §9.3.3) only kicks in on literal space chars;
    // approximated as once per call.
    let glyph_total = avg_advance * glyph_count as f32
        + state.text.char_space * glyph_count as f32
        + state.text.word_space;
    let dx = glyph_total * state.text.h_scale;
    state.text.text_matrix = state
        .text
        .text_matrix
        .premultiply(Matrix::translation(dx, 0.0));
}

fn advance_after_emit(state: &mut InterpreterState, text: &str, _span: &TextSpan) {
    advance_after_text(state, text.chars().count());
}

// ── Reading-order assembly + block clustering ───────────────────────────────

/// Merge per-glyph spans into word-sized spans.
///
/// Two adjacent spans concatenate when they share a baseline (within
/// `0.35 × max_font_size`), share font + font-size, and have an
/// intra-word gap (`< 0.5 × font_size`). No synthetic space is inserted
/// at the seam — only literal whitespace from the PDF produces word
/// boundaries. Inserting spaces on every glyph-cluster boundary turns
/// "Firmware" into "Firm w are" on kerned PDFs.
fn merge_adjacent_spans(spans: &[TextSpan]) -> Vec<TextSpan> {
    if spans.is_empty() {
        return Vec::new();
    }
    let mut sorted: Vec<TextSpan> = spans.to_vec();
    sorted.sort_by(|a, b| {
        b.bbox
            .y0
            .partial_cmp(&a.bbox.y0)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| {
                a.bbox
                    .x0
                    .partial_cmp(&b.bbox.x0)
                    .unwrap_or(std::cmp::Ordering::Equal)
            })
    });

    let mut out: Vec<TextSpan> = Vec::with_capacity(sorted.len());
    for s in sorted {
        let merged = match out.last_mut() {
            Some(prev) => {
                let same_baseline = (prev.bbox.y0 - s.bbox.y0).abs()
                    < (prev.font_size.max(s.font_size) * 0.35);
                let same_font = prev.font == s.font
                    && (prev.font_size - s.font_size).abs() < 0.05;
                let gap = s.bbox.x0 - prev.bbox.x1;
                let close_enough = gap < prev.font_size.max(s.font_size) * 0.5
                    && gap >= -prev.font_size;
                if same_baseline && same_font && close_enough {
                    prev.text.push_str(&s.text);
                    prev.bbox = prev.bbox.union(s.bbox);
                    true
                } else {
                    false
                }
            }
            None => false,
        };
        if !merged {
            out.push(s);
        }
    }
    out
}

/// Re-build a per-page plain-text string from positioned spans. Sorts
/// top-to-bottom (PDF y decreases) then left-to-right; inserts `\n`
/// between lines whose y-centers are more than half a font-size apart.
fn assemble_reading_order(spans: &[TextSpan]) -> String {
    if spans.is_empty() {
        return String::new();
    }
    let mut sorted: Vec<&TextSpan> = spans.iter().collect();
    sorted.sort_by(|a, b| {
        b.bbox
            .y0
            .partial_cmp(&a.bbox.y0)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| {
                a.bbox
                    .x0
                    .partial_cmp(&b.bbox.x0)
                    .unwrap_or(std::cmp::Ordering::Equal)
            })
    });
    let mut out = String::new();
    let mut last_y = sorted[0].bbox.y0;
    let mut last_x_end = sorted[0].bbox.x0;
    let line_break_threshold = sorted[0].font_size * 0.5;
    for (i, s) in sorted.iter().enumerate() {
        if i > 0 {
            if (last_y - s.bbox.y0).abs() > line_break_threshold {
                out.push('\n');
            } else if s.bbox.x0 - last_x_end > s.font_size * 0.25 {
                if !out.ends_with(' ') && !out.is_empty() {
                    out.push(' ');
                }
            }
        }
        out.push_str(&s.text);
        last_y = s.bbox.y0;
        last_x_end = s.bbox.x1;
    }
    out
}

#[derive(Clone)]
struct AssembledBlock {
    text: String,
    bbox: Rect,
    lines: Vec<TextLine>,
}

// ── MuPDF stext-style block segmentation ────────────────────────────────────
//
// Ported from MuPDF `stext-device.c`. All distances are em-normalized
// (divided by glyph size); without this normalization, a 6pt footnote and
// an 18pt title share absolute thresholds and segmentation collapses.

/// Em-normalized `|base_offset|` below which two spans share a line.
const BASE_MAX_DIST: f32 = 0.8;
/// Em-normalized `|base_offset|` above which two spans start a new block.
const PARAGRAPH_DIST: f32 = 1.5;
#[allow(dead_code)]
const SPACE_DIST: f32 = 0.15;
/// Em-normalized along-baseline gap above which a same-baseline jump is
/// treated as a column-wrap rather than an inter-word space. MuPDF's
/// per-glyph constant is `0.8`; our unit is one merged span, so we need
/// a threshold that excludes ordinary word gaps (0.3–1.5 em wide) but
/// catches column boundaries. 5.0 em ≈ 50pt at 10pt font — wider than
/// any single word space in justified text.
const SPACE_MAX_DIST: f32 = 5.0;
/// Em-normalized line-start indent above which a new line opens a new
/// block (paragraph-style indent).
const INDENT_NEW_PARA: f32 = 0.5;

/// Group spans into blocks by walking content-stream order and making the
/// MuPDF stext per-span decision: matching writing direction, em-normalized
/// baseline offset, and along-baseline spacing.
///
/// Walks in content-stream order, NOT a geometric sort — emission order is
/// reading order for virtually all files, and a y/x sort conflates columns
/// (which produced one-block-per-page on multi-column dense forms).
fn group_into_blocks(spans: &[TextSpan]) -> Vec<AssembledBlock> {
    if spans.is_empty() {
        return Vec::new();
    }

    // Streaming state:
    // - cur_line_start: (x, y) of the current line's start, anchors indent test
    // - cur_pen: visual cursor after the previous span (bbox.x1, bbox.y0)
    // - cur_block_start_x: leftmost line-start x in the active block

    let mut blocks: Vec<AssembledBlock> = Vec::new();
    let mut current_lines: Vec<TextLine> = Vec::new();
    let mut current_line_spans: Vec<TextSpan> = Vec::new();
    let mut current_block_text = String::new();
    let mut current_block_bbox: Option<Rect> = None;
    let mut cur_line_start: Option<(f32, f32)> = None;
    let mut cur_pen: Option<(f32, f32)> = None;
    let mut cur_block_start_x: Option<f32> = None;
    let mut cur_block_max_fs: f32 = 0.0;

    let flush_line = |line_spans: &mut Vec<TextSpan>,
                      lines: &mut Vec<TextLine>,
                      block_text: &mut String| {
        if line_spans.is_empty() {
            return;
        }
        let mut line_bbox = line_spans[0].bbox;
        let mut text = String::new();
        let mut first = true;
        for s in line_spans.iter() {
            if !first
                && !text.ends_with(' ')
                && !s.text.starts_with(' ')
                && !text.is_empty()
            {
                text.push(' ');
            }
            first = false;
            text.push_str(&s.text);
            line_bbox = line_bbox.union(s.bbox);
        }
        if !block_text.is_empty() {
            block_text.push('\n');
        }
        block_text.push_str(&text);
        lines.push(TextLine {
            text,
            bbox: line_bbox,
            spans: std::mem::take(line_spans),
        });
    };

    let flush_block = |line_spans: &mut Vec<TextSpan>,
                       lines: &mut Vec<TextLine>,
                       block_text: &mut String,
                       block_bbox: &mut Option<Rect>,
                       blocks: &mut Vec<AssembledBlock>| {
        flush_line(line_spans, lines, block_text);
        if lines.is_empty() {
            return;
        }
        blocks.push(AssembledBlock {
            text: std::mem::take(block_text),
            bbox: block_bbox.take().unwrap_or(Rect::ZERO),
            lines: std::mem::take(lines),
        });
    };

    for s in spans {
        let fs = s.font_size.max(1.0);
        let (line_x_start, pen_x, pen_y) = match (cur_line_start, cur_pen) {
            (Some(ls), Some(pen)) => (ls.0, pen.0, pen.1),
            _ => {
                cur_line_start = Some((s.bbox.x0, s.bbox.y0));
                cur_pen = Some((s.bbox.x1, s.bbox.y0));
                cur_block_start_x = Some(s.bbox.x0);
                cur_block_max_fs = fs;
                current_block_bbox = Some(s.bbox);
                current_line_spans.push(s.clone());
                continue;
            }
        };

        // PDF y increases upward; positive dy means new glyph above pen.
        // Assumes horizontal LTR; rotated text would need a per-glyph
        // baseline direction read from the text matrix.
        let dx = s.bbox.x0 - pen_x;
        let dy = s.bbox.y0 - pen_y;
        let spacing = dx / fs;
        let base_offset = dy / fs;

        let same_line = base_offset.abs() < BASE_MAX_DIST;
        let new_block;
        let new_line;
        if same_line {
            if spacing > SPACE_MAX_DIST {
                // Wide same-baseline gap = tabular right-column on same row.
                new_line = true;
                new_block = true;
            } else if spacing < -SPACE_MAX_DIST {
                // Large negative spacing on same baseline = column-wrap.
                new_line = true;
                new_block = true;
            } else {
                new_line = false;
                new_block = false;
            }
        } else if base_offset.abs() <= PARAGRAPH_DIST {
            new_line = true;
            let indent = s.bbox.x0 - cur_block_start_x.unwrap_or(s.bbox.x0);
            let indent_em = indent / fs;
            let _ = line_x_start;
            new_block = indent_em > INDENT_NEW_PARA;
        } else {
            new_line = true;
            new_block = true;
        }

        // Font-size change of >15% combined with any baseline drop opens a
        // new block — separates headings from body even when their gap is
        // small enough to satisfy same-line.
        let fs_changed = (fs - cur_block_max_fs).abs() / cur_block_max_fs.max(1.0) > 0.15
            && base_offset.abs() > 0.05;

        if new_block || fs_changed {
            flush_block(
                &mut current_line_spans,
                &mut current_lines,
                &mut current_block_text,
                &mut current_block_bbox,
                &mut blocks,
            );
            cur_block_start_x = Some(s.bbox.x0);
            cur_block_max_fs = fs;
            cur_line_start = Some((s.bbox.x0, s.bbox.y0));
        } else if new_line {
            flush_line(
                &mut current_line_spans,
                &mut current_lines,
                &mut current_block_text,
            );
            cur_line_start = Some((s.bbox.x0, s.bbox.y0));
        }

        current_block_bbox = Some(match current_block_bbox {
            Some(b) => b.union(s.bbox),
            None => s.bbox,
        });
        cur_block_max_fs = cur_block_max_fs.max(fs);
        cur_pen = Some((s.bbox.x1, s.bbox.y0));
        current_line_spans.push(s.clone());
    }
    flush_block(
        &mut current_line_spans,
        &mut current_lines,
        &mut current_block_text,
        &mut current_block_bbox,
        &mut blocks,
    );
    blocks
}

/// Partition spans into columns by detecting vertical gutters in the
/// x-coverage profile.
///
/// Required because the per-span segmenter assumes reading order; on
/// multi-column pages the content stream often emits "row 1 col A, row 1
/// col B, row 2 col A, …" and a downstream segmenter cross-streams tokens
/// between columns.
///
/// A gutter candidate is a contiguous x-run with coverage ≤ 5% of the
/// peak. Real column gutters are wider than 2× the median font size
/// (narrower runs are inter-word). Edge gutters (margins) are excluded.
fn partition_into_columns(spans: &[TextSpan]) -> Vec<Vec<TextSpan>> {
    if spans.len() < 8 {
        return vec![spans.to_vec()];
    }
    // 1pt resolution is sufficient for column detection.
    let min_x = spans
        .iter()
        .map(|s| s.bbox.x0)
        .fold(f32::INFINITY, f32::min)
        .floor() as i32;
    let max_x = spans
        .iter()
        .map(|s| s.bbox.x1)
        .fold(f32::NEG_INFINITY, f32::max)
        .ceil() as i32;
    if max_x <= min_x + 4 {
        return vec![spans.to_vec()];
    }
    let width = (max_x - min_x) as usize;
    let mut coverage: Vec<u32> = vec![0; width];

    for s in spans {
        let lo = (s.bbox.x0.floor() as i32 - min_x).max(0) as usize;
        let hi = ((s.bbox.x1.ceil() as i32 - min_x) as usize).min(width);
        if lo >= hi {
            continue;
        }
        for c in &mut coverage[lo..hi] {
            *c += 1;
        }
    }
    let max_coverage = coverage.iter().copied().max().unwrap_or(0);
    if max_coverage < 4 {
        return vec![spans.to_vec()];
    }
    let gutter_threshold = (max_coverage / 20).max(1); // 5% of max

    let mut gutters: Vec<(i32, i32)> = Vec::new();
    let mut run_start: Option<usize> = None;
    for (i, &c) in coverage.iter().enumerate() {
        if c <= gutter_threshold {
            run_start.get_or_insert(i);
        } else if let Some(start) = run_start.take() {
            gutters.push((start as i32 + min_x, i as i32 + min_x));
        }
    }
    if let Some(start) = run_start {
        gutters.push((start as i32 + min_x, width as i32 + min_x));
    }

    let median_fs = median_font_size(spans).max(8.0);
    let min_gutter_width = (median_fs * 2.0).round() as i32;
    let mut real_gutters: Vec<(i32, i32)> = gutters
        .into_iter()
        .filter(|(s, e)| {
            let w = e - s;
            // Exclude margins (whitespace before leftmost / after rightmost content).
            w >= min_gutter_width && *s > min_x + 4 && *e < max_x - 4
        })
        .collect();
    // Cap at 4 columns; more than that catches between-row whitespace.
    if real_gutters.len() > 3 {
        real_gutters.sort_by_key(|(s, e)| -(e - s));
        real_gutters.truncate(3);
        real_gutters.sort_by_key(|(s, _)| *s);
    }
    if real_gutters.is_empty() {
        return vec![spans.to_vec()];
    }

    // Span goes into the first interval whose range contains its x-center.
    let mut cuts: Vec<(f32, f32)> = Vec::with_capacity(real_gutters.len() + 1);
    let mut prev_end = min_x as f32;
    for &(g_s, g_e) in &real_gutters {
        cuts.push((prev_end, g_s as f32));
        prev_end = g_e as f32;
    }
    cuts.push((prev_end, max_x as f32));

    let mut columns: Vec<Vec<TextSpan>> = vec![Vec::new(); cuts.len()];
    for s in spans {
        let center = (s.bbox.x0 + s.bbox.x1) / 2.0;
        let idx = cuts
            .iter()
            .position(|(a, b)| center >= *a && center < *b)
            .unwrap_or_else(|| cuts.len() - 1);
        columns[idx].push(s.clone());
    }
    columns.into_iter().filter(|c| !c.is_empty()).collect()
}

fn median_font_size(spans: &[TextSpan]) -> f32 {
    let mut sizes: Vec<f32> = spans.iter().map(|s| s.font_size).collect();
    if sizes.is_empty() {
        return 10.0;
    }
    sizes.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
    sizes[sizes.len() / 2]
}

/// Split-only paragraph refinement. Splits any line whose indent differs
/// by `> 1.0 × line_height` from the block's left edge, whose height
/// differs by `≥ 25%` from the previous line, or that starts a list item.
/// Never merges — the per-span pass is conservative on purpose so this
/// can refine without losing structure.
fn paragraph_break_post_pass(blocks: Vec<AssembledBlock>) -> Vec<AssembledBlock> {
    let mut out = Vec::with_capacity(blocks.len());
    for block in blocks {
        if block.lines.len() < 2 {
            out.push(block);
            continue;
        }
        out.extend(split_block_by_paragraph(block));
    }
    out
}

fn split_block_by_paragraph(block: AssembledBlock) -> Vec<AssembledBlock> {
    let block_start_x = block
        .lines
        .iter()
        .map(|l| l.bbox.x0)
        .fold(f32::INFINITY, f32::min);

    let mut result: Vec<AssembledBlock> = Vec::new();
    let mut cur_lines: Vec<TextLine> = Vec::new();
    let mut cur_text = String::new();
    let mut cur_bbox: Option<Rect> = None;
    let mut prev_height: Option<f32> = None;

    let flush = |cur_lines: &mut Vec<TextLine>,
                 cur_text: &mut String,
                 cur_bbox: &mut Option<Rect>,
                 result: &mut Vec<AssembledBlock>| {
        if cur_lines.is_empty() {
            return;
        }
        result.push(AssembledBlock {
            text: std::mem::take(cur_text),
            bbox: cur_bbox.take().unwrap_or(Rect::ZERO),
            lines: std::mem::take(cur_lines),
        });
    };

    for line in block.lines {
        let line_height = line.bbox.height().max(1.0);
        let mut split = false;
        if let Some(ph) = prev_height {
            if (line_height - ph).abs() / ph.max(1.0) > 0.25 {
                split = true;
            }
        }
        let indent = line.bbox.x0 - block_start_x;
        if indent.abs() > line_height * 1.0 && !cur_lines.is_empty() {
            split = true;
        }
        if !cur_lines.is_empty() && line_starts_list_item(&line.text) {
            split = true;
        }

        if split && !cur_lines.is_empty() {
            flush(&mut cur_lines, &mut cur_text, &mut cur_bbox, &mut result);
        }
        if !cur_text.is_empty() {
            cur_text.push('\n');
        }
        cur_text.push_str(&line.text);
        cur_bbox = Some(match cur_bbox {
            Some(b) => b.union(line.bbox),
            None => line.bbox,
        });
        prev_height = Some(line_height);
        cur_lines.push(line);
    }
    flush(&mut cur_lines, &mut cur_text, &mut cur_bbox, &mut result);
    result
}

/// Split a single-line block in the top/bottom 8% band on a wide
/// intra-line gap (`> 3× max_font_size`). Catches running headers like
/// `CHAPTER 11. PERLBOT  11.3. INSTANCE VARIABLES` that share a baseline
/// but carry two independent labels.
fn header_footer_split(blocks: Vec<AssembledBlock>, page_height: f32) -> Vec<AssembledBlock> {
    if page_height <= 0.0 {
        return blocks;
    }
    let header_band_bottom = page_height * 0.92;
    let footer_band_top = page_height * 0.08;
    let mut out: Vec<AssembledBlock> = Vec::with_capacity(blocks.len());
    for block in blocks {
        if block.lines.len() != 1 {
            out.push(block);
            continue;
        }
        let line = &block.lines[0];
        let y = (line.bbox.y0 + line.bbox.y1) / 2.0;
        let is_in_header_band = y >= header_band_bottom;
        let is_in_footer_band = y <= footer_band_top;
        if !is_in_header_band && !is_in_footer_band {
            out.push(block);
            continue;
        }
        let max_fs = line.spans.iter().map(|s| s.font_size).fold(0.0f32, f32::max).max(1.0);
        let gap_threshold = max_fs * 3.0;
        let mut spans_sorted = line.spans.clone();
        spans_sorted.sort_by(|a, b| {
            a.bbox
                .x0
                .partial_cmp(&b.bbox.x0)
                .unwrap_or(std::cmp::Ordering::Equal)
        });
        let mut split_at: Option<usize> = None;
        for (i, pair) in spans_sorted.windows(2).enumerate() {
            let gap = pair[1].bbox.x0 - pair[0].bbox.x1;
            if gap > gap_threshold {
                split_at = Some(i + 1);
                break;
            }
        }
        let Some(idx) = split_at else {
            out.push(block);
            continue;
        };
        let (left, right) = spans_sorted.split_at(idx);
        for cluster in [left, right] {
            if cluster.is_empty() {
                continue;
            }
            let mut bbox = cluster[0].bbox;
            let mut text = String::new();
            for s in cluster {
                if !text.is_empty() && !text.ends_with(' ') {
                    text.push(' ');
                }
                text.push_str(&s.text);
                bbox = bbox.union(s.bbox);
            }
            let new_line = TextLine {
                text: text.clone(),
                bbox,
                spans: cluster.to_vec(),
            };
            out.push(AssembledBlock {
                text,
                bbox,
                lines: vec![new_line],
            });
        }
    }
    out
}

/// Detect a list-item marker prefix: Unicode bullet, `(a)`/`(i)`,
/// `1.`/`2)`, smart-quoted legal-style `‘‘(b)`. Conservative on purpose
/// — false negatives are preferable to splitting a paragraph that
/// opens with "1990 was a year of…".
fn line_starts_list_item(text: &str) -> bool {
    let trimmed = text.trim_start_matches(|c: char| c.is_whitespace() || c == '\u{2018}' || c == '\u{201C}' || c == '\'' || c == '"');
    if trimmed.is_empty() {
        return false;
    }
    let mut chars = trimmed.chars();
    let first = match chars.next() {
        Some(c) => c,
        None => return false,
    };
    if matches!(
        first,
        '\u{2022}'   // •
        | '\u{25E6}' // ◦
        | '\u{2023}' // ‣
        | '\u{25A0}' // ■
        | '\u{25CF}' // ●
        | '\u{2043}' // ⁃
        | '\u{2219}' // ∙
        | '\u{2014}' // — (em-dash)
        | '\u{2013}' // – (en-dash)
    ) {
        // Require trailing whitespace so we don't trip on "—5 years later".
        return matches!(chars.next(), Some(c) if c.is_whitespace());
    }
    if first == '(' {
        let mut iter = chars.clone();
        let mut depth = 1usize;
        let mut consumed = 0usize;
        for c in iter.by_ref() {
            consumed += 1;
            if c == ')' {
                depth -= 1;
                break;
            }
            if !c.is_alphanumeric() {
                return false;
            }
            if depth == 0 || consumed > 6 {
                return false;
            }
        }
        if depth != 0 {
            return false;
        }
        return matches!(iter.next(), Some(c) if c.is_whitespace() || c.is_ascii_punctuation())
            || iter.next().is_none();
    }
    // `1.` / `2)` / `iv.` — up to 4 alphanumerics, `.` or `)`, whitespace.
    if first.is_alphanumeric() {
        let mut prefix_len = 1;
        let mut iter = chars.clone();
        while let Some(c) = iter.next() {
            if c.is_alphanumeric() && prefix_len < 4 {
                prefix_len += 1;
            } else if c == '.' || c == ')' {
                return matches!(iter.next(), Some(c) if c.is_whitespace());
            } else {
                return false;
            }
        }
    }
    false
}

struct WordOut {
    text: String,
    bbox: Rect,
}

/// Split a span on whitespace, proportioning the bbox by character count.
fn split_span_into_words(span: &TextSpan) -> Vec<WordOut> {
    let mut out = Vec::new();
    let total_chars = span.text.chars().count() as f32;
    if total_chars <= 0.0 {
        return out;
    }
    let bbox_w = span.bbox.width();
    let x_per_char = if total_chars > 0.0 { bbox_w / total_chars } else { 0.0 };
    let mut char_offset = 0usize;
    for word in span.text.split_whitespace() {
        let word_chars = word.chars().count();
        if word_chars == 0 {
            continue;
        }
        let start_idx = match span.text[char_offset.min(span.text.len())..].find(word) {
            Some(i) => char_offset + i,
            None => char_offset,
        };
        let start_chars = span.text[..start_idx].chars().count() as f32;
        let x0 = span.bbox.x0 + x_per_char * start_chars;
        let x1 = x0 + x_per_char * word_chars as f32;
        out.push(WordOut {
            text: word.to_string(),
            bbox: Rect::new(x0, span.bbox.y0, x1, span.bbox.y1),
        });
        char_offset = start_idx + word.len();
    }
    out
}