GitCorner

Code

ossartcraftgridcraft🌐
1687a9c05b0c
//! Reading worksheet parts.

use std::collections::HashMap;
use std::sync::Arc;

use gridcraft_core::date::{serial_from_ymd, time_fraction};
use gridcraft_core::{CellError, CellRef, DateSystem, MAX_COLS, MAX_ROWS, RangeRef, Value};
use gridcraft_formula::Expr;
use gridcraft_model::{
    AutoFilter, Cell, CfOperator, CfRule, CfValueKind, Comment, CondFormat, EditRange, ErrorStyle, FilterCriterion, Formula, Hyperlink, LineInfo,
    NoteBox, NoteCorner, Orientation, PageOrder, PasswordHash, Sheet, SheetProtection, Sparkline, SparklineKind, Style, Table, TableColumn, TotalsFn,
    Validation, ValidationKind, XmlColumnPr,
};

use crate::IoError;
use crate::fmla::{from_file, unwrap_google_sheets};
use crate::package::Rel;
use crate::read::Ctx;
use crate::styles::read_color;
use crate::tables::{col_width_to_px, paper_name, pt_to_px};
use crate::xml::{self, El};

mod parts;
mod rules;

pub use parts::{read_autofilter, read_table};
use parts::{read_comments, read_hyperlinks, read_note_shapes, read_threaded};
use rules::{read_cf, read_validation, read_x14_cf};

struct Shared {
    anchor: CellRef,
    expr: Option<Expr>,
    text: String,
    unwrapped: bool,
    /// Approximate bytes one dependent cell costs (its printed text plus its expression tree);
    /// what exceeds [`SHARED_FORMULA_FREE_COST`] is charged against [`MAX_SHARED_FORMULA_BYTES`].
    cost: u64,
}

/// What one sheet's hyperlinks have copied so far, across all its `<hyperlinks>` blocks.
#[derive(Default)]
struct LinkBudget {
    cells: u64,
    bytes: u64,
}

#[derive(Default)]
struct RowState {
    next_row: u32,
    shared: HashMap<u32, Shared>,
    /// Dynamic-array spill ranges and legacy array ranges: cached values inside them (other than
    /// the anchor) are not stored, so the formula can fill them again.
    dynamic: Vec<RangeRef>,
    /// Cells inside the ranges above, for a cap before a pathological sheet proves it itself.
    dynamic_cells: u64,
    /// Row-membership checks served so far, for the work cap above.
    dynamic_checks: u64,
    /// The cell being read lost its shared formula to a copy limit: its cached value is kept, even
    /// inside an array range (where a formula's cached values otherwise give way to the spill).
    shared_copy_refused: bool,
    dropped: u64,
    rows: u64,
}

/// The known dynamic range `pos` lies in, when it isn't the range's anchor: the cell's cached
/// value gives way to the formula that will fill it (or, for a Python cell, becomes its
/// result). Charges every scanned range against one work budget, then gives up consulting the
/// ranges at all: the worst kind of file may then import a few cached spill values, but it
/// never stalls the whole import.
fn dynamic_range(st: &mut RowState, pos: CellRef) -> Option<RangeRef> {
    if st.dynamic_checks > MAX_DYNAMIC_CHECKS || st.dynamic.is_empty() {
        return None;
    }
    let ranges = st.dynamic.len();
    let hit = st.dynamic.iter().find(|r| r.contains(pos) && r.start != pos).copied();
    st.dynamic_checks = st.dynamic_checks.saturating_add(ranges as u64);
    hit
}

/// Records a dynamic-array range, so its cells outside the anchor import as empty and the
/// formula fills them again. Repeated identical anchors (a damaged or hostile sheet may repeat
/// the same record) are recorded once, and count and area are capped: every later cell inside
/// known range territory pays a scan proportional to what is recorded here.
fn push_dynamic(st: &mut RowState, range: RangeRef) {
    if st.dynamic.contains(&range) {
        return;
    }
    let cells = range.count();
    if st.dynamic.len() >= MAX_DYNAMIC_RANGES || st.dynamic_cells.saturating_add(cells) > MAX_DYNAMIC_CELLS {
        return;
    }
    st.dynamic_cells = st.dynamic_cells.saturating_add(cells);
    st.dynamic.push(range);
}

/// Forgets the range anchored at `pos` (a Python cell whose code the file doesn't hold, which
/// keeps only its cached value): the cached values over the rest of its spill are kept as plain
/// values too, as the file shows them, rather than left for a result that won't come. Charged
/// like [`dynamic_range`]'s scans.
fn forget_dynamic(st: &mut RowState, pos: CellRef) {
    if st.dynamic_checks > MAX_DYNAMIC_CHECKS {
        return;
    }
    st.dynamic_checks = st.dynamic_checks.saturating_add(st.dynamic.len() as u64);
    if let Some(i) = st.dynamic.iter().rposition(|r| r.start == pos) {
        st.dynamic.remove(i);
    }
}

/// Records the spill range of the Python cell read at `pos`, its anchor, when the file declares
/// one that a result can fill: the spill then exists even when the file holds no records for its
/// blank cells. Charged like [`dynamic_range`]'s scans.
fn record_python_spill(st: &mut RowState, sheet: &mut Sheet, pos: CellRef) {
    if st.dynamic_checks > MAX_DYNAMIC_CHECKS {
        return;
    }
    st.dynamic_checks = st.dynamic_checks.saturating_add(st.dynamic.len() as u64);
    let Some(r) = st.dynamic.iter().rev().find(|r| r.start == pos).copied() else { return };
    if r.count() > 1 && r.count() <= gridcraft_model::python::MAX_RESULT_CELLS as u64 {
        sheet.spill_ranges.insert(pos, r);
    }
}

