pdf-inspector 0.1.6

//! Line-based table detection.
//!
//! Detects tables from PDF path operators (`m`/`l`/`S`) that draw ruled
//! gridlines.  Many IRS forms and government PDFs use these instead of
//! `re` (rectangle) operators.

use std::collections::HashSet;

use crate::tables::Table;
use crate::types::{PdfLine, TextItem};

use super::detect_rects::{assign_items_to_grid, snap_edges};

/// Derive column edges from the x-endpoints of horizontal-rule
/// segments when no vertical lines were drawn.
///
/// Catalog and archival-finding-aid tables are commonly drawn with
/// per-row horizontal rules broken into N segments (one segment per
/// cell), with no vertical dividers at all. The segment break points
/// (e.g. `[50, 127], [127, 485], [485, 562]` per row) implicitly
/// encode the column boundaries.
///
/// Returns column edges if ≥3 distinct x-positions each show up as a
/// segment endpoint on ≥50% of the unique horizontal-line rows.
/// Returns `None` otherwise — decorative rules with varying widths
/// shouldn't be mistaken for a table.
fn derive_columns_from_horizontal_segments(horizontals: &[(f32, f32, f32)]) -> Option<Vec<f32>> {
    if horizontals.len() < 3 {
        return None;
    }

    let mut endpoints: Vec<f32> = Vec::with_capacity(horizontals.len() * 2);
    for &(_, x_min, x_max) in horizontals {
        endpoints.push(x_min);
        endpoints.push(x_max);
    }
    let clusters = snap_edges(&endpoints, 5.0);
    if clusters.len() < 3 {
        return None;
    }

    // Bucket y-values to count unique rows. Tolerance ~0.1pt (×10
    // rounding) tolerates the snap_edges 3pt clustering used later
    // for row edges.
    let unique_rows: HashSet<i32> = horizontals
        .iter()
        .map(|&(y, _, _)| (y * 10.0).round() as i32)
        .collect();
    if unique_rows.len() < 2 {
        return None;
    }
    let min_rows = (unique_rows.len() as f32 * 0.5).ceil() as usize;

    let qualifying: Vec<f32> = clusters
        .iter()
        .copied()
        .filter(|&cluster_x| {
            let rows_touched: HashSet<i32> = horizontals
                .iter()
                .filter(|&&(_, x_min, x_max)| {
                    (x_min - cluster_x).abs() < 5.0 || (x_max - cluster_x).abs() < 5.0
                })
                .map(|&(y, _, _)| (y * 10.0).round() as i32)
                .collect();
            rows_touched.len() >= min_rows
        })
        .collect();

    if qualifying.len() < 3 {
        return None;
    }
    Some(qualifying)
}

