GitCorner

Code

ossartcraftcadcraft🌐
a770fa5a5e5f
//! TABLE geometry from the table's cell styles: cell fills, borders and texts. Shared by the
//! display list and the DXF writer (which stores the same geometry as the table's block).

use std::collections::HashMap;

use cadcraft_color::Color;
use cadcraft_doc::{CellBorder, CellStyle, Drawing, Lineweight, Table, TableStyle};
use cadcraft_geom::Vec2;

use crate::{Builder, Ctx, Ink, ink};

/// The most cells laid out (rows × columns); larger tables draw only their outline.
pub const MAX_LAYOUT_CELLS: usize = 1_000_000;

/// A border segment.
#[derive(Clone, Debug, PartialEq)]
pub struct TableLine {
    pub a: Vec2,
    pub b: Vec2,
    pub color: Color,
    pub lineweight: Lineweight,
}

/// A cell background.
#[derive(Clone, Debug, PartialEq)]
pub struct TableFill {
    /// Corners, counter-clockwise from the bottom left.
    pub corners: [Vec2; 4],
    pub color: Color,
}

/// A cell's text, placed at its alignment point.
#[derive(Clone, Debug, PartialEq)]
pub struct TableText {
    pub row: usize,
    pub col: usize,
    pub at: Vec2,
    /// MTEXT attachment (1 top left … 9 bottom right).
    pub attach: u8,
    pub height: f64,
    pub color: Color,
    pub style: String,
    pub text: String,
}

/// Everything a table draws, in world coordinates.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct TableGeom {
    pub fills: Vec<TableFill>,
    pub lines: Vec<TableLine>,
    pub texts: Vec<TableText>,
}

/// Which cells are covered by a merge (and so not drawn on their own).
pub fn table_covered(t: &Table) -> Vec<Vec<bool>> {
    coverage(t).unwrap_or_else(|partial| partial)
}

// No partial coverage may reach owner assignment: it would revisit unbounded merge rectangles.
/// Mark cells covered by merges under grid-size and marking-work limits.
/// Return partial coverage as an error so layout can use its outline fallback instead of assigning owners.
fn coverage(t: &Table) -> Result<Vec<Vec<bool>>, Vec<Vec<bool>>> {
    let rows = t.row_heights.len().min(10_000);
    let cols = t.col_widths.len().min(10_000);
    if rows.saturating_mul(cols) > MAX_LAYOUT_CELLS {
        return Err(vec![Vec::new(); rows]);
    }
    let mut cov = vec![vec![false; cols]; rows];
    // Coverage marking visits each merge's whole rectangle. Overlapping merges re-mark cells that
    // are already covered, so bound the total marking steps to a small multiple of the cell count
    // rather than letting overlapping declarations cause quadratic work (CWE-407).
    let mut budget: u64 = (rows as u64).saturating_mul(cols as u64).saturating_mul(4).saturating_add(1024);
    for (r, row) in t.cells.iter().enumerate().take(rows) {
        for (c, cell) in row.iter().enumerate().take(cols) {
            if let Some((rs, cs)) = cell.merged {
                for rr in r..(r + rs.max(1) as usize).min(rows) {
                    for cc in c..(c + cs.max(1) as usize).min(cols) {
                        budget = budget.saturating_sub(1);
                        if budget == 0 {
                            return Err(cov);
                        }
                        if (rr, cc) != (r, c)
                            && let Some(x) = cov.get_mut(rr).and_then(|v| v.get_mut(cc))
                        {
                            *x = true;
                        }
                    }
                }
            }
        }
    }
    Ok(cov)
}

/// The table style a table uses (Standard defaults when missing).
pub fn table_style_of(d: &Drawing, t: &Table) -> TableStyle {
    d.table_styles.iter().find(|s| s.name.eq_ignore_ascii_case(&t.style)).cloned().unwrap_or_default()
}