/// Past the scan budget, the cells of a Python spill read afterwards were kept as plain cells, not
/// as its spilled values, and a result rebuilt over them would block itself. Every Python spill of
/// such a sheet keeps its values as plain values instead, with no live spill.
fn settle_python_spills_past_budget(st: &RowState, sheet: &mut Sheet) {
    if st.dynamic_checks <= MAX_DYNAMIC_CHECKS {
        return;
    }
    let anchors: Vec<CellRef> = sheet.spill_ranges.keys().copied().filter(|a| sheet.cells.get(*a).is_some_and(|c| c.py.is_some())).collect();
    for anchor in anchors {
        sheet.settle_spill(anchor);
    }
}

/// The most cell elements read from one workbook, across its sheets: the reader's own cap.
/// (`calc::eval::MAX_CELLS` has the same value but limits one array result, not a workbook.)
pub(crate) const MAX_CELLS: u64 = 16_000_000;
/// Target and tooltip bytes kept for hyperlinks of one sheet, over all cells: the same URL is
/// copied for every cell of its range, so length × cells must stay bounded whatever the file.
const MAX_HYPERLINK_BYTES: u64 = 8 * 1024 * 1024;
/// Most cells one sheet's hyperlinks may cover (each cell gets its own copy of the link).
const MAX_HYPERLINK_CELLS: u64 = 10_000;
/// Longest hyperlink target kept, in bytes (Excel's own limit is about 2,079 characters).
const MAX_HYPERLINK_TARGET: usize = 8_192;
/// Longest hyperlink ScreenTip kept, in characters (Excel's limit).
const MAX_TOOLTIP_CHARS: usize = 255;
/// What a dependent of a shared formula may cost for free: an ordinary formula cell's worth (by
/// [`shared_cost`], a formula of about 40 operators and operands), so a sheet of many ordinary
/// shared formulas is never cut short however many cells share them.
const SHARED_FORMULA_FREE_COST: u64 = 4096;
/// Budget, per workbook, for what shared formulas cost beyond [`SHARED_FORMULA_FREE_COST`] per
/// dependent cell: a long master copied into many cells is where the expansion multiplies the
/// file's bytes, and this bounds it to well within a web build's memory.
pub const MAX_SHARED_FORMULA_BYTES: u64 = 256 << 20;
const MAX_COLUMN_ASSIGNMENTS: u64 = 1_000_000;
/// Most dynamic-array and legacy-array ranges of one sheet.
const MAX_DYNAMIC_RANGES: usize = 65_536;
/// Worst-case cells inside the dynamic ranges the sheet declares. Beyond it further ranges are
/// dropped: they would cost their storage in every membership lookup that follows.
const MAX_DYNAMIC_CELLS: u64 = 16_000_000;
/// Most row-membership checks the sheet's ranges may serve. Beyond it the remaining cells are
/// imported with their cached values instead of being blanked for a spill that may still come,
/// so adversarial range counts can't make each cell scan a long list (a real workbook has a
/// handful of ranges).
const MAX_DYNAMIC_CHECKS: u64 = 16_000_000;
/// Most conditional-format range cells one sheet keeps, over all rules of an element: every
/// rule copies its element's whole range list, so rules × ranges must stay bounded.
const MAX_COND_CELLS: u64 = 4_000_000;

fn read_sheet_format(e: &El, sheet: &mut Sheet) {
    if let Some(h) = e.attr_f64("defaultRowHeight") {
        let px = pt_to_px(h);
        if px > 0.0 {
            sheet.default_row_height = px;
        }
    }
    if let Some(w) = e.attr_f64("defaultColWidth") {
        let px = col_width_to_px(w);
        if px > 0.0 {
            sheet.default_col_width = px;
        }
    } else if let Some(b) = e.attr_f64("baseColWidth") {
        let px = ((b.clamp(0.0, 255.0) * 7.0 + 5.0) / 8.0).ceil() * 8.0;
        sheet.default_col_width = px as f32;
    }
}