/// Detect tables from line segments on a given page.
///
/// Lines are classified as horizontal or vertical, snapped into grid edges,
/// and validated before assigning text items to the resulting grid.
pub fn detect_tables_from_lines(items: &[TextItem], lines: &[PdfLine], page: u32) -> Vec<Table> {
    // Filter lines for this page
    let page_lines: Vec<&PdfLine> = lines.iter().filter(|l| l.page == page).collect();
    if page_lines.is_empty() {
        return Vec::new();
    }

    // Classify lines as horizontal or vertical (within 2° of axis)
    let mut horizontals: Vec<(f32, f32, f32)> = Vec::new(); // (y, x_min, x_max)
    let mut verticals: Vec<(f32, f32, f32)> = Vec::new(); // (x, y_min, y_max)

    let angle_tolerance = 2.0_f32.to_radians().tan(); // ~0.035

    for line in &page_lines {
        let dx = (line.x2 - line.x1).abs();
        let dy = (line.y2 - line.y1).abs();
        let length = (dx * dx + dy * dy).sqrt();

        // Skip very short lines (decorations, tick marks)
        if length < 20.0 {
            continue;
        }

        if dx > 0.01 && dy / dx <= angle_tolerance {
            // Horizontal line
            let y = (line.y1 + line.y2) / 2.0;
            let x_min = line.x1.min(line.x2);
            let x_max = line.x1.max(line.x2);
            horizontals.push((y, x_min, x_max));
        } else if dy > 0.01 && dx / dy <= angle_tolerance {
            // Vertical line
            let x = (line.x1 + line.x2) / 2.0;
            let y_min = line.y1.min(line.y2);
            let y_max = line.y1.max(line.y2);
            verticals.push((x, y_min, y_max));
        }
        // Diagonal lines are ignored
    }

    if horizontals.len() < 3 {
        return Vec::new();
    }

    // If no/very-few vertical lines are drawn, try to derive column edges
    // from the x-endpoints of the horizontal-rule segments. Catalog and
    // archival-finding-aid layouts commonly draw each row's horizontal
    // rule as N segments (one per cell), with no vertical dividers at
    // all — the segment break points encode the column boundaries.
    let implicit_col_edges: Option<Vec<f32>> = if verticals.len() < 2 {
        derive_columns_from_horizontal_segments(&horizontals)
    } else {
        None
    };
    if verticals.len() < 2 && implicit_col_edges.is_none() {
        return Vec::new();
    }
    let cols_from_segments = implicit_col_edges.is_some();

    log::debug!(
        "detect_lines p{}: {} horiz, {} vert lines (of {} total on page){}",
        page,
        horizontals.len(),
        verticals.len(),
        page_lines.len(),
        if cols_from_segments {
            " — columns from horizontal segments"
        } else {
            ""
        }
    );

    // Snap Y-values of horizontal lines → row edges
    let h_ys: Vec<f32> = horizontals.iter().map(|(y, _, _)| *y).collect();
    let row_edges = snap_edges(&h_ys, 3.0);

    // Column edges from drawn verticals when present, else from the
    // horizontal-segment endpoints derived above.
    let col_edges = if let Some(c) = implicit_col_edges {
        c
    } else {
        let v_xs: Vec<f32> = verticals.iter().map(|(x, _, _)| *x).collect();
        snap_edges(&v_xs, 3.0)
    };

    log::debug!(
        "detect_lines p{}: {} row edges, {} col edges after snap",
        page,
        row_edges.len(),
        col_edges.len()
    );

    // Require at least 2 columns (3 col edges) and 2 rows (3 row edges).
    // A single column of horizontal lines is just separator rules, not a table.
    if row_edges.len() < 3 || col_edges.len() < 3 {
        return Vec::new();
    }

    // Cap grid size: >20 columns is almost certainly a diagram, not a table
    if col_edges.len() > 21 || row_edges.len() > 80 {
        log::debug!(
            "detect_lines p{}: rejected — too many edges ({}x{})",
            page,
            row_edges.len(),
            col_edges.len()
        );
        return Vec::new();
    }

    let table_x_min = col_edges.first().copied().unwrap_or(0.0);
    let table_x_max = col_edges.last().copied().unwrap_or(0.0);
    let table_width = table_x_max - table_x_min;
    if table_width < 50.0 {
        return Vec::new();
    }

    let table_y_min = row_edges.first().copied().unwrap_or(0.0);
    let table_y_max = row_edges.last().copied().unwrap_or(0.0);
    let table_height = (table_y_max - table_y_min).abs();
    if table_height < 20.0 {
        return Vec::new();
    }

    // Reject page-spanning frames: a decorative outer border has just 4
    // edges (top/bottom/left/right). Real full-page tables — common in
    // governmental ledgers, financial reports, etc. — span the same A4 /
    // Letter dimensions but have many internal row/column rules. Only
    // reject when the line set looks like a bare frame, not a grid.
    // Standard pages are ~595×842 (A4) or ~612×792 (Letter).
    if table_width > 500.0 && table_height > 700.0 && horizontals.len() <= 4 && verticals.len() <= 4
    {
        log::debug!(
            "detect_lines p{}: rejected — page-spanning frame ({:.0}×{:.0}, {} h + {} v)",
            page,
            table_width,
            table_height,
            horizontals.len(),
            verticals.len()
        );
        return Vec::new();
    }

    // Validate horizontal lines: at least 3 should span a meaningful width.
    // Full-width spanning (>50%) is ideal, but tables with partial horizontal
    // rules (column-level separators) are also valid if there are enough.
    let spanning_h = horizontals
        .iter()
        .filter(|(_, x_min, x_max)| (x_max - x_min) > table_width * 0.5)
        .count();
    let partial_h = horizontals
        .iter()
        .filter(|(_, x_min, x_max)| (x_max - x_min) > table_width * 0.15)
        .count();
    if spanning_h < 3 && partial_h < 6 {
        log::debug!(
            "detect_lines p{}: rejected — {} spanning + {} partial H lines",
            page,
            spanning_h,
            partial_h
        );
        return Vec::new();
    }

    // Validate vertical lines: at least 2 should span a meaningful height.
    // Full spanning (>30%) is ideal, but accept many shorter lines (>10%)
    // for tables with partial column separators. Skipped entirely when
    // columns came from horizontal-segment endpoints — there are no
    // vertical lines to validate against, and the segment-endpoint
    // consistency check in `derive_columns_from_horizontal_segments`
    // is the equivalent guard.
    let spanning_v = if cols_from_segments {
        0
    } else {
        let s = verticals
            .iter()
            .filter(|(_, y_min, y_max)| (y_max - y_min) > table_height * 0.3)
            .count();
        let p = verticals
            .iter()
            .filter(|(_, y_min, y_max)| (y_max - y_min) > table_height * 0.10)
            .count();
        if s < 2 && p < 4 {
            log::debug!(
                "detect_lines p{}: rejected — {} spanning + {} partial V lines",
                page,
                s,
                p
            );
            return Vec::new();
        }
        s
    };

    // Row edges need to be in descending order (top of page = higher Y first)
    let mut row_edges_desc = row_edges;
    row_edges_desc.sort_by(|a, b| b.total_cmp(a));

    log::debug!(
        "detect_lines p{}: {} row_edges, {} col_edges, table=({:.0},{:.0})-({:.0},{:.0}), spanning_h={}, spanning_v={}",
        page, row_edges_desc.len(), col_edges.len(),
        table_x_min, table_y_min, table_x_max, table_y_max,
        spanning_h, spanning_v
    );

    // Assign items to grid
    let (cells, item_indices) = assign_items_to_grid(items, &col_edges, &row_edges_desc, page);

    // Require at least 2 non-empty rows
    let non_empty_rows = cells
        .iter()
        .filter(|row| row.iter().any(|cell| !cell.is_empty()))
        .count();
    if non_empty_rows < 2 {
        return Vec::new();
    }

    // Content density: at least 15% of cells should have content
    let num_cols_grid = cells.first().map_or(0, |r| r.len());
    let total_cells = cells.len() * num_cols_grid;
    if total_cells > 0 {
        let filled_cells = cells
            .iter()
            .flat_map(|row| row.iter())
            .filter(|cell| !cell.is_empty())
            .count();
        let density = filled_cells as f32 / total_cells as f32;
        if density < 0.15 {
            return Vec::new();
        }
    }

    // Require that at least 2 distinct columns have content.
    // Charts/diagrams have text concentrated on axes (1 column);
    // real tables spread data across multiple columns.
    let cols_with_content = (0..num_cols_grid)
        .filter(|&c| {
            cells
                .iter()
                .any(|row| row.get(c).is_some_and(|cell| !cell.is_empty()))
        })
        .count();
    if cols_with_content < 2 {
        return Vec::new();
    }

    // The grid must capture a meaningful portion of the page's text items.
    // Chart/graph grids on textbook pages capture scattered labels but miss
    // the bulk of the page content (explanatory text, problem statements).
    let page_item_count = items.iter().filter(|i| i.page == page).count();
    if page_item_count > 0 {
        let capture_ratio = item_indices.len() as f32 / page_item_count as f32;
        // If the grid captures less than 20% of items, it's not a real table
        if capture_ratio < 0.20 {
            return Vec::new();
        }
    }

    // Reject grids with very uniform row spacing — likely chart gridlines.
    // Real tables have variable row heights; chart Y-axes have equal spacing.
    if row_edges_desc.len() >= 5 {
        let spacings: Vec<f32> = row_edges_desc
            .windows(2)
            .map(|w| (w[0] - w[1]).abs())
            .collect();
        let mean_spacing = spacings.iter().sum::<f32>() / spacings.len() as f32;
        if mean_spacing > 0.1 {
            let variance = spacings
                .iter()
                .map(|s| (s - mean_spacing).powi(2))
                .sum::<f32>()
                / spacings.len() as f32;
            let cv = variance.sqrt() / mean_spacing;
            // CV < 0.02 means nearly identical spacing — likely chart grid.
            // Spreadsheet-exported tables often have uniform rows (CV 0.03-0.05),
            // so we use a tighter threshold to avoid false negatives.
            if cv < 0.02 {
                return Vec::new();
            }
        }
    }

    let num_cols = col_edges.len() - 1;
    let num_rows = row_edges_desc.len() - 1;

    if num_rows < 2 || num_cols < 2 {
        return Vec::new();
    }

    log::debug!(
        "detect_lines p{}: ACCEPTED {}x{} grid, {} items captured of {} on page, non_empty_rows={}, cols_with_content={}",
        page, num_rows, num_cols, item_indices.len(), page_item_count, non_empty_rows, cols_with_content
    );

    vec![Table::new(
        col_edges,
        row_edges_desc[..num_rows].to_vec(),
        cells,
        item_indices,
    )]
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::types::ItemType;

    fn make_item(text: &str, x: f32, y: f32, page: u32) -> TextItem {
        TextItem {
            text: text.into(),
            x,
            y,
            width: 30.0,
            height: 10.0,
            font: "F1".into(),
            font_size: 10.0,
            page,
            is_bold: false,
            is_italic: false,
            is_underline: false,
            is_strikeout: false,
            item_type: ItemType::Text,
            mcid: None,
        }
    }

    fn make_hline(y: f32, x1: f32, x2: f32, page: u32) -> PdfLine {
        PdfLine {
            x1,
            y1: y,
            x2,
            y2: y,
            page,
        }
    }

    fn make_vline(x: f32, y1: f32, y2: f32, page: u32) -> PdfLine {
        PdfLine {
            x1: x,
            y1,
            x2: x,
            y2,
            page,
        }
    }

    #[test]
    fn test_basic_grid_detection() {
        // 3x2 grid with horizontal lines at y=500, 480, 460 and vertical at x=100, 200, 300
        let lines = vec![
            make_hline(500.0, 100.0, 300.0, 1),
            make_hline(480.0, 100.0, 300.0, 1),
            make_hline(460.0, 100.0, 300.0, 1),
            make_vline(100.0, 460.0, 500.0, 1),
            make_vline(200.0, 460.0, 500.0, 1),
            make_vline(300.0, 460.0, 500.0, 1),
        ];

        let items = vec![
            make_item("Col A", 110.0, 490.0, 1),
            make_item("Col B", 210.0, 490.0, 1),
            make_item("val 1", 110.0, 470.0, 1),
            make_item("val 2", 210.0, 470.0, 1),
        ];

        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert_eq!(tables.len(), 1);
        assert_eq!(tables[0].cells.len(), 2); // 2 data rows
        assert_eq!(tables[0].cells[0].len(), 2); // 2 columns
    }

    #[test]
    fn test_short_lines_ignored() {
        // Lines shorter than 20pt should be ignored
        let lines = vec![
            make_hline(500.0, 100.0, 110.0, 1), // 10pt - too short
            make_hline(480.0, 100.0, 115.0, 1), // 15pt - too short
            make_hline(460.0, 100.0, 112.0, 1), // 12pt - too short
        ];

        let items = vec![make_item("text", 105.0, 490.0, 1)];

        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert!(tables.is_empty());
    }

    #[test]
    fn test_wrong_page_ignored() {
        let lines = vec![
            make_hline(500.0, 100.0, 300.0, 2),
            make_hline(480.0, 100.0, 300.0, 2),
            make_hline(460.0, 100.0, 300.0, 2),
            make_vline(100.0, 460.0, 500.0, 2),
            make_vline(200.0, 460.0, 500.0, 2),
            make_vline(300.0, 460.0, 500.0, 2),
        ];

        let items = vec![make_item("text", 110.0, 490.0, 1)];

        // Request page 1, but lines are on page 2
        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert!(tables.is_empty());
    }

    #[test]
    fn test_empty_grid_rejected() {
        // Grid with no text items inside
        let lines = vec![
            make_hline(500.0, 100.0, 300.0, 1),
            make_hline(480.0, 100.0, 300.0, 1),
            make_hline(460.0, 100.0, 300.0, 1),
            make_vline(100.0, 460.0, 500.0, 1),
            make_vline(200.0, 460.0, 500.0, 1),
            make_vline(300.0, 460.0, 500.0, 1),
        ];

        let items: Vec<TextItem> = Vec::new();

        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert!(tables.is_empty());
    }

    #[test]
    fn test_horizontal_rules_not_table() {
        // Only horizontal lines with no verticals — separator rules, not a table
        let lines = vec![
            make_hline(500.0, 100.0, 500.0, 1),
            make_hline(480.0, 100.0, 500.0, 1),
            make_hline(460.0, 100.0, 500.0, 1),
            make_hline(440.0, 100.0, 500.0, 1),
        ];

        let items = vec![
            make_item("text1", 110.0, 490.0, 1),
            make_item("text2", 110.0, 470.0, 1),
        ];

        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert!(tables.is_empty());
    }

    #[test]
    fn test_horizontal_segments_only_implicit_columns_accepted() {
        // Catalog/finding-aid pattern: each row's horizontal rule is
        // drawn as 3 segments at consistent x-endpoints (50, 127, 485,
        // 562), with no vertical lines anywhere. The segment break
        // points must be inferred as column edges.
        let mut lines = Vec::new();
        // Slightly uneven row spacing so the chart-gridline rejector
        // (CV < 0.02) doesn't fire.
        let row_ys = [80.0_f32, 145.0, 215.0, 280.0, 350.0, 415.0, 485.0];
        for &y in &row_ys {
            lines.push(make_hline(y, 50.0, 127.0, 1));
            lines.push(make_hline(y, 127.0, 485.0, 1));
            lines.push(make_hline(y, 485.0, 562.0, 1));
        }
        // Populate every cell so capture / density checks pass.
        let mut items = Vec::new();
        for w in row_ys.windows(2) {
            let row_y = (w[0] + w[1]) / 2.0;
            items.push(make_item("id", 80.0, row_y, 1));
            items.push(make_item("description here", 200.0, row_y, 1));
            items.push(make_item("date", 510.0, row_y, 1));
        }
        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert_eq!(
            tables.len(),
            1,
            "horizontal-segment-only grid should be accepted"
        );
        let t = &tables[0];
        assert!(
            t.cells.len() >= 4,
            "expected ≥4 rows, got {}",
            t.cells.len()
        );
        assert_eq!(t.cells[0].len(), 3, "expected 3 columns");
    }

    #[test]
    fn test_horizontal_segments_with_inconsistent_endpoints_rejected() {
        // Decorative rules of varying widths shouldn't be detected as a
        // table — each line has its own x-endpoints, no consistent
        // column boundary survives the 50%-of-rows threshold.
        let lines = vec![
            make_hline(100.0, 50.0, 150.0, 1),
            make_hline(200.0, 50.0, 220.0, 1),
            make_hline(300.0, 50.0, 310.0, 1),
            make_hline(400.0, 50.0, 470.0, 1),
        ];
        let items = vec![
            make_item("decorative", 100.0, 150.0, 1),
            make_item("text", 100.0, 250.0, 1),
        ];
        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert!(
            tables.is_empty(),
            "varying-width decorative rules should not be detected"
        );
    }

    #[test]
    fn test_page_spanning_bare_frame_rejected() {
        // Just an outer A4-sized rectangle: 2 horizontals + 2 verticals.
        // No internal structure → decorative border, not a table.
        let lines = vec![
            make_hline(20.0, 20.0, 575.0, 1),  // top
            make_hline(820.0, 20.0, 575.0, 1), // bottom
            make_vline(20.0, 20.0, 820.0, 1),  // left
            make_vline(575.0, 20.0, 820.0, 1), // right
        ];
        let items = vec![
            make_item("title", 100.0, 100.0, 1),
            make_item("body", 100.0, 200.0, 1),
        ];
        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert!(
            tables.is_empty(),
            "Page-sized 4-edge frame should be rejected as decoration"
        );
    }

    #[test]
    fn test_page_spanning_grid_with_internal_lines_accepted() {
        // Full-page table (governmental-ledger pattern): A4-sized grid
        // that previously hit the "page-spanning frame" early reject
        // before downstream validation could even look at it.
        // Verticals span the full table height so we isolate the
        // frame-vs-grid decision under test.
        let mut lines = Vec::new();
        // 13 horizontal rules: header + 12 row separators
        let h_ys = [
            22.5, 37.9, 95.5, 144.5, 184.9, 233.9, 291.7, 340.7, 415.8, 499.6, 574.7, 623.7, 698.8,
        ];
        for &y in &h_ys {
            lines.push(make_hline(y, 22.6, 566.6, 1));
        }
        // 7 column dividers spanning full table height.
        let v_xs = [22.6, 66.3, 116.3, 186.6, 263.1, 493.5, 566.5];
        for &x in &v_xs {
            lines.push(make_vline(x, 22.5, 698.8, 1));
        }
        // Populate every cell so the capture-ratio + density checks pass.
        let mut items = Vec::new();
        for r in 0..(h_ys.len() - 1) {
            let row_y = (h_ys[r] + h_ys[r + 1]) / 2.0;
            for c in 0..(v_xs.len() - 1) {
                let col_x = (v_xs[c] + v_xs[c + 1]) / 2.0;
                items.push(make_item("x", col_x, row_y, 1));
            }
        }
        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert_eq!(
            tables.len(),
            1,
            "Full-page table with internal grid should be accepted"
        );
        let t = &tables[0];
        assert!(
            t.cells.len() >= 6,
            "expected ≥6 rows, got {}",
            t.cells.len()
        );
        assert!(
            t.cells[0].len() >= 3,
            "expected ≥3 columns, got {}",
            t.cells[0].len()
        );
    }

    #[test]
    fn test_single_column_rejected() {
        // Only 2 col edges (1 column) — not a table even with verticals
        let lines = vec![
            make_hline(500.0, 100.0, 200.0, 1),
            make_hline(480.0, 100.0, 200.0, 1),
            make_hline(460.0, 100.0, 200.0, 1),
            make_vline(100.0, 460.0, 500.0, 1),
            make_vline(200.0, 460.0, 500.0, 1),
        ];

        let items = vec![
            make_item("a", 110.0, 490.0, 1),
            make_item("b", 110.0, 470.0, 1),
        ];

        let tables = detect_tables_from_lines(&items, &lines, 1);
        assert!(
            tables.is_empty(),
            "Single-column grid should not be a table"
        );
    }
}