/// The scale of a table relative to its style: SCALE changes the table's text height, and every
/// cell style height and margin follows.
fn style_scale(st: &TableStyle, t: &Table) -> f64 {
    // A table from another writer is resolved to its style's height on reading (scale 1); a
    // non-positive height here is the same "no scale of its own".
    let k = t.text_height / st.text_height;
    if k.is_finite() && k > 0.0 { k } else { 1.0 }
}

/// Column and row edge offsets (x right, y down from the insertion point).
fn edges(sizes: &[f64], n: usize) -> Vec<f64> {
    let mut out = Vec::with_capacity(n + 1);
    out.push(0.0);
    let mut acc = 0.0;
    for s in sizes.iter().take(n) {
        acc += if s.is_finite() { *s } else { 0.0 };
        out.push(acc);
    }
    out
}

/// A merged cell (or a plain one): its anchor, span and cell style.
struct Anchor {
    row: usize,
    col: usize,
    rows: usize,
    cols: usize,
    style: usize,
}

/// Lay out table `t` of drawing `d`, every part of a broken table.
pub fn table_geometry(d: &Drawing, t: &Table) -> TableGeom {
    let parts = t.parts();
    if parts.len() <= 1 {
        return layout(d, t);
    }
    // Every part is laid out and kept, so the cells of all of them count together (a header repeated
    // on each part adds to each); past the limit only the table's outline is drawn.
    let cols = t.col_widths.len().min(10_000);
    let total: usize = parts.iter().map(|p| p.rows.len().min(10_000).saturating_mul(cols)).fold(0, usize::saturating_add);
    if total > MAX_LAYOUT_CELLS {
        // One outline per part, at the part's origin and as tall as its displayed rows.
        let w = edges(&t.col_widths, cols).last().copied().unwrap_or(0.0);
        let mut g = TableGeom::default();
        for p in parts {
            let h: f64 = p.rows.iter().take(10_000).map(|r| t.row_heights.get(*r).copied().filter(|v| v.is_finite()).unwrap_or(0.0)).sum();
            outline_box(&mut g, p.origin, w, h);
        }
        return g;
    }
    let mut g = TableGeom::default();
    for p in parts {
        let mut pg = layout(d, &part_table(t, &p.rows, p.origin));
        for tx in &mut pg.texts {
            tx.row = p.rows.get(tx.row).copied().unwrap_or(tx.row);
        }
        g.fills.extend(pg.fills);
        g.lines.extend(pg.lines);
        g.texts.extend(pg.texts);
    }
    g
}

/// One part of a broken table as a table of its own: its rows (with their cell styles) at
/// `origin`; merges are cut at the part's edge.
fn part_table(t: &Table, rows: &[usize], origin: Vec2) -> Table {
    let cols = t.col_widths.len().min(10_000);
    let mut cells: Vec<Vec<cadcraft_doc::TableCell>> =
        rows.iter().take(10_000).map(|r| t.cells.get(*r).map(|row| row.iter().take(cols).cloned().collect()).unwrap_or_default()).collect();
    // Only expand sparse rows to the full column count when detailed layout is actually permitted.
    // Otherwise `layout` renders an outline, so materialising millions of empty cells here would be
    // wasted work an attacker can trigger with a compact dimension array (CWE-789).
    if rows.len().min(10_000).saturating_mul(cols) <= MAX_LAYOUT_CELLS {
        // `run[i]`: how many rows from part row `i` follow one another in the table, found once so a
        // merge is cut by a lookup, not by walking the rows it spans.
        let mut run = vec![1u32; rows.len()];
        for i in (0..rows.len().saturating_sub(1)).rev() {
            if rows.get(i + 1).zip(rows.get(i)).is_some_and(|(next, this)| *next == this + 1) {
                run[i] = run.get(i + 1).copied().unwrap_or(0).saturating_add(1);
            }
        }
        for (i, row) in cells.iter_mut().enumerate() {
            row.resize_with(cols, Default::default);
            for cell in row.iter_mut() {
                if let Some((rs, cs)) = cell.merged {
                    // Rows of the merge that follow in this part.
                    let n = rs.max(1).min(run.get(i).copied().unwrap_or(1));
                    cell.merged = (n > 1 || cs > 1).then_some((n, cs));
                }
            }
        }
    }
    Table {
        insert: origin.to3(t.insert.z),
        col_widths: t.col_widths.clone(),
        row_heights: rows.iter().map(|r| t.row_heights.get(*r).copied().unwrap_or(0.0)).collect(),
        row_styles: rows.iter().map(|r| t.row_style(*r).to_string()).collect(),
        cells,
        style: t.style.clone(),
        text_height: t.text_height,
        title: false,
        header: false,
        breaks: None,
        data_link: None,
    }
}