/// Reads the sheet part `part`, with the VML shape numbers of the form controls read into the
/// model (pass-through keeps the other controls).
pub fn read_sheet(cx: &mut Ctx<'_>, part: &str, name: &str) -> Result<(Sheet, crate::controls::ReadControls), IoError> {
    let bytes = cx.pkg.read(part)?.ok_or_else(|| IoError::Format(format!("missing part {part}")))?;
    let rels = cx.pkg.rels(part)?;
    let mut sheet = Sheet::new(name);
    let mut st = RowState::default();
    let res = xml::parse_streaming(&bytes, &["row"], &mut |row| read_row(cx, &mut sheet, &mut st, &row));
    let root = match res {
        Ok(r) => r,
        Err(IoError::TooLarge(m)) => return Err(IoError::TooLarge(m)),
        Err(e) => {
            cx.warn(format!("sheet \"{name}\" is damaged ({e}); kept {} rows", st.rows));
            El::default()
        }
    };
    if st.dropped > 0 {
        cx.warn(format!("sheet \"{name}\": {} cells or rows outside the 1,048,576 × 16,384 grid were dropped", st.dropped));
    }
    settle_python_spills_past_budget(&st, &mut sheet);
    drop(bytes);

    // Relationships by id: hyperlinks, drawings and tables each look one up.
    let mut rel_by_id: HashMap<&str, &Rel> = HashMap::with_capacity(rels.len());
    for r in &rels {
        // The first of duplicate ids wins, as a linear search would find it.
        rel_by_id.entry(r.id.as_str()).or_insert(r);
    }
    let mut fit_to_page = false;
    let mut link_budget = LinkBudget::default();
    let mut cf_kept_cells = 0u64;
    let mut column_assignments_left = MAX_COLUMN_ASSIGNMENTS;
    cx.cf_ext_ids.clear();
    for e in &root.children {
        match e.name.as_str() {
            "sheetPr" => {
                if let Some(t) = e.child("tabColor") {
                    sheet.tab_color = Some(read_color(t, &cx.palette));
                }
                if let Some(o) = e.child("outlinePr") {
                    sheet.summary_below = o.flag("summaryBelow", true);
                    sheet.summary_right = o.flag("summaryRight", true);
                }
                fit_to_page = e.child("pageSetUpPr").is_some_and(|p| p.flag("fitToPage", false));
            }
            "sheetViews" => read_views(e, &mut sheet),
            "sheetFormatPr" => read_sheet_format(e, &mut sheet),
            "cols" => read_cols(cx, e, &mut sheet, &mut column_assignments_left)?,
            "mergeCells" => {
                for m in e.kids("mergeCell") {
                    if let Some(r) = m.attr("ref").and_then(RangeRef::parse)
                        && !r.is_single()
                    {
                        sheet.merges.push(r);
                    }
                }
            }
            "conditionalFormatting" => read_cf(cx, e, &mut sheet, &mut cf_kept_cells),
            "dataValidations" => {
                for v in e.kids("dataValidation") {
                    if let Some(v) = read_validation(v) {
                        sheet.validations.push(v);
                    }
                }
            }
            "hyperlinks" => read_hyperlinks(cx, name, e, &rel_by_id, &mut sheet, &mut link_budget),
            "autoFilter" => sheet.autofilter = read_autofilter(cx, e),
            "printOptions" => {
                sheet.print.gridlines = e.flag("gridLines", false);
                sheet.print.headings = e.flag("headings", false);
                sheet.print.center_h = e.flag("horizontalCentered", false);
                sheet.print.center_v = e.flag("verticalCentered", false);
            }
            "pageMargins" => {
                let m = &mut sheet.print.margins;
                for (i, k) in ["left", "right", "top", "bottom", "header", "footer"].iter().enumerate() {
                    if let (Some(v), Some(slot)) = (e.attr_f64(k), m.get_mut(i)) {
                        *slot = v.clamp(0.0, 50.0) as f32;
                    }
                }
            }
            "pageSetup" => {
                if e.attr("orientation") == Some("landscape") {
                    sheet.print.orientation = Orientation::Landscape;
                }
                // `downThenOver` when absent (ECMA-376's default); an unknown value reads as that too.
                sheet.print.page_order = e.attr("pageOrder").and_then(PageOrder::parse).unwrap_or_default();
                // The number counts only when `useFirstPageNumber` says so; otherwise it's Automatic.
                sheet.print.first_page_number = e.flag("useFirstPageNumber", false).then(|| e.attr_u32("firstPageNumber")).flatten();
                if let Some(p) = e.attr_u32("paperSize").and_then(paper_name) {
                    sheet.print.paper = p.to_string();
                }
                if let Some(s) = e.attr_u32("scale") {
                    sheet.print.scale = s.clamp(10, 400) as u16;
                }
                if fit_to_page || root.child("sheetPr").and_then(|p| p.child("pageSetUpPr")).is_some_and(|p| p.flag("fitToPage", false)) {
                    let w = e.attr_u32("fitToWidth").unwrap_or(1).min(32767) as u16;
                    let h = e.attr_u32("fitToHeight").unwrap_or(1).min(32767) as u16;
                    sheet.print.fit_to = Some((w, h));
                }
            }
            "headerFooter" => {
                let pr = &mut sheet.print;
                for (tag, slot) in [
                    ("oddHeader", &mut pr.header),
                    ("oddFooter", &mut pr.footer),
                    ("evenHeader", &mut pr.even_header),
                    ("evenFooter", &mut pr.even_footer),
                    ("firstHeader", &mut pr.first_header),
                    ("firstFooter", &mut pr.first_footer),
                ] {
                    // Excel caps each at 255 characters; a hostile file can't make them huge.
                    *slot = e.child(tag).map(|h| h.text.chars().take(255).collect()).unwrap_or_default();
                }
                pr.different_first = e.flag("differentFirst", false);
                pr.different_odd_even = e.flag("differentOddEven", false);
                pr.hf_scale_with_doc = e.flag("scaleWithDoc", true);
                pr.hf_align_with_margins = e.flag("alignWithMargins", true);
            }
            "rowBreaks" => sheet.print.row_breaks = e.kids("brk").filter_map(|b| b.attr_u32("id")).filter(|&r| r > 0 && r < MAX_ROWS).collect(),
            "colBreaks" => sheet.print.col_breaks = e.kids("brk").filter_map(|b| b.attr_u32("id")).filter(|&c| c > 0 && c < MAX_COLS).collect(),
            "sheetProtection" if e.flag("sheet", false) => {
                sheet.protection = Some(SheetProtection {
                    password: read_password(e, ""),
                    legacy_password_hash: None,
                    select_locked: !e.flag("selectLockedCells", false),
                    select_unlocked: !e.flag("selectUnlockedCells", false),
                    format_cells: !e.flag("formatCells", true),
                    format_columns: !e.flag("formatColumns", true),
                    format_rows: !e.flag("formatRows", true),
                    insert_columns: !e.flag("insertColumns", true),
                    insert_rows: !e.flag("insertRows", true),
                    delete_columns: !e.flag("deleteColumns", true),
                    delete_rows: !e.flag("deleteRows", true),
                    sort: !e.flag("sort", true),
                    autofilter: !e.flag("autoFilter", true),
                });
            }
            "drawing" => {
                if let Some(rel) = e.attr("id").and_then(|id| rel_by_id.get(id).copied()) {
                    let target = rel.target.clone();
                    crate::drawing::read_drawing(cx, &target, &mut sheet)?;
                }
            }
            "tableParts" => {
                for tp in e.kids("tablePart") {
                    if let Some(rel) = tp.attr("id").and_then(|id| rel_by_id.get(id).copied()) {
                        let target = rel.target.clone();
                        if let Some(x) = cx.optional_xml(&target)?
                            && let Some(mut t) = read_table(cx, &x)
                        {
                            t.id = cx.next_object_id();
                            sheet.tables.push(t);
                        }
                    }
                }
            }
            "extLst" => read_ext(cx, e, &mut sheet, &mut cf_kept_cells),
            "protectedRanges" => read_protected_ranges(e, &mut sheet),
            _ => {}
        }
    }
    let read_controls = read_form_controls(cx, &root, &rels, &mut sheet);
    // Comments are related to the sheet without an element in it.
    for rel in rels.iter().filter(|r| r.kind == "comments") {
        if let Some(x) = cx.optional_xml(&rel.target)? {
            read_comments(&x, &mut sheet);
        }
    }
    for rel in rels.iter().filter(|r| r.kind == "threadedComment") {
        if let Some(x) = cx.optional_xml(&rel.target)? {
            read_threaded(cx, &x, &mut sheet);
        }
    }
    // Which notes are displayed (`<x:Visible/>`) and where their boxes sit live in the VML shapes.
    // Best effort: the VML is only read for those, so a part that doesn't parse is skipped without
    // a warning.
    if !sheet.comments.is_empty() {
        for rel in rels.iter().filter(|r| r.kind == "vmlDrawing") {
            if let Ok(Some(x)) = cx.pkg.read_xml(&rel.target) {
                read_note_shapes(&x, &mut sheet, 0);
            }
        }
    }
    Ok((sheet, read_controls))
}

/// Buttons, scroll bars and spin buttons: the `<controls>` list (also inside
/// `mc:AlternateContent`) with its properties parts, else the shapes of the VML drawing that
/// `<legacyDrawing r:id>` names (not the header and footer drawing of `<legacyDrawingHF>`).
/// Returns the VML shape numbers read, so pass-through keeps only the others.
fn read_form_controls(cx: &mut Ctx<'_>, root: &El, rels: &[Rel], sheet: &mut Sheet) -> crate::controls::ReadControls {
    let controls = root.children.iter().filter_map(crate::controls::controls_of).next_back();
    let vml = root.child("legacyDrawing").and_then(|e| e.attr("id"));
    if controls.is_some() || vml.is_some() { crate::controls::read(cx, controls, vml, rels, sheet) } else { Default::default() }
}

/// A protection password hash: the iterated attributes (`algorithmName`, `hashValue`,
/// `saltValue`, `spinCount`) or the legacy 16-bit `password`, each name preceded by `prefix`
/// (`workbook` gives `workbookHashValue`…). One that can't be read keeps a hash that never
/// matches, so what it protects stays locked rather than open.
pub(crate) fn read_password(e: &El, prefix: &str) -> Option<PasswordHash> {
    let attr = |base: &str| e.attr(&password_attr(prefix, base));
    if attr("algorithmName").is_some() || attr("hashValue").is_some() {
        return Some(PasswordHash::Iterated {
            algorithm: attr("algorithmName").unwrap_or("").to_string(),
            hash: attr("hashValue").unwrap_or("").to_string(),
            salt: attr("saltValue").unwrap_or("").to_string(),
            spin_count: e.attr_u32(&password_attr(prefix, "spinCount")).unwrap_or(0),
        });
    }
    attr("password").map(|h| match u16::from_str_radix(h.trim(), 16) {
        Ok(h) => PasswordHash::Legacy(h),
        Err(_) => PasswordHash::Iterated { algorithm: String::new(), hash: String::new(), salt: String::new(), spin_count: 0 },
    })
}

/// `base` preceded by `prefix` in camel case: ("workbook", "hashValue") → `workbookHashValue`.
pub(crate) fn password_attr(prefix: &str, base: &str) -> String {
    let mut chars = base.chars();
    match chars.next() {
        Some(c) if !prefix.is_empty() => format!("{prefix}{}{}", c.to_ascii_uppercase(), chars.as_str()),
        _ => base.to_string(),
    }
}

/// Allow Edit Ranges. A range whose password can't be read keeps a hash that never matches
/// (or an unsupported algorithm), so it stays locked rather than open.
fn read_protected_ranges(e: &El, sheet: &mut Sheet) {
    for p in e.kids("protectedRange") {
        let ranges: Vec<RangeRef> = p.attr("sqref").unwrap_or("").split_whitespace().filter_map(RangeRef::parse).collect();
        if ranges.is_empty() {
            continue;
        }
        let password = read_password(p, "");
        let title = p.attr("name").unwrap_or("").to_string();
        sheet.edit_ranges.push(EditRange { title, ranges, password, security_descriptor: p.attr("securityDescriptor").map(str::to_string) });
    }
}

fn read_views(e: &El, sheet: &mut Sheet) {
    let Some(v) = e.child("sheetView") else { return };
    sheet.show_gridlines = v.flag("showGridLines", true);
    sheet.show_headings = v.flag("showRowColHeaders", true);
    sheet.show_formulas = v.flag("showFormulas", false);
    sheet.show_zeros = v.flag("showZeros", true);
    sheet.show_outline_symbols = v.flag("showOutlineSymbols", true);
    sheet.right_to_left = v.flag("rightToLeft", false);
    sheet.view = v.attr("view").and_then(gridcraft_model::SheetViewMode::parse).unwrap_or_default();
    if let Some(z) = v.attr_u32("zoomScale") {
        sheet.zoom = z.clamp(10, 400) as u16;
    }
    if let Some(c) = v.attr("topLeftCell").and_then(CellRef::parse) {
        sheet.view_top_left = c;
    }
    let mut active_pane = None;
    if let Some(p) = v.child("pane") {
        if matches!(p.attr("state"), Some("frozen") | Some("frozenSplit")) {
            let cols = p.attr_f64("xSplit").unwrap_or(0.0).clamp(0.0, (MAX_COLS - 1) as f64) as u32;
            let rows = p.attr_f64("ySplit").unwrap_or(0.0).clamp(0.0, (MAX_ROWS - 1) as f64) as u32;
            if rows > 0 || cols > 0 {
                sheet.freeze = Some((rows, cols));
                // With frozen panes the scroll position is the scrolling pane's first cell.
                if let Some(c) = p.attr("topLeftCell").and_then(CellRef::parse) {
                    sheet.view_top_left = c;
                }
            }
        }
        active_pane = p.attr("activePane");
    }
    let sel = v.kids("selection").find(|s| s.attr("pane") == active_pane).or_else(|| v.kids("selection").last());
    if let Some(c) = sel.and_then(|s| s.attr("activeCell")).and_then(CellRef::parse) {
        sheet.view_active = c;
    }
}