/// The table's outline alone, for a table too large to lay out.
fn outline(t: &Table) -> TableGeom {
    let rows = t.row_heights.len().min(10_000);
    let cols = t.col_widths.len().min(10_000);
    let (w, h) = (edges(&t.col_widths, cols).last().copied().unwrap_or(0.0), edges(&t.row_heights, rows).last().copied().unwrap_or(0.0));
    let mut g = TableGeom::default();
    outline_box(&mut g, t.insert.xy(), w, h);
    g
}

/// The four sides of a `w` by `h` box hanging down from `o`.
fn outline_box(g: &mut TableGeom, o: Vec2, w: f64, h: f64) {
    let p = |x: f64, y: f64| o + Vec2::new(x, -y);
    let corners = [p(0.0, 0.0), p(w, 0.0), p(w, h), p(0.0, h), p(0.0, 0.0)];
    for s in corners.windows(2) {
        if let [a, b] = s {
            g.lines.push(TableLine { a: *a, b: *b, color: Color::ByBlock, lineweight: Lineweight::ByBlock });
        }
    }
}

/// Lay out one part.
fn layout(d: &Drawing, t: &Table) -> TableGeom {
    let st = table_style_of(d, t);
    let rows = t.row_heights.len().min(10_000);
    let cols = t.col_widths.len().min(10_000);
    let xs = edges(&t.col_widths, cols);
    let ys = edges(&t.row_heights, rows);
    let o = t.insert.xy();
    let p = |x: f64, y: f64| o + Vec2::new(x, -y);
    let x_at = |c: usize| xs.get(c).copied().unwrap_or(0.0);
    let y_at = |r: usize| ys.get(r).copied().unwrap_or(0.0);
    let mut g = TableGeom::default();
    if rows == 0 || cols == 0 {
        return g;
    }
    let cov = coverage(t);
    if rows.saturating_mul(cols) > MAX_LAYOUT_CELLS || cov.is_err() {
        return outline(t);
    }
    let k = style_scale(&st, t);
    // Cell styles by name, scaled to the table.
    let mut styles: Vec<CellStyle> = Vec::new();
    let mut by_name: HashMap<String, usize> = HashMap::new();
    let mut style_index = |name: &str| -> usize {
        let key = name.to_ascii_lowercase();
        if let Some(i) = by_name.get(&key) {
            return *i;
        }
        let mut cs = st.cell_style(name);
        cs.text_height *= k;
        cs.margin_h *= k;
        cs.margin_v *= k;
        styles.push(cs);
        let i = styles.len() - 1;
        by_name.insert(key, i);
        i
    };
    // Anchors and the anchor owning each grid cell.
    let cov = cov.unwrap_or_default();
    let mut anchors: Vec<Anchor> = Vec::new();
    let mut owner = vec![usize::MAX; rows * cols];
    for r in 0..rows {
        for c in 0..cols {
            if cov.get(r).and_then(|v| v.get(c)).copied().unwrap_or(false) {
                continue;
            }
            let cell = t.cells.get(r).and_then(|row| row.get(c));
            let (rs, cs) = cell.and_then(|x| x.merged).map(|(a, b)| (a.max(1) as usize, b.max(1) as usize)).unwrap_or((1, 1));
            let (rs, cs) = (rs.min(rows - r), cs.min(cols - c));
            let style = style_index(t.cell_style_name(r, c));
            let id = anchors.len();
            for rr in r..r + rs {
                for cc in c..c + cs {
                    if let Some(x) = owner.get_mut(rr * cols + cc)
                        && *x == usize::MAX
                    {
                        *x = id;
                    }
                }
            }
            anchors.push(Anchor { row: r, col: c, rows: rs, cols: cs, style });
        }
    }
    let own = |r: usize, c: usize| owner.get(r * cols + c).copied().filter(|x| *x != usize::MAX);
    let style_of = |a: Option<usize>| a.and_then(|a| anchors.get(a)).and_then(|a| styles.get(a.style));
    let same_style = |a: Option<usize>, b: Option<usize>| matches!((a.and_then(|a| anchors.get(a)), b.and_then(|b| anchors.get(b))), (Some(x), Some(y)) if x.style == y.style);
    // Fills first, under the borders and texts.
    for a in &anchors {
        let Some(cs) = styles.get(a.style) else { continue };
        if let Some(fill) = cs.fill {
            let (x0, x1, y0, y1) = (x_at(a.col), x_at(a.col + a.cols), y_at(a.row), y_at(a.row + a.rows));
            g.fills.push(TableFill { corners: [p(x0, y1), p(x1, y1), p(x1, y0), p(x0, y0)], color: fill });
        }
    }
    // Borders: one segment per grid edge between different cells, joined while unchanged.
    let push = |g: &mut TableGeom, a: Vec2, b: Vec2, br: Option<CellBorder>| {
        let Some(br) = br.filter(|b| b.visible) else { return };
        if let Some(last) = g.lines.last_mut()
            && last.b == a
            && last.color == br.color
            && last.lineweight == br.lineweight
            && (last.b - last.a).cross(b - a).abs() <= 1e-12 * (1.0 + (last.b - last.a).len() * (b - a).len())
        {
            last.b = b;
            return;
        }
        g.lines.push(TableLine { a, b, color: br.color, lineweight: br.lineweight });
    };
    for i in 0..=rows {
        for c in 0..cols {
            let above = if i > 0 { own(i - 1, c) } else { None };
            let below = if i < rows { own(i, c) } else { None };
            if above.is_some() && above == below {
                continue;
            }
            let br = match (style_of(above), style_of(below)) {
                (None, Some(b)) => Some(b.borders.top),
                (Some(a), None) => Some(a.borders.bottom),
                (Some(a), Some(_)) if same_style(above, below) => Some(a.borders.inside_h),
                (Some(a), Some(b)) => Some(CellBorder { visible: a.borders.bottom.visible && b.borders.top.visible, ..b.borders.top }),
                (None, None) => None,
            };
            push(&mut g, p(x_at(c), y_at(i)), p(x_at(c + 1), y_at(i)), br);
        }
    }
    for j in 0..=cols {
        for r in 0..rows {
            let left = if j > 0 { own(r, j - 1) } else { None };
            let right = if j < cols { own(r, j) } else { None };
            if left.is_some() && left == right {
                continue;
            }
            let br = match (style_of(left), style_of(right)) {
                (None, Some(b)) => Some(b.borders.left),
                (Some(a), None) => Some(a.borders.right),
                (Some(a), Some(_)) if same_style(left, right) => Some(a.borders.inside_v),
                (Some(a), Some(b)) => Some(CellBorder { visible: a.borders.right.visible && b.borders.left.visible, ..b.borders.left }),
                (None, None) => None,
            };
            push(&mut g, p(x_at(j), y_at(r)), p(x_at(j), y_at(r + 1)), br);
        }
    }
    // Texts at their alignment point inside the margins.
    for a in &anchors {
        let Some(cell) = t.cells.get(a.row).and_then(|row| row.get(a.col)).filter(|c| !c.text.is_empty()) else { continue };
        let Some(cs) = styles.get(a.style) else { continue };
        let (x0, x1, y0, y1) = (x_at(a.col), x_at(a.col + a.cols), y_at(a.row), y_at(a.row + a.rows));
        let attach = cs.align.clamp(1, 9);
        let x = match (attach - 1) % 3 {
            0 => x0 + cs.margin_h,
            1 => (x0 + x1) / 2.0,
            _ => x1 - cs.margin_h,
        };
        let y = match (attach - 1) / 3 {
            0 => y0 + cs.margin_v,
            1 => (y0 + y1) / 2.0,
            _ => y1 - cs.margin_v,
        };
        g.texts.push(TableText {
            row: a.row,
            col: a.col,
            at: p(x, y),
            attach,
            height: cell.text_height.filter(|h| h.is_finite() && *h > 0.0).map_or(cs.text_height, |h| h * k),
            color: cs.text_color,
            style: cs.text_style.clone(),
            text: cell.text.clone(),
        });
    }
    g
}