fn read_cols(cx: &Ctx<'_>, e: &El, sheet: &mut Sheet, remaining: &mut u64) -> Result<(), IoError> {
    for c in e.kids("col") {
        let (Some(min), Some(max)) = (c.attr_u32("min"), c.attr_u32("max")) else { continue };
        if min == 0 || min > MAX_COLS || max < min {
            continue;
        }
        let max = max.min(MAX_COLS);
        let mut info = LineInfo::default();
        // A width without `customWidth` that equals the default is just the default.
        if let Some(w) = c.attr_f64("width") {
            let px = col_width_to_px(w);
            if c.flag("customWidth", false) || px != sheet.default_col_width {
                info.size = Some(px);
            }
        }
        info.hidden = c.flag("hidden", false);
        info.outline = c.attr_u32("outlineLevel").unwrap_or(0).min(7) as u8;
        info.collapsed = c.flag("collapsed", false);
        if let Some(s) = c.attr_u32("style") {
            let id = cx.style(Some(s));
            if id != gridcraft_model::StyleId::DEFAULT {
                info.style = Some(id);
            }
        }
        // A custom width equal to the default still pins the column (Standard Width leaves it alone).
        if info == LineInfo::default() {
            continue;
        }
        // Overlapping declarations repeat work even when the final map stays small.
        // Charge the clipped span before expansion, sharing the budget across <cols> blocks.
        *remaining = remaining
            .checked_sub(u64::from(max - min + 1))
            .ok_or_else(|| IoError::TooLarge(format!("sheet \"{}\": more than {MAX_COLUMN_ASSIGNMENTS} expanded column assignments", sheet.name)))?;
        for col in (min - 1)..max {
            sheet.cols.insert(col, info);
        }
    }
    Ok(())
}

/// Charges `n` cell elements against the workbook's [`MAX_CELLS`].
fn charge_cells(cx: &mut Ctx<'_>, n: u64) -> Result<(), IoError> {
    cx.cells = cx.cells.saturating_add(n);
    if cx.cells > MAX_CELLS {
        return Err(IoError::TooLarge(format!("the workbook has more than {MAX_CELLS} cells")));
    }
    Ok(())
}

/// One `<row>`. Every `<c>` in it counts against [`MAX_CELLS`], also in a row that is dropped
/// for a bad row number: one worksheet part read for many sheets can't parse cells uncounted.
fn read_row(cx: &mut Ctx<'_>, sheet: &mut Sheet, st: &mut RowState, row: &El) -> Result<(), IoError> {
    st.rows += 1;
    let r = match row.attr_u32("r") {
        Some(r) if r >= 1 => r - 1,
        Some(_) => {
            st.dropped += 1;
            return charge_cells(cx, row.kids("c").count() as u64);
        }
        None => st.next_row,
    };
    if r >= MAX_ROWS {
        st.dropped += 1;
        return charge_cells(cx, row.kids("c").count() as u64);
    }
    st.next_row = r + 1;
    let mut info = LineInfo::default();
    if let Some(ht) = row.attr_f64("ht") {
        info.custom = row.flag("customHeight", false);
        // Automatic heights equal to the default are noise.
        if info.custom || (pt_to_px(ht) - sheet.default_row_height).abs() > 0.5 {
            info.size = Some(pt_to_px(ht));
        }
    }
    info.hidden = row.flag("hidden", false);
    info.outline = row.attr_u32("outlineLevel").unwrap_or(0).min(7) as u8;
    info.collapsed = row.flag("collapsed", false);
    if row.flag("customFormat", false)
        && let Some(s) = row.attr_u32("s")
    {
        info.style = Some(cx.style(Some(s)));
    }
    if info != LineInfo::default() {
        sheet.rows.insert(r, info);
    }
    let mut next_col = 0u32;
    for c in row.kids("c") {
        charge_cells(cx, 1)?;
        let pos = match c.attr("r") {
            Some(a) => match CellRef::parse(a.trim()) {
                Some(p) => p,
                None => {
                    st.dropped += 1;
                    continue;
                }
            },
            None => CellRef::new(r, next_col),
        };
        if pos.col >= MAX_COLS || pos.row >= MAX_ROWS {
            st.dropped += 1;
            continue;
        }
        next_col = pos.col + 1;
        read_cell(cx, sheet, st, c, pos);
    }
    Ok(())
}

fn read_cell(cx: &mut Ctx<'_>, sheet: &mut Sheet, st: &mut RowState, c: &El, pos: CellRef) {
    let style = cx.style(c.attr_u32("s"));
    let v = c.child("v").map(|v| v.text.as_str());
    let value = match c.attr("t").unwrap_or("n") {
        "s" => match v.and_then(|v| v.trim().parse::<usize>().ok()) {
            Some(i) => match cx.sst.get(i) {
                Some(s) => Value::Text(s.clone()),
                None => {
                    cx.warn("some cells refer to missing shared strings");
                    Value::Empty
                }
            },
            None => Value::Empty,
        },
        "str" => v.map(|v| Value::text(xml::decode_xstring(v))).unwrap_or(Value::Empty),
        "inlineStr" => {
            c.child("is").map(|is| Value::text(xml::rich_text(is))).or_else(|| v.map(|v| Value::text(xml::decode_xstring(v)))).unwrap_or(Value::Empty)
        }
        "b" => v.map(|v| Value::Bool(matches!(v.trim(), "1" | "true" | "TRUE"))).unwrap_or(Value::Empty),
        "e" => v.map(|v| Value::Error(CellError::parse(v.trim()).unwrap_or(CellError::Value))).unwrap_or(Value::Empty),
        "d" => match v.and_then(|v| parse_iso_datetime(v.trim(), cx.date_system)) {
            Some(n) => Value::number(n),
            None => {
                if let Some(v) = v
                    && !v.trim().is_empty()
                {
                    cx.warn("some date cells could not be read");
                }
                Value::Empty
            }
        },
        _ => match v.map(str::trim).filter(|v| !v.is_empty()) {
            Some(t) => match t.parse::<f64>() {
                Ok(n) if n.is_finite() => Value::Number(if n == 0.0 { 0.0 } else { n }),
                _ => {
                    cx.warn("some numeric cells could not be read");
                    Value::Empty
                }
            },
            None => Value::Empty,
        },
    };
    let picture = c.attr("vm").and_then(|vm| {
        if vm == "0" {
            return None;
        }
        let picture = vm.parse::<usize>().ok().and_then(|n| n.checked_sub(1)).and_then(|n| cx.cell_pictures.get(n)).cloned().flatten();
        if picture.is_none() {
            cx.warn("some cells have unsupported or missing value metadata; kept their scalar fallback (cell pictures may be missing)");
        }
        picture
    });
    if let Some(picture) = picture {
        if c.child("f").is_some() {
            cx.warn("formula-generated cell pictures were imported as static pictures; their formulas were not retained");
        }
        sheet.set_picture(pos, picture);
        sheet.set_style(pos, style);
        return;
    }
    let dynamic = c.attr("cm").is_some();
    st.shared_copy_refused = false;
    let formula = c.child("f").and_then(|f| read_formula(cx, st, f, pos, dynamic));
    // A `PY(index,0|1)` formula is a Python cell whose code is a script of the Python part. The
    // older `PY("…",0|1)` form is read from the formula's own text: the formula parser would fold
    // line breaks in the code. A formula naming a script the part lacks keeps only its cached
    // values, its own and its spill's, as plain values.
    let py = match (&formula, c.child("f")) {
        (Some(fm), Some(f)) => crate::python_part::cell_code(&mut cx.python, fm, &f.text),
        _ => crate::python_part::PyFormula::Not,
    };
    let (formula, py) = match py {
        crate::python_part::PyFormula::Not => (formula, None),
        crate::python_part::PyFormula::Code(py) => (None, Some(Arc::new(py))),
        crate::python_part::PyFormula::Missing => {
            forget_dynamic(st, pos);
            (None, None)
        }
    };
    if py.is_some() {
        record_python_spill(st, sheet, pos);
    }
    // A formula without dynamic-array metadata is a legacy formula, unless entered as a
    // Ctrl+Shift+Enter array or unwrapped from Google Sheets' export (#2871).
    if formula.as_ref().is_some_and(|f| !f.dynamic && f.array.is_none() && f.expr_arc().is_some()) {
        cx.legacy_formulas.push(pos);
    }
    let spilled_from = if formula.is_none() && py.is_none() && !st.shared_copy_refused { dynamic_range(st, pos) } else { None };
    let python_anchor = spilled_from.is_some_and(|r| sheet.cells.get(r.start).is_some_and(|a| a.py.is_some()));
    let value = match spilled_from {
        // A Python cell's spilled values are kept: they are its result until it runs again.
        Some(r) if python_anchor && r.count() <= gridcraft_model::python::MAX_RESULT_CELLS as u64 => {
            if !value.is_empty() {
                sheet.spill.insert(pos, value);
            }
            sheet.spill_ranges.insert(r.start, r);
            Value::Empty
        }
        // A Python cell's range larger than a result may be is a crafted file's: it is no spill,
        // and its cells keep the values the file shows as plain values, as when the cell keeps
        // only its own value.
        Some(_) if python_anchor => value,
        // A formula's spilled values are dropped: recalculation fills them again.
        Some(_) => Value::Empty,
        None => value,
    };
    // A dynamic array keeps the area it was saved spilling over (`ref`): when two arrays want the
    // same cells, recalculating gives them to this one again, as before saving.
    if dynamic
        && formula.as_ref().is_some_and(|f| f.array.is_none())
        && let Some(r) = st.dynamic.last().filter(|r| r.start == pos)
    {
        sheet.spill_ranges.insert(pos, *r);
    }
    sheet.cells.set(pos, Cell { value, formula: formula.map(Arc::new), style, py });
}

fn read_formula(cx: &mut Ctx<'_>, st: &mut RowState, f: &El, pos: CellRef, dynamic: bool) -> Option<Formula> {
    // Keep the file's dynamic-array mark (and treat Google Sheets unwrapped formulas as dynamic),
    // so saving never turns the formula into a legacy one.
    let mut unwrapped = false;
    let fm = read_formula_text(cx, st, f, pos, dynamic, &mut unwrapped)?;
    let dynamic = dynamic || unwrapped;
    Some(Formula { dynamic, ..fm })
}