/// A cell style colour as drawn: ByBlock / ByLayer take the table's colour.
fn style_ink(c: Color, table: Ink) -> Ink {
    match c {
        Color::ByBlock | Color::ByLayer => table,
        c => ink(c, Color::Index(7), Color::Index(7)),
    }
}

/// Draw a table into the display list.
pub(crate) fn draw(b: &mut Builder, ctx: &Ctx, t: &Table, rgb: Ink, lw: f32) {
    let g = table_geometry(ctx.d, t);
    if b.opts.fill {
        for f in &g.fills {
            let [a, bb, c, dd] = f.corners;
            b.tris(ctx, style_ink(f.color, rgb), &[a, bb, c, a, c, dd]);
        }
    }
    for l in &g.lines {
        let w = match l.lineweight {
            Lineweight::Mm100(v) => f32::from(v) / 100.0,
            Lineweight::Default => crate::default_lineweight(ctx.d),
            Lineweight::ByBlock | Lineweight::ByLayer => lw,
        };
        b.polyline(ctx, style_ink(l.color, rgb), w, &[l.a, l.b]);
    }
    if !b.opts.text {
        return;
    }
    for tx in &g.texts {
        let ts = crate::text_style(ctx.d, &tx.style);
        let font = crate::style_font(&ts);
        // Cell content is MTEXT (`\P`, `{\Q15;…}`, `\F…;`): laid out as such, at the cell's
        // alignment point (its numbering is MTEXT's attachment).
        let mp = cadcraft_fonts::MTextParams {
            attach: tx.attach,
            font,
            width_factor: ts.width_factor,
            oblique: ts.oblique,
            ..cadcraft_fonts::MTextParams::new(tx.at, tx.height)
        };
        let layout = cadcraft_fonts::layout_mtext_with(&tx.text, &mp);
        for piece in &layout.pieces {
            b.shaped(ctx, style_ink(tx.color, rgb), lw, &piece.shaped);
        }
    }
}