fn read_formula_text(cx: &mut Ctx<'_>, st: &mut RowState, f: &El, pos: CellRef, dynamic: bool, unwrapped: &mut bool) -> Option<Formula> {
    let mut model = from_file(f.text.trim());
    if let Some(known) = cx.known_function
        && let Some(u) = unwrap_google_sheets(&model, known)
    {
        model = u;
        *unwrapped = true;
    }
    let text = model.as_str();
    match f.attr("t").unwrap_or("normal") {
        "shared" => {
            let si = f.attr_u32("si")?;
            if !text.is_empty() {
                let expr = gridcraft_formula::parse(text).ok();
                let cost = shared_cost(text, expr.as_ref());
                st.shared.insert(si, Shared { anchor: pos, expr, text: text.to_string(), unwrapped: *unwrapped, cost });
                Some(Formula::new(text))
            } else {
                let Some(sh) = st.shared.get(&si) else {
                    cx.warn("a shared formula refers to a missing master cell; kept the cached value");
                    return None;
                };
                // The parser's own test: bytes first (cheap), then characters, so a multibyte
                // master that failed to parse for another reason gets no false length warning.
                if sh.expr.is_none()
                    && sh.text.len() > gridcraft_formula::MAX_FORMULA_LEN
                    && sh.text.chars().count() > gridcraft_formula::MAX_FORMULA_LEN
                {
                    cx.warn(format!(
                        "a shared formula is longer than {} characters; kept the cached values of the cells that share it",
                        gridcraft_formula::MAX_FORMULA_LEN
                    ));
                    st.shared_copy_refused = true;
                    return None;
                }
                if !charge(&mut cx.shared_formula_bytes, extra_shared_cost(sh.cost), MAX_SHARED_FORMULA_BYTES) {
                    cx.warn("shared formulas expand to too much data; kept the cached values of the remaining cells that share them");
                    st.shared_copy_refused = true;
                    return None;
                }
                *unwrapped |= sh.unwrapped;
                Some(match &sh.expr {
                    Some(e) => {
                        let dr = pos.row as i64 - sh.anchor.row as i64;
                        let dc = pos.col as i64 - sh.anchor.col as i64;
                        Formula::from_expr(gridcraft_formula::adjust::shift_relative(e.clone(), dr, dc))
                    }
                    None => Formula::new(&sh.text),
                })
            }
        }
        "array" => {
            if text.is_empty() {
                return None;
            }
            let mut fm = Formula::new(text);
            let range = f.attr("ref").and_then(RangeRef::parse).unwrap_or(RangeRef::cell(pos));
            if !range.is_single() {
                push_dynamic(st, range);
            }
            if !dynamic {
                fm.array = Some(range);
            }
            Some(fm)
        }
        "dataTable" => {
            cx.warn("what-if data tables are not supported; kept their values");
            None
        }
        _ => {
            if text.is_empty() {
                None
            } else {
                Some(Formula::new(text))
            }
        }
    }
}

/// `2024-03-15`, `2024-03-15T10:30:00Z`, `10:30:00` → serial.
pub fn parse_iso_datetime(s: &str, sys: DateSystem) -> Option<f64> {
    let s = s.trim_end_matches('Z');
    let (date, time) = match s.split_once('T') {
        Some((d, t)) => (d, Some(t)),
        None if s.contains(':') => ("", Some(s)),
        None => (s, None),
    };
    let mut serial = 0.0;
    if !date.is_empty() {
        let mut it = date.split('-');
        let y: i64 = it.next()?.parse().ok()?;
        let m: i64 = it.next()?.parse().ok()?;
        let d: i64 = it.next()?.parse().ok()?;
        if !(1..=12).contains(&m) || !(1..=31).contains(&d) {
            return None;
        }
        serial = serial_from_ymd(sys, y, m, d)?;
    }
    if let Some(t) = time {
        // Drop a time-zone offset.
        let t = t.split(['+']).next().unwrap_or(t);
        let mut it = t.split(':');
        let h: f64 = it.next()?.parse().ok()?;
        let mi: f64 = it.next().unwrap_or("0").parse().ok()?;
        let se: f64 = it.next().unwrap_or("0").parse().ok()?;
        if !(0.0..24.0).contains(&h) || !(0.0..60.0).contains(&mi) || !(0.0..61.0).contains(&se) {
            return None;
        }
        serial += time_fraction(h, mi, se);
    }
    Some(serial)
}

/// What one dependent of a shared formula costs: its printed text plus its expression tree.
fn shared_cost(text: &str, expr: Option<&Expr>) -> u64 {
    let mut nodes = 0u64;
    if let Some(e) = expr {
        e.walk(&mut |_| nodes = nodes.saturating_add(1));
    }
    let node = std::mem::size_of::<Expr>() as u64;
    (text.len() as u64).saturating_mul(2).saturating_add(nodes.saturating_mul(node)).saturating_add(64)
}

/// What one dependent of a shared formula costing `cost` is charged: its cost beyond an ordinary
/// formula cell's.
fn extra_shared_cost(cost: u64) -> u64 {
    cost.saturating_sub(SHARED_FORMULA_FREE_COST)
}

/// Adds `cost` to `used` when that stays within `cap`; `false` (and `used` unchanged) otherwise.
fn charge(used: &mut u64, cost: u64, cap: u64) -> bool {
    match used.checked_add(cost) {
        Some(total) if total <= cap => {
            *used = total;
            true
        }
        _ => false,
    }
}

/// The first `max` characters of `s`.
fn truncate_chars(s: &str, max: usize) -> String {
    match s.char_indices().nth(max) {
        Some((at, _)) => s.get(..at).unwrap_or(s).to_string(),
        None => s.to_string(),
    }
}

pub fn parse_sqref(s: Option<&str>) -> Vec<RangeRef> {
    s.unwrap_or("").split_whitespace().filter_map(RangeRef::parse).collect()
}

/// Worksheet extensions: x14 data validations and sparklines.
fn read_ext(cx: &mut Ctx<'_>, e: &El, sheet: &mut Sheet, cf_kept_cells: &mut u64) {
    for ext in e.kids("ext") {
        for c in &ext.children {
            match c.name.as_str() {
                "dataValidations" => {
                    for v in c.kids("dataValidation") {
                        if let Some(v) = read_validation(v) {
                            sheet.validations.push(v);
                        }
                    }
                }
                "sparklineGroups" => {
                    for g in c.kids("sparklineGroup") {
                        let kind = match g.attr("type") {
                            Some("column") => SparklineKind::Column,
                            Some("stacked") => SparklineKind::WinLoss,
                            _ => SparklineKind::Line,
                        };
                        let color = g.child("colorSeries").map(|c| read_color(c, &cx.palette)).unwrap_or_default();
                        let markers = g.flag("markers", false);
                        for s in g.child("sparklines").map(|s| s.kids("sparkline").collect::<Vec<_>>()).unwrap_or_default() {
                            let source = s.child("f").map(|f| f.text.trim().to_string()).unwrap_or_default();
                            if let Some(cell) = s.child("sqref").and_then(|q| CellRef::parse(q.text.trim())) {
                                sheet.sparklines.push(Sparkline { cell, source, kind, color, markers });
                            }
                        }
                    }
                }
                "conditionalFormattings" => read_x14_cf(cx, c, sheet, cf_kept_cells),
                _ => {}
            }
        }
    }
}

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

    #[test]
    fn shared_formula_budget_stops_expansion() {
        let expr = gridcraft_formula::parse("SUM(1,2,3)").ok();
        let cost = shared_cost("SUM(1,2,3)", expr.as_ref());
        assert!(cost > 64 + 4 * std::mem::size_of::<Expr>() as u64);
        let cap = cost * 3;
        let mut used = 0;
        assert!((0..3).all(|_| charge(&mut used, cost, cap)));
        assert!(!charge(&mut used, cost, cap));
        assert_eq!(used, cap);
        assert!(!charge(&mut used, u64::MAX, u64::MAX));
    }

    #[test]
    fn ordinary_shared_formulas_are_free_and_long_ones_pay_their_excess() {
        let text = r#"IF(AND(A1>0,B1<>""),VLOOKUP(C1,Sheet2!$A$1:$D$500,4,FALSE)*SUM(D1:D10)/COUNT(D1:D10),IFERROR(E1/F1,0))"#;
        let expr = gridcraft_formula::parse(text).ok();
        assert!(expr.is_some());
        assert_eq!(extra_shared_cost(shared_cost(text, expr.as_ref())), 0, "an ordinary formula costs nothing extra");
        let long = vec![format!("SUM({}1)", "1,".repeat(199)); 10].join("+");
        let expr = gridcraft_formula::parse(&long).ok();
        assert!(expr.is_some());
        let cost = shared_cost(&long, expr.as_ref());
        assert_eq!(extra_shared_cost(cost), cost - SHARED_FORMULA_FREE_COST);
        // A few thousand copies of a long master no longer fit the budget.
        assert!(extra_shared_cost(cost).saturating_mul(10_000) > MAX_SHARED_FORMULA_BYTES);
    }

    #[test]
    fn truncate_keeps_whole_characters() {
        assert_eq!(truncate_chars("ab\u{e9}d", 3), "ab\u{e9}");
        assert_eq!(truncate_chars("ab", 3), "ab");
    }

    #[test]
    fn iso_dates() {
        assert_eq!(parse_iso_datetime("1900-01-01", DateSystem::D1900), Some(1.0));
        assert_eq!(parse_iso_datetime("2024-01-01T12:00:00Z", DateSystem::D1900), Some(45292.5));
        assert_eq!(parse_iso_datetime("1904-01-02", DateSystem::D1904), Some(1.0));
        assert_eq!(parse_iso_datetime("06:00:00", DateSystem::D1900), Some(0.25));
        assert_eq!(parse_iso_datetime("garbage", DateSystem::D1900), None);
        assert_eq!(parse_iso_datetime("2024-13-01", DateSystem::D1900), None);
    }

    fn ctx(pkg: crate::package::Package<'_>) -> Ctx<'_> {
        Ctx {
            pkg,
            report: Default::default(),
            sst: vec![],
            phonetics: vec![],
            xf_map: vec![],
            dxfs: vec![],
            palette: vec![],
            date_system: DateSystem::D1900,
            styles: Default::default(),
            persons: Default::default(),
            next_id: 1,
            num_fmts: Default::default(),
            cell_pictures: vec![],
            cf_ext_ids: vec![],
            known_function: None,
            python: Default::default(),
            cells: 0,
            shared_formula_bytes: 0,
            legacy_formulas: vec![],
        }
    }

    /// #2159: the workbook-wide cell cap refuses the open once passed, across sheets.
    #[test]
    fn cells_past_the_workbook_cap_are_refused() {
        let bytes = crate::tests::minimal(r#"<sheetData><row r="1"><c r="A1"><v>1</v></c><c r="B1"><v>2</v></c></row></sheetData>"#, &[], "", "");
        let pkg = crate::package::Package::open(&bytes).unwrap();
        let mut cx = ctx(pkg);
        cx.cells = MAX_CELLS - 2;
        let (sheet, _) = read_sheet(&mut cx, "xl/worksheets/sheet1.xml", "Data").unwrap();
        assert_eq!(sheet.cells.len(), 2);
        assert!(matches!(read_sheet(&mut cx, "xl/worksheets/sheet1.xml", "Data"), Err(IoError::TooLarge(_))));
    }

    /// #2159: the cells of a row dropped for its row number still count against the cap, so a
    /// part read for many sheets can't parse cells uncounted.
    #[test]
    fn cells_of_dropped_rows_count_against_the_cap() {
        let rows = r#"<sheetData><row r="0"><c><v>1</v></c><c><v>2</v></c></row><row r="2000000"><c><v>3</v></c></row></sheetData>"#;
        let bytes = crate::tests::minimal(rows, &[], "", "");
        let pkg = crate::package::Package::open(&bytes).unwrap();
        let mut cx = ctx(pkg);
        let (sheet, _) = read_sheet(&mut cx, "xl/worksheets/sheet1.xml", "Data").unwrap();
        assert!(sheet.cells.is_empty(), "both rows are dropped");
        assert_eq!(cx.cells, 3);
        cx.cells = MAX_CELLS - 2;
        assert!(matches!(read_sheet(&mut cx, "xl/worksheets/sheet1.xml", "Data"), Err(IoError::TooLarge(_))));
    }

    #[test]
    fn sqref_keeps_more_than_ten_thousand_ranges() {
        let sq = (1..=12_000).map(|r| format!("A{r}")).collect::<Vec<_>>().join(" ");
        let ranges = parse_sqref(Some(&sq));
        assert_eq!(ranges.len(), 12_000);
        assert_eq!(ranges.last().copied(), RangeRef::parse("A12000"));
    }
}