#[cfg(test)]
mod budget_tests {
    use super::*;
    use cadcraft_doc::TableCell;

    /// Excessive overlapping merges draw only the table outline after coverage work is exhausted.
    #[test]
    fn overlapping_merges_use_outline_fallback() {
        let t = Table {
            row_heights: vec![1.0; 40],
            col_widths: vec![1.0; 40],
            cells: vec![vec![TableCell { merged: Some((40, 40)), ..Default::default() }; 40]; 40],
            ..Default::default()
        };
        assert!(coverage(&t).is_err());
        let g = layout(&Drawing::default(), &t);
        assert_eq!(g.lines.len(), 4);
        assert!(g.fills.is_empty() && g.texts.is_empty());
    }

    /// A split table within the displayed-cell budget clips a merge to contiguous selected rows.
    #[test]
    fn part_clips_merges_using_displayed_column_count() {
        let t = Table {
            row_heights: vec![1.0; 102],
            col_widths: vec![1.0; 10_001],
            cells: vec![vec![TableCell { merged: Some((100, 1)), ..Default::default() }]],
            ..Default::default()
        };
        let mut rows: Vec<_> = (0..99).collect();
        rows.push(101);
        let part = part_table(&t, &rows, Vec2::ZERO);
        assert_eq!(part.cells[0][0].merged, Some((99, 1)));
    }
}