Skip to main content

sheetkit_core/
raw_transfer.rs

1//! Read-direction buffer serializer for bulk data transfer.
2//!
3//! Converts a `WorksheetXml` and `SharedStringTable` into a compact binary
4//! buffer that can be transferred to JavaScript as a single `Buffer` object,
5//! avoiding per-cell napi object creation overhead.
6//!
7//! Binary format (little-endian throughout):
8//!
9//! ```text
10//! HEADER (16 bytes)
11//!   magic:     u32  = 0x534B5244 ("SKRD")
12//!   version:   u16  = 1
13//!   row_count: u32  = occupied rows (sparse) or rectangle rows (dense)
14//!   col_count: u16  = number of columns
15//!   flags:     u32  = bit 0: 1=sparse, 0=dense
16//!
17//! ROW INDEX (row_count * 8 bytes; sparse omits unoccupied rows)
18//!   per row: row_number (u32) + offset (u32) into CELL DATA
19//!   offset = 0xFFFFFFFF for empty rows
20//!
21//! STRING TABLE
22//!   count:     u32
23//!   blob_size: u32
24//!   offsets:   u32[count] (byte offset within blob)
25//!   blob:      concatenated UTF-8 strings (blob_size bytes)
26//!
27//! CELL DATA
28//!   Dense:  row_count * col_count * 9 bytes
29//!     per cell: type (u8) + payload (8 bytes)
30//!   Sparse: variable length
31//!     per row: cell_count (u16) + cell_count * 11 bytes
32//!       per cell: col (u16) + type (u8) + payload (8 bytes)
33//! ```
34
35use std::borrow::Cow;
36use std::collections::HashMap;
37
38use crate::cell::CellValue;
39use crate::cell_ref_shift::{
40    shift_cell_references_with_abs_preallocated, shifted_cell_references_len_with_abs,
41};
42use crate::error::{Error, Result};
43use crate::resource::ResourceDimension;
44use crate::sst::SharedStringTable;
45use crate::traversal::{
46    check_limit, checked_output_add, checked_output_mul, CheckedRect, TraversalLimits,
47    TraversalMode, TraversalOptions,
48};
49use crate::utils::cell_ref::cell_name_to_coordinates;
50use crate::utils::constants::{MAX_COLUMNS, MAX_ROWS};
51use sheetkit_xml::worksheet::{CellTypeTag, WorksheetXml};
52
53pub const MAGIC: u32 = 0x534B5244;
54pub const VERSION: u16 = 1;
55pub const HEADER_SIZE: usize = 16;
56pub const CELL_STRIDE: usize = 9;
57
58pub const TYPE_EMPTY: u8 = 0x00;
59pub const TYPE_NUMBER: u8 = 0x01;
60pub const TYPE_STRING: u8 = 0x02;
61pub const TYPE_BOOL: u8 = 0x03;
62pub const TYPE_DATE: u8 = 0x04;
63pub const TYPE_ERROR: u8 = 0x05;
64pub const TYPE_FORMULA: u8 = 0x06;
65pub const TYPE_RICH_STRING: u8 = 0x07;
66
67pub const FLAG_SPARSE: u32 = 0x01;
68
69#[cfg(test)]
70const EMPTY_ROW_OFFSET: u32 = 0xFFFF_FFFF;
71const SPARSE_CELL_STRIDE: usize = 11;
72
73/// Serialize a worksheet's cell data into a compact binary buffer.
74///
75/// Reads cell data directly from `WorksheetXml` sheet data, resolving shared
76/// string references via `sst`. The default layout is sparse.
77pub fn sheet_to_raw_buffer(ws: &WorksheetXml, sst: &SharedStringTable) -> Result<Vec<u8>> {
78    sheet_to_raw_buffer_with_options(ws, sst, TraversalOptions::default())
79}
80
81/// Serializes a worksheet using an explicit finite traversal policy.
82pub fn sheet_to_raw_buffer_with_options(
83    ws: &WorksheetXml,
84    sst: &SharedStringTable,
85    options: TraversalOptions,
86) -> Result<Vec<u8>> {
87    sheet_to_raw_buffer_with_date_styles_and_options(ws, sst, &[], options)
88}
89
90/// Serialize a worksheet while promoting numeric cells that use date styles.
91pub fn sheet_to_raw_buffer_with_date_styles(
92    ws: &WorksheetXml,
93    sst: &SharedStringTable,
94    style_is_date: &[bool],
95) -> Result<Vec<u8>> {
96    sheet_to_raw_buffer_with_date_styles_and_options(
97        ws,
98        sst,
99        style_is_date,
100        TraversalOptions::default(),
101    )
102}
103
104/// Serializes a worksheet with date styles and an explicit traversal policy.
105pub fn sheet_to_raw_buffer_with_date_styles_and_options(
106    ws: &WorksheetXml,
107    sst: &SharedStringTable,
108    style_is_date: &[bool],
109    options: TraversalOptions,
110) -> Result<Vec<u8>> {
111    let rows = &ws.sheet_data.rows;
112    let limits = options.limits();
113
114    if rows.is_empty() {
115        return write_empty_buffer(limits);
116    }
117
118    let (min_row, max_row, min_col, max_col, total_cells) = scan_dimensions(ws, limits)?;
119
120    if total_cells == 0 {
121        return write_empty_buffer(limits);
122    }
123
124    let sparse = options.mode() == TraversalMode::Sparse;
125    let rect = if sparse {
126        CheckedRect::new_sparse(min_row, max_row, min_col, max_col, limits)?
127    } else {
128        CheckedRect::new(min_row, max_row, min_col, max_col, limits)?
129    };
130    let occupied_rows = rows.iter().filter(|row| !row.cells.is_empty()).count() as u64;
131    check_limit(
132        ResourceDimension::RowCount,
133        limits.max_rows(),
134        occupied_rows,
135    )?;
136    check_limit(
137        ResourceDimension::CellCount,
138        limits.max_cells(),
139        total_cells,
140    )?;
141    let row_count = if sparse {
142        occupied_rows
143    } else {
144        rect.row_count()
145    };
146    let col_count = rect.column_count();
147
148    let mut string_table = StringTableBuilder::new();
149
150    let mut cell_entries = collect_cell_entries(
151        ws,
152        sst,
153        min_col,
154        &mut string_table,
155        style_is_date,
156        limits,
157        occupied_rows,
158    )?;
159    cell_entries.sort_unstable_by_key(|row| row.row_num);
160
161    let flags: u32 = (if sparse { FLAG_SPARSE } else { 0 }) | ((min_col & 0xFFFF) << 16);
162
163    let row_index_size = checked_output_mul(row_count, 8, limits)?;
164    let string_section_size = string_table.encoded_size(limits)?;
165    let cell_data_size = if sparse {
166        sparse_cell_data_size(&cell_entries, limits)?
167    } else {
168        checked_output_mul(rect.cell_count(), CELL_STRIDE as u64, limits)?
169    };
170    let mut total_size = checked_output_add(HEADER_SIZE as u64, row_index_size, limits)?;
171    total_size = checked_output_add(total_size, string_section_size, limits)?;
172    total_size = checked_output_add(total_size, cell_data_size, limits)?;
173    let total_size = usize::try_from(total_size)
174        .map_err(|_| Error::Internal("raw transfer output size is not addressable".to_string()))?;
175
176    let string_section = string_table.encode(limits)?;
177    let cell_data = if sparse {
178        encode_sparse_cells(&cell_entries, cell_data_size, limits)?
179    } else {
180        encode_dense_cells(
181            &cell_entries,
182            min_row,
183            rect.row_count(),
184            col_count,
185            cell_data_size,
186        )?
187    };
188    let row_index = build_row_index(
189        &cell_entries,
190        min_row,
191        rect.row_count(),
192        col_count,
193        sparse,
194        row_index_size,
195    )?;
196
197    let mut buf = Vec::new();
198    buf.try_reserve_exact(total_size)
199        .map_err(|_| Error::Internal("raw transfer output allocation failed".to_string()))?;
200
201    buf.extend_from_slice(&MAGIC.to_le_bytes());
202    buf.extend_from_slice(&VERSION.to_le_bytes());
203    buf.extend_from_slice(&(row_count as u32).to_le_bytes());
204    buf.extend_from_slice(&(col_count as u16).to_le_bytes());
205    buf.extend_from_slice(&flags.to_le_bytes());
206
207    buf.extend_from_slice(&row_index);
208    buf.extend_from_slice(&string_section);
209    buf.extend_from_slice(&cell_data);
210
211    Ok(buf)
212}
213
214fn write_empty_buffer(limits: TraversalLimits) -> Result<Vec<u8>> {
215    checked_output_add(0, HEADER_SIZE as u64, limits)?;
216    let mut buf = Vec::new();
217    buf.try_reserve_exact(HEADER_SIZE)
218        .map_err(|_| Error::Internal("raw transfer output allocation failed".to_string()))?;
219    buf.extend_from_slice(&MAGIC.to_le_bytes());
220    buf.extend_from_slice(&VERSION.to_le_bytes());
221    buf.extend_from_slice(&0u32.to_le_bytes());
222    buf.extend_from_slice(&0u16.to_le_bytes());
223    buf.extend_from_slice(&0u32.to_le_bytes());
224    Ok(buf)
225}
226
227/// A formula cell as the row transfer buffers encode it.
228#[derive(Debug, Clone, PartialEq)]
229pub struct FormulaCell {
230    /// 1-based row number.
231    pub row: u32,
232    /// 1-based column number.
233    pub col: u32,
234    /// [`CellValue::Formula`] with the encoded expression and cached result.
235    pub value: CellValue,
236}
237
238/// Lists the formula cells of a worksheet together with their cached results.
239///
240/// Applies the traversal checks of the row transfer encoders and returns one
241/// entry for every cell those encoders write as a formula record, with the
242/// same expression (shared-formula followers are resolved). Cached results
243/// follow [`crate::row::resolve_cell_value`] with `style_is_date`.
244/// `consumed_output_bytes` is the size of a buffer already produced for the
245/// same traversal; it counts against `max_output_bytes` before this list.
246pub fn sheet_formula_cells(
247    ws: &WorksheetXml,
248    sst: &SharedStringTable,
249    style_is_date: &[bool],
250    options: TraversalOptions,
251    consumed_output_bytes: u64,
252) -> Result<Vec<FormulaCell>> {
253    let limits = options.limits();
254    let (min_row, max_row, min_col, max_col, total_cells) = scan_dimensions(ws, limits)?;
255    if total_cells == 0 {
256        return Ok(Vec::new());
257    }
258    if options.mode() == TraversalMode::Sparse {
259        CheckedRect::new_sparse(min_row, max_row, min_col, max_col, limits)?;
260    } else {
261        CheckedRect::new(min_row, max_row, min_col, max_col, limits)?;
262    }
263    let rows = &ws.sheet_data.rows;
264    let occupied_rows = rows.iter().filter(|row| !row.cells.is_empty()).count() as u64;
265    check_limit(
266        ResourceDimension::RowCount,
267        limits.max_rows(),
268        occupied_rows,
269    )?;
270
271    let mut budget = RawValueBudget::new(limits);
272    budget.charge_u64(consumed_output_bytes)?;
273    let shared_formulas = SharedFormulaResolver::new(ws, &mut budget)?;
274    let mut cells = Vec::new();
275    for row in rows {
276        check_limit(
277            ResourceDimension::ColumnCount,
278            limits.max_columns(),
279            row.cells.len() as u64,
280        )?;
281        for cell in row.cells.iter().filter(|cell| cell.f.is_some()) {
282            let Some(expr) = shared_formulas.formula_for(cell, &mut budget)? else {
283                continue;
284            };
285            budget.charge_u64(crate::row::cell_cloned_payload_bytes(cell, sst))?;
286            let mut value = crate::row::resolve_cell_value(cell, sst, style_is_date);
287            if let (CellValue::Formula { expr: target, .. }, Cow::Owned(resolved)) =
288                (&mut value, expr)
289            {
290                *target = resolved;
291            }
292            cells
293                .try_reserve(1)
294                .map_err(|_| Error::Internal("formula cell allocation failed".to_string()))?;
295            cells.push(FormulaCell {
296                row: row.r,
297                col: resolve_col(cell)?,
298                value,
299            });
300        }
301    }
302    Ok(cells)
303}
304
305struct CellEntry {
306    col: u32,
307    type_tag: u8,
308    payload: [u8; 8],
309}
310
311struct RowEntries {
312    row_num: u32,
313    cells: Vec<CellEntry>,
314}
315
316#[derive(Debug)]
317struct SharedFormulaMaster {
318    formula: String,
319    col: u32,
320    row: u32,
321}
322
323/// Resolves shared-formula followers to their shifted master expression.
324///
325/// A follower with no usable master is encoded through its cached cell value.
326/// If it has no cached value, the encoders emit `TYPE_EMPTY` rather than an
327/// empty formula record.
328#[derive(Debug)]
329pub(crate) struct SharedFormulaResolver {
330    masters: HashMap<u32, SharedFormulaMaster>,
331}
332
333pub(crate) struct RawValueBudget {
334    limits: TraversalLimits,
335    allocated_bytes: u64,
336}
337
338impl RawValueBudget {
339    pub(crate) const fn new(limits: TraversalLimits) -> Self {
340        Self {
341            limits,
342            allocated_bytes: 0,
343        }
344    }
345
346    fn charge(&mut self, bytes: usize) -> Result<()> {
347        self.charge_u64(bytes as u64)
348    }
349
350    pub(crate) fn charge_u64(&mut self, bytes: u64) -> Result<()> {
351        self.allocated_bytes = checked_output_add(self.allocated_bytes, bytes, self.limits)?;
352        Ok(())
353    }
354}
355
356pub(crate) fn inline_string_visible_text<'a>(
357    inline: &'a sheetkit_xml::worksheet::InlineString,
358    budget: &mut RawValueBudget,
359) -> Result<Cow<'a, str>> {
360    if inline.r.is_empty() {
361        return Ok(Cow::Borrowed(inline.t.as_deref().unwrap_or("")));
362    }
363    budget.charge(inline.r.len())?;
364    let visible_len = inline.r.iter().try_fold(0usize, |total, run| {
365        total
366            .checked_add(run.t.value.len())
367            .ok_or_else(|| Error::Internal("inline rich text length overflow".to_string()))
368    })?;
369    budget.charge(visible_len)?;
370    let mut visible = String::new();
371    visible
372        .try_reserve_exact(visible_len)
373        .map_err(|_| Error::Internal("inline rich text allocation failed".to_string()))?;
374    for run in &inline.r {
375        visible.push_str(&run.t.value);
376    }
377    Ok(Cow::Owned(visible))
378}
379
380impl SharedFormulaResolver {
381    pub(crate) fn new(ws: &WorksheetXml, budget: &mut RawValueBudget) -> Result<Self> {
382        Self::with_index(ws, None, budget)
383    }
384
385    /// Collects shared-formula masters, limited to index `only` when set.
386    pub(crate) fn with_index(
387        ws: &WorksheetXml,
388        only: Option<u32>,
389        budget: &mut RawValueBudget,
390    ) -> Result<Self> {
391        let mut masters = HashMap::new();
392        for row in &ws.sheet_data.rows {
393            for cell in &row.cells {
394                let Some(formula) = cell.f.as_deref() else {
395                    continue;
396                };
397                if formula.t.as_deref() != Some("shared") {
398                    continue;
399                }
400                let (Some(si), Some(value)) = (formula.si, formula.value.as_deref()) else {
401                    continue;
402                };
403                if value.is_empty() || only.is_some_and(|wanted| wanted != si) {
404                    continue;
405                }
406                if let std::collections::hash_map::Entry::Vacant(entry) = masters.entry(si) {
407                    let col = resolve_col(cell)?;
408                    budget.charge(value.len())?;
409                    let mut master_formula = String::new();
410                    master_formula.try_reserve_exact(value.len()).map_err(|_| {
411                        Error::Internal("shared formula allocation failed".to_string())
412                    })?;
413                    master_formula.push_str(value);
414                    entry.insert(SharedFormulaMaster {
415                        formula: master_formula,
416                        col,
417                        row: row.r,
418                    });
419                }
420            }
421        }
422        Ok(Self { masters })
423    }
424
425    pub(crate) fn formula_for<'a>(
426        &'a self,
427        cell: &'a sheetkit_xml::worksheet::Cell,
428        budget: &mut RawValueBudget,
429    ) -> Result<Option<Cow<'a, str>>> {
430        let Some(formula) = cell.f.as_deref() else {
431            return Ok(None);
432        };
433        if formula.t.as_deref() != Some("shared")
434            || formula.value.as_deref().is_some_and(|v| !v.is_empty())
435        {
436            return Ok(formula.value.as_deref().map(Cow::Borrowed));
437        }
438
439        let Some(master) = formula.si.and_then(|si| self.masters.get(&si)) else {
440            return Ok(None);
441        };
442        let col = resolve_col(cell)?;
443        let (_, row) = cell_name_to_coordinates(cell.r.as_str())?;
444        let col_delta = i64::from(col) - i64::from(master.col);
445        let row_delta = i64::from(row) - i64::from(master.row);
446        let shift = |ref_col: u32, ref_row: u32, abs_col: bool, abs_row: bool| {
447            let shifted_col = if abs_col {
448                ref_col
449            } else {
450                (i64::from(ref_col) + col_delta).clamp(1, i64::from(MAX_COLUMNS)) as u32
451            };
452            let shifted_row = if abs_row {
453                ref_row
454            } else {
455                (i64::from(ref_row) + row_delta).clamp(1, i64::from(MAX_ROWS)) as u32
456            };
457            (shifted_col, shifted_row)
458        };
459        budget.charge(master.formula.len())?;
460        let shifted_len = shifted_cell_references_len_with_abs(&master.formula, shift)?;
461        budget.charge(shifted_len)?;
462        let shifted =
463            shift_cell_references_with_abs_preallocated(&master.formula, shifted_len, shift)?;
464        debug_assert_eq!(shifted.len(), shifted_len);
465        Ok(Some(Cow::Owned(shifted)))
466    }
467}
468
469/// Gives shared-formula followers their master's shifted expression during
470/// one read. Masters are collected on the first follower, so reads without
471/// followers pay nothing.
472pub(crate) struct SharedFollowers<'a> {
473    ws: &'a WorksheetXml,
474    only: Option<u32>,
475    budget: RawValueBudget,
476    resolver: Option<SharedFormulaResolver>,
477}
478
479impl<'a> SharedFollowers<'a> {
480    /// `admitted_bytes` is output already charged against `limits` by the
481    /// read; `only` restricts master collection to one shared index.
482    pub(crate) fn new(
483        ws: &'a WorksheetXml,
484        limits: TraversalLimits,
485        admitted_bytes: u64,
486        only: Option<u32>,
487    ) -> Result<Self> {
488        let mut budget = RawValueBudget::new(limits);
489        budget.charge_u64(admitted_bytes)?;
490        Ok(Self {
491            ws,
492            only,
493            budget,
494            resolver: None,
495        })
496    }
497
498    /// Replaces the empty expression of a follower. Other values and orphan
499    /// followers are kept.
500    pub(crate) fn resolve(
501        &mut self,
502        value: &mut CellValue,
503        cell: &sheetkit_xml::worksheet::Cell,
504    ) -> Result<()> {
505        let CellValue::Formula { expr, .. } = value else {
506            return Ok(());
507        };
508        let is_shared = cell
509            .f
510            .as_deref()
511            .is_some_and(|f| f.t.as_deref() == Some("shared"));
512        if !expr.is_empty() || !is_shared {
513            return Ok(());
514        }
515        let resolver = match self.resolver.take() {
516            Some(resolver) => resolver,
517            None => SharedFormulaResolver::with_index(self.ws, self.only, &mut self.budget)?,
518        };
519        let resolved = resolver.formula_for(cell, &mut self.budget);
520        if let Some(resolved) = resolved? {
521            *expr = resolved.into_owned();
522        }
523        self.resolver = Some(resolver);
524        Ok(())
525    }
526}
527
528fn scan_dimensions(
529    ws: &WorksheetXml,
530    limits: TraversalLimits,
531) -> Result<(u32, u32, u32, u32, u64)> {
532    let mut min_row = u32::MAX;
533    let mut max_row = 0u32;
534    let mut min_col = u32::MAX;
535    let mut max_col = 0u32;
536    let mut total_cells = 0u64;
537
538    for row in &ws.sheet_data.rows {
539        if row.cells.is_empty() {
540            continue;
541        }
542        min_row = min_row.min(row.r);
543        max_row = max_row.max(row.r);
544        total_cells = total_cells
545            .checked_add(row.cells.len() as u64)
546            .ok_or_else(|| Error::Internal("raw transfer cell count overflow".to_string()))?;
547        check_limit(
548            ResourceDimension::CellCount,
549            limits.max_cells(),
550            total_cells,
551        )?;
552        for cell in &row.cells {
553            let col = resolve_col(cell)?;
554            min_col = min_col.min(col);
555            max_col = max_col.max(col);
556        }
557    }
558
559    if total_cells == 0 {
560        return Ok((1, 1, 1, 1, 0));
561    }
562
563    Ok((min_row, max_row, min_col, max_col, total_cells))
564}
565
566fn resolve_col(cell: &sheetkit_xml::worksheet::Cell) -> Result<u32> {
567    if cell.col > 0 {
568        return Ok(cell.col);
569    }
570    let (col, _row) = cell_name_to_coordinates(cell.r.as_str())?;
571    Ok(col)
572}
573
574fn collect_cell_entries(
575    ws: &WorksheetXml,
576    sst: &SharedStringTable,
577    min_col: u32,
578    string_table: &mut StringTableBuilder,
579    style_is_date: &[bool],
580    limits: TraversalLimits,
581    occupied_rows: u64,
582) -> Result<Vec<RowEntries>> {
583    let mut result = Vec::new();
584    let occupied_rows = usize::try_from(occupied_rows)
585        .map_err(|_| Error::Internal("raw transfer row count is not addressable".to_string()))?;
586    result
587        .try_reserve_exact(occupied_rows)
588        .map_err(|_| Error::Internal("raw transfer row allocation failed".to_string()))?;
589    let mut raw_value_budget = RawValueBudget::new(limits);
590    let shared_formulas = SharedFormulaResolver::new(ws, &mut raw_value_budget)?;
591
592    for row in &ws.sheet_data.rows {
593        if row.cells.is_empty() {
594            continue;
595        }
596
597        check_limit(
598            ResourceDimension::ColumnCount,
599            limits.max_columns(),
600            row.cells.len() as u64,
601        )?;
602        let mut cells = Vec::new();
603        cells
604            .try_reserve_exact(row.cells.len())
605            .map_err(|_| Error::Internal("raw transfer cell allocation failed".to_string()))?;
606        for cell in &row.cells {
607            let col = resolve_col(cell)?;
608            let relative_col = col - min_col;
609            let (type_tag, payload) = encode_cell_value(
610                cell,
611                sst,
612                string_table,
613                &shared_formulas,
614                style_is_date,
615                limits,
616                &mut raw_value_budget,
617            )?;
618            cells.push(CellEntry {
619                col: relative_col,
620                type_tag,
621                payload,
622            });
623        }
624
625        result.push(RowEntries {
626            row_num: row.r,
627            cells,
628        });
629    }
630
631    Ok(result)
632}
633
634fn encode_cell_value(
635    cell: &sheetkit_xml::worksheet::Cell,
636    sst: &SharedStringTable,
637    string_table: &mut StringTableBuilder,
638    shared_formulas: &SharedFormulaResolver,
639    style_is_date: &[bool],
640    limits: TraversalLimits,
641    raw_value_budget: &mut RawValueBudget,
642) -> Result<(u8, [u8; 8])> {
643    let mut payload = [0u8; 8];
644
645    if cell.f.is_some() {
646        if let Some(formula_expr) = shared_formulas.formula_for(cell, raw_value_budget)? {
647            let idx = string_table.intern(formula_expr.as_ref(), limits)?;
648            payload[..4].copy_from_slice(&(idx as u32).to_le_bytes());
649            return Ok((TYPE_FORMULA, payload));
650        }
651    }
652
653    match cell.t {
654        CellTypeTag::SharedString => {
655            if let Some(ref v) = cell.v {
656                if let Ok(sst_idx) = v.parse::<usize>() {
657                    let text = sst.get(sst_idx).unwrap_or("");
658                    let idx = string_table.intern(text, limits)?;
659                    payload[..4].copy_from_slice(&(idx as u32).to_le_bytes());
660                    if sst.get_rich_text(sst_idx).is_some() {
661                        return Ok((TYPE_RICH_STRING, payload));
662                    }
663                    return Ok((TYPE_STRING, payload));
664                }
665            }
666            Ok((TYPE_EMPTY, payload))
667        }
668        CellTypeTag::Boolean => {
669            if let Some(ref v) = cell.v {
670                payload[0] = if v == "1" || v.eq_ignore_ascii_case("true") {
671                    1
672                } else {
673                    0
674                };
675            }
676            Ok((TYPE_BOOL, payload))
677        }
678        CellTypeTag::Error => {
679            let error_text = cell.v.as_deref().unwrap_or("#VALUE!");
680            let idx = string_table.intern(error_text, limits)?;
681            payload[..4].copy_from_slice(&(idx as u32).to_le_bytes());
682            Ok((TYPE_ERROR, payload))
683        }
684        CellTypeTag::InlineString => {
685            let text = if let Some(inline) = cell.is.as_deref() {
686                inline_string_visible_text(inline, raw_value_budget)?
687            } else {
688                Cow::Borrowed(cell.v.as_deref().unwrap_or(""))
689            };
690            let idx = string_table.intern(text.as_ref(), limits)?;
691            payload[..4].copy_from_slice(&(idx as u32).to_le_bytes());
692            Ok((TYPE_STRING, payload))
693        }
694        CellTypeTag::Date => {
695            if let Some(ref v) = cell.v {
696                if let Ok(n) = v.parse::<f64>() {
697                    payload.copy_from_slice(&n.to_le_bytes());
698                    return Ok((TYPE_DATE, payload));
699                }
700            }
701            Ok((TYPE_EMPTY, payload))
702        }
703        CellTypeTag::FormulaString => {
704            if let Some(ref v) = cell.v {
705                let idx = string_table.intern(v, limits)?;
706                payload[..4].copy_from_slice(&(idx as u32).to_le_bytes());
707                return Ok((TYPE_STRING, payload));
708            }
709            Ok((TYPE_EMPTY, payload))
710        }
711        CellTypeTag::None | CellTypeTag::Number => {
712            if let Some(ref v) = cell.v {
713                if let Ok(n) = v.parse::<f64>() {
714                    payload.copy_from_slice(&n.to_le_bytes());
715                    let is_date = cell
716                        .s
717                        .and_then(|idx| style_is_date.get(idx as usize).copied())
718                        .unwrap_or(false);
719                    return Ok((if is_date { TYPE_DATE } else { TYPE_NUMBER }, payload));
720                }
721            }
722            Ok((TYPE_EMPTY, payload))
723        }
724    }
725}
726
727struct StringTableBuilder {
728    strings: Vec<String>,
729    index_map: HashMap<String, usize>,
730    blob_bytes: u64,
731}
732
733impl StringTableBuilder {
734    fn new() -> Self {
735        Self {
736            strings: Vec::new(),
737            index_map: HashMap::new(),
738            blob_bytes: 0,
739        }
740    }
741
742    fn intern(&mut self, s: &str, limits: TraversalLimits) -> Result<usize> {
743        if let Some(&idx) = self.index_map.get(s) {
744            return Ok(idx);
745        }
746        let new_count = self.strings.len() as u64 + 1;
747        check_limit(
748            ResourceDimension::CollectionCount,
749            limits.max_cells(),
750            new_count,
751        )?;
752        let new_blob_bytes = checked_output_add(self.blob_bytes, s.len() as u64, limits)?;
753        let offsets = checked_output_mul(new_count, 4, limits)?;
754        checked_output_add(
755            checked_output_add(8, offsets, limits)?,
756            new_blob_bytes,
757            limits,
758        )?;
759        let idx = self.strings.len();
760        self.strings
761            .try_reserve(1)
762            .map_err(|_| Error::Internal("raw transfer string allocation failed".to_string()))?;
763        self.index_map.try_reserve(1).map_err(|_| {
764            Error::Internal("raw transfer string index allocation failed".to_string())
765        })?;
766        let mut owned = String::new();
767        owned
768            .try_reserve_exact(s.len())
769            .map_err(|_| Error::Internal("raw transfer string allocation failed".to_string()))?;
770        owned.push_str(s);
771        self.strings.push(owned.clone());
772        self.index_map.insert(owned, idx);
773        self.blob_bytes = new_blob_bytes;
774        Ok(idx)
775    }
776
777    fn encoded_size(&self, limits: TraversalLimits) -> Result<u64> {
778        let count = self.strings.len() as u64;
779        check_limit(
780            ResourceDimension::CollectionCount,
781            limits.max_cells(),
782            count,
783        )?;
784        let offsets = checked_output_mul(count, 4, limits)?;
785        let header_and_offsets = checked_output_add(8, offsets, limits)?;
786        checked_output_add(header_and_offsets, self.blob_bytes, limits)
787    }
788
789    /// Encode the string table section: count(u32) + blob_size(u32) + offsets(u32[count]) + blob.
790    fn encode(&self, limits: TraversalLimits) -> Result<Vec<u8>> {
791        let total = usize::try_from(self.encoded_size(limits)?)
792            .map_err(|_| Error::Internal("raw transfer string table is too large".to_string()))?;
793        let count = self.strings.len() as u32;
794        if count == 0 {
795            let mut buf = Vec::new();
796            buf.try_reserve_exact(8).map_err(|_| {
797                Error::Internal("raw transfer string table allocation failed".to_string())
798            })?;
799            buf.extend_from_slice(&0u32.to_le_bytes());
800            buf.extend_from_slice(&0u32.to_le_bytes());
801            return Ok(buf);
802        }
803
804        let mut blob = Vec::new();
805        let blob_len = usize::try_from(self.blob_bytes)
806            .map_err(|_| Error::Internal("raw transfer string blob is too large".to_string()))?;
807        blob.try_reserve_exact(blob_len).map_err(|_| {
808            Error::Internal("raw transfer string blob allocation failed".to_string())
809        })?;
810        let mut offsets = Vec::new();
811        offsets.try_reserve_exact(self.strings.len()).map_err(|_| {
812            Error::Internal("raw transfer string offsets allocation failed".to_string())
813        })?;
814        for s in &self.strings {
815            offsets.push(blob.len() as u32);
816            blob.extend_from_slice(s.as_bytes());
817        }
818        let blob_size = blob.len() as u32;
819
820        let mut buf = Vec::new();
821        buf.try_reserve_exact(total).map_err(|_| {
822            Error::Internal("raw transfer string table allocation failed".to_string())
823        })?;
824        buf.extend_from_slice(&count.to_le_bytes());
825        buf.extend_from_slice(&blob_size.to_le_bytes());
826        for off in &offsets {
827            buf.extend_from_slice(&off.to_le_bytes());
828        }
829        buf.extend_from_slice(&blob);
830        Ok(buf)
831    }
832}
833
834fn encode_dense_cells(
835    row_entries: &[RowEntries],
836    min_row: u32,
837    row_count: u64,
838    col_count: u64,
839    total: u64,
840) -> Result<Vec<u8>> {
841    let total = usize::try_from(total)
842        .map_err(|_| Error::Internal("dense raw transfer output is too large".to_string()))?;
843    let row_count = usize::try_from(row_count)
844        .map_err(|_| Error::Internal("dense raw transfer row count is too large".to_string()))?;
845    let col_count = usize::try_from(col_count)
846        .map_err(|_| Error::Internal("dense raw transfer column count is too large".to_string()))?;
847    let mut buf = Vec::new();
848    buf.try_reserve_exact(total)
849        .map_err(|_| Error::Internal("dense raw transfer allocation failed".to_string()))?;
850    buf.resize(total, 0);
851
852    for re in row_entries {
853        let row_offset = (re.row_num - min_row) as usize;
854        for ce in &re.cells {
855            let cell_idx = row_offset * col_count + ce.col as usize;
856            let pos = cell_idx * CELL_STRIDE;
857            buf[pos] = ce.type_tag;
858            buf[pos + 1..pos + 9].copy_from_slice(&ce.payload);
859        }
860    }
861
862    debug_assert_eq!(buf.len(), row_count * col_count * CELL_STRIDE);
863    Ok(buf)
864}
865
866fn sparse_cell_data_size(row_entries: &[RowEntries], limits: TraversalLimits) -> Result<u64> {
867    row_entries.iter().try_fold(0u64, |total, row| {
868        let cells = checked_output_mul(row.cells.len() as u64, SPARSE_CELL_STRIDE as u64, limits)?;
869        checked_output_add(total, checked_output_add(2, cells, limits)?, limits)
870    })
871}
872
873fn encode_sparse_cells(
874    row_entries: &[RowEntries],
875    total: u64,
876    _limits: TraversalLimits,
877) -> Result<Vec<u8>> {
878    let total = usize::try_from(total)
879        .map_err(|_| Error::Internal("sparse raw transfer output is too large".to_string()))?;
880    let mut buf = Vec::new();
881    buf.try_reserve_exact(total)
882        .map_err(|_| Error::Internal("sparse raw transfer allocation failed".to_string()))?;
883    for row in row_entries {
884        let count = u16::try_from(row.cells.len())
885            .map_err(|_| Error::Internal("raw transfer row has too many cells".to_string()))?;
886        buf.extend_from_slice(&count.to_le_bytes());
887        for cell in &row.cells {
888            let col = u16::try_from(cell.col).map_err(|_| {
889                Error::Internal("raw transfer relative column is too large".to_string())
890            })?;
891            buf.extend_from_slice(&col.to_le_bytes());
892            buf.push(cell.type_tag);
893            buf.extend_from_slice(&cell.payload);
894        }
895    }
896
897    Ok(buf)
898}
899
900fn build_row_index(
901    row_entries: &[RowEntries],
902    min_row: u32,
903    dense_row_count: u64,
904    col_count: u64,
905    sparse: bool,
906    total: u64,
907) -> Result<Vec<u8>> {
908    let total = usize::try_from(total)
909        .map_err(|_| Error::Internal("raw transfer row index is too large".to_string()))?;
910    let mut index = Vec::new();
911    index
912        .try_reserve_exact(total)
913        .map_err(|_| Error::Internal("raw transfer row index allocation failed".to_string()))?;
914
915    if sparse {
916        let mut sparse_offset = 0u32;
917        for row in row_entries {
918            index.extend_from_slice(&row.row_num.to_le_bytes());
919            index.extend_from_slice(&sparse_offset.to_le_bytes());
920            let row_size = 2u32
921                .checked_add(
922                    u32::try_from(row.cells.len())
923                        .map_err(|_| Error::Internal("raw transfer row is too large".to_string()))?
924                        .checked_mul(SPARSE_CELL_STRIDE as u32)
925                        .ok_or_else(|| {
926                            Error::Internal("raw transfer row is too large".to_string())
927                        })?,
928                )
929                .ok_or_else(|| Error::Internal("raw transfer offset overflow".to_string()))?;
930            sparse_offset = sparse_offset
931                .checked_add(row_size)
932                .ok_or_else(|| Error::Internal("raw transfer offset overflow".to_string()))?;
933        }
934    } else {
935        for row_offset in 0..dense_row_count {
936            let row_num = min_row
937                .checked_add(u32::try_from(row_offset).map_err(|_| {
938                    Error::Internal("raw transfer row offset is too large".to_string())
939                })?)
940                .ok_or_else(|| Error::Internal("raw transfer row overflow".to_string()))?;
941            index.extend_from_slice(&row_num.to_le_bytes());
942            let offset = row_offset
943                .checked_mul(col_count)
944                .and_then(|cells| cells.checked_mul(CELL_STRIDE as u64))
945                .and_then(|bytes| u32::try_from(bytes).ok())
946                .ok_or_else(|| Error::Internal("raw transfer offset overflow".to_string()))?;
947            index.extend_from_slice(&offset.to_le_bytes());
948        }
949    }
950
951    Ok(index)
952}
953
954#[cfg(test)]
955#[allow(
956    clippy::field_reassign_with_default,
957    clippy::needless_lifetimes,
958    clippy::approx_constant
959)]
960mod tests {
961    use super::*;
962    use sheetkit_xml::shared_strings::{R, T};
963    use sheetkit_xml::worksheet::{
964        Cell, CellFormula, CellTypeTag, CompactCellRef, InlineString, Row, SheetData, WorksheetXml,
965    };
966
967    fn make_cell(col_ref: &str, col_num: u32, t: CellTypeTag, v: Option<&str>) -> Cell {
968        Cell {
969            r: CompactCellRef::new(col_ref).unwrap(),
970            col: col_num,
971            s: None,
972            t,
973            v: v.map(|s| s.to_string()),
974            f: None,
975            is: None,
976        }
977    }
978
979    fn make_row(row_num: u32, cells: Vec<Cell>) -> Row {
980        Row {
981            r: row_num,
982            spans: None,
983            s: None,
984            custom_format: None,
985            ht: None,
986            hidden: None,
987            custom_height: None,
988            outline_level: None,
989            cells,
990        }
991    }
992
993    fn make_worksheet(rows: Vec<Row>) -> WorksheetXml {
994        let mut ws = WorksheetXml::default();
995        ws.sheet_data = SheetData { rows };
996        ws
997    }
998
999    fn make_sst(strings: &[&str]) -> SharedStringTable {
1000        let mut sst = SharedStringTable::new();
1001        for s in strings {
1002            sst.add(s);
1003        }
1004        sst
1005    }
1006
1007    fn read_u32_le(buf: &[u8], offset: usize) -> u32 {
1008        u32::from_le_bytes(buf[offset..offset + 4].try_into().unwrap())
1009    }
1010
1011    fn read_u16_le(buf: &[u8], offset: usize) -> u16 {
1012        u16::from_le_bytes(buf[offset..offset + 2].try_into().unwrap())
1013    }
1014
1015    /// Parse a buffer and return (row_index_end, string_section_end, cell_data_start, flags).
1016    fn parse_sections(buf: &[u8]) -> (usize, usize, usize, u32) {
1017        let row_count = read_u32_le(buf, 6) as usize;
1018        let flags = read_u32_le(buf, 12);
1019        let row_index_end = HEADER_SIZE + row_count * 8;
1020        let string_count = read_u32_le(buf, row_index_end) as usize;
1021        let blob_size = read_u32_le(buf, row_index_end + 4) as usize;
1022        let string_section_end = row_index_end + 8 + string_count * 4 + blob_size;
1023        (row_index_end, string_section_end, string_section_end, flags)
1024    }
1025
1026    /// Read a string from the string table by index.
1027    fn read_string(buf: &[u8], string_section_start: usize, idx: usize) -> String {
1028        let count = read_u32_le(buf, string_section_start) as usize;
1029        let blob_size = read_u32_le(buf, string_section_start + 4) as usize;
1030        assert!(
1031            idx < count,
1032            "string index {idx} out of range (count={count})"
1033        );
1034        let offsets_start = string_section_start + 8;
1035        let blob_start = offsets_start + count * 4;
1036
1037        let start = read_u32_le(buf, offsets_start + idx * 4) as usize;
1038        let end = if idx + 1 < count {
1039            read_u32_le(buf, offsets_start + (idx + 1) * 4) as usize
1040        } else {
1041            blob_size
1042        };
1043        String::from_utf8(buf[blob_start + start..blob_start + end].to_vec()).unwrap()
1044    }
1045
1046    /// Read the cell type tag and payload from cell data at a given position.
1047    fn read_cell_at(
1048        buf: &[u8],
1049        cell_data_start: usize,
1050        is_sparse: bool,
1051        cell_index: usize,
1052    ) -> (u8, &[u8]) {
1053        if is_sparse {
1054            panic!("use read_sparse_row for sparse format");
1055        }
1056        let pos = cell_data_start + cell_index * CELL_STRIDE;
1057        (buf[pos], &buf[pos + 1..pos + 9])
1058    }
1059
1060    /// Read sparse row: returns vec of (col, type_tag, payload_slice).
1061    fn read_sparse_row<'a>(buf: &'a [u8], row_offset: usize) -> Vec<(u16, u8, &'a [u8])> {
1062        let cell_count = read_u16_le(buf, row_offset) as usize;
1063        let mut result = Vec::with_capacity(cell_count);
1064        let mut pos = row_offset + 2;
1065        for _ in 0..cell_count {
1066            let col = read_u16_le(buf, pos);
1067            let type_tag = buf[pos + 2];
1068            let payload = &buf[pos + 3..pos + 11];
1069            result.push((col, type_tag, payload));
1070            pos += SPARSE_CELL_STRIDE;
1071        }
1072        result
1073    }
1074
1075    #[test]
1076    fn test_empty_sheet() {
1077        let ws = make_worksheet(vec![]);
1078        let sst = SharedStringTable::new();
1079        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1080
1081        assert_eq!(buf.len(), HEADER_SIZE);
1082        assert_eq!(read_u32_le(&buf, 0), MAGIC);
1083        assert_eq!(read_u16_le(&buf, 4), VERSION);
1084        assert_eq!(read_u32_le(&buf, 6), 0);
1085        assert_eq!(read_u16_le(&buf, 10), 0);
1086        assert_eq!(read_u32_le(&buf, 12), 0);
1087    }
1088
1089    #[test]
1090    fn test_single_number_cell() {
1091        let ws = make_worksheet(vec![make_row(
1092            1,
1093            vec![make_cell("A1", 1, CellTypeTag::None, Some("42.5"))],
1094        )]);
1095        let sst = SharedStringTable::new();
1096        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1097
1098        assert_eq!(read_u32_le(&buf, 0), MAGIC);
1099        let row_count = read_u32_le(&buf, 6);
1100        let col_count = read_u16_le(&buf, 10) as usize;
1101        assert_eq!(row_count, 1);
1102        assert_eq!(col_count, 1);
1103
1104        let (st_start, _, cd_start, flags) = parse_sections(&buf);
1105        let is_sparse = flags & FLAG_SPARSE != 0;
1106
1107        if is_sparse {
1108            let cells = read_sparse_row(&buf, cd_start);
1109            assert_eq!(cells.len(), 1);
1110            assert_eq!(cells[0].1, TYPE_NUMBER);
1111            let val = f64::from_le_bytes(cells[0].2.try_into().unwrap());
1112            assert!((val - 42.5).abs() < f64::EPSILON);
1113        } else {
1114            let (tag, payload) = read_cell_at(&buf, cd_start, false, 0);
1115            assert_eq!(tag, TYPE_NUMBER);
1116            let val = f64::from_le_bytes(payload.try_into().unwrap());
1117            assert!((val - 42.5).abs() < f64::EPSILON);
1118        }
1119
1120        let _ = st_start;
1121    }
1122
1123    #[test]
1124    fn test_string_cell_sst() {
1125        let sst = make_sst(&["Hello", "World"]);
1126        let ws = make_worksheet(vec![make_row(
1127            1,
1128            vec![make_cell("A1", 1, CellTypeTag::SharedString, Some("1"))],
1129        )]);
1130        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1131
1132        let (st_start, _, cd_start, flags) = parse_sections(&buf);
1133        let is_sparse = flags & FLAG_SPARSE != 0;
1134
1135        let string_count = read_u32_le(&buf, st_start);
1136        assert_eq!(string_count, 1);
1137
1138        let s0 = read_string(&buf, st_start, 0);
1139        assert_eq!(s0, "World");
1140
1141        let str_idx = if is_sparse {
1142            let cells = read_sparse_row(&buf, cd_start);
1143            assert_eq!(cells[0].1, TYPE_STRING);
1144            u32::from_le_bytes(cells[0].2[..4].try_into().unwrap()) as usize
1145        } else {
1146            let (tag, payload) = read_cell_at(&buf, cd_start, false, 0);
1147            assert_eq!(tag, TYPE_STRING);
1148            u32::from_le_bytes(payload[..4].try_into().unwrap()) as usize
1149        };
1150        assert_eq!(
1151            str_idx, 0,
1152            "should reference local string index 0 = 'World'"
1153        );
1154    }
1155
1156    #[test]
1157    fn test_bool_cell() {
1158        let sst = SharedStringTable::new();
1159        let ws = make_worksheet(vec![make_row(
1160            1,
1161            vec![
1162                make_cell("A1", 1, CellTypeTag::Boolean, Some("1")),
1163                make_cell("B1", 2, CellTypeTag::Boolean, Some("0")),
1164            ],
1165        )]);
1166        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1167
1168        let col_count = read_u16_le(&buf, 10) as usize;
1169        assert_eq!(col_count, 2);
1170
1171        let (_, _, cd_start, flags) = parse_sections(&buf);
1172        let is_sparse = flags & FLAG_SPARSE != 0;
1173
1174        if is_sparse {
1175            let cells = read_sparse_row(&buf, cd_start);
1176            assert_eq!(cells.len(), 2);
1177            assert_eq!(cells[0].1, TYPE_BOOL);
1178            assert_eq!(cells[0].2[0], 1);
1179            assert_eq!(cells[1].1, TYPE_BOOL);
1180            assert_eq!(cells[1].2[0], 0);
1181        } else {
1182            let (tag0, payload0) = read_cell_at(&buf, cd_start, false, 0);
1183            assert_eq!(tag0, TYPE_BOOL);
1184            assert_eq!(payload0[0], 1);
1185            let (tag1, payload1) = read_cell_at(&buf, cd_start, false, 1);
1186            assert_eq!(tag1, TYPE_BOOL);
1187            assert_eq!(payload1[0], 0);
1188        }
1189    }
1190
1191    #[test]
1192    fn test_error_cell() {
1193        let sst = SharedStringTable::new();
1194        let ws = make_worksheet(vec![make_row(
1195            1,
1196            vec![make_cell("A1", 1, CellTypeTag::Error, Some("#DIV/0!"))],
1197        )]);
1198        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1199
1200        let (st_start, _, cd_start, flags) = parse_sections(&buf);
1201        let is_sparse = flags & FLAG_SPARSE != 0;
1202
1203        let string_count = read_u32_le(&buf, st_start);
1204        assert!(string_count >= 1);
1205
1206        let type_tag = if is_sparse {
1207            let cells = read_sparse_row(&buf, cd_start);
1208            cells[0].1
1209        } else {
1210            let (tag, _) = read_cell_at(&buf, cd_start, false, 0);
1211            tag
1212        };
1213        assert_eq!(type_tag, TYPE_ERROR);
1214
1215        let error_str = read_string(&buf, st_start, 0);
1216        assert_eq!(error_str, "#DIV/0!");
1217    }
1218
1219    #[test]
1220    fn test_formula_cell() {
1221        let sst = SharedStringTable::new();
1222        let mut cell = make_cell("A1", 1, CellTypeTag::None, Some("84"));
1223        cell.f = Some(Box::new(CellFormula {
1224            t: None,
1225            reference: None,
1226            si: None,
1227            value: Some("A2+B2".to_string()),
1228        }));
1229        let ws = make_worksheet(vec![make_row(1, vec![cell])]);
1230        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1231
1232        let (st_start, _, cd_start, flags) = parse_sections(&buf);
1233        let is_sparse = flags & FLAG_SPARSE != 0;
1234
1235        let (type_tag, str_idx) = if is_sparse {
1236            let cells = read_sparse_row(&buf, cd_start);
1237            let idx = u32::from_le_bytes(cells[0].2[..4].try_into().unwrap()) as usize;
1238            (cells[0].1, idx)
1239        } else {
1240            let (tag, payload) = read_cell_at(&buf, cd_start, false, 0);
1241            let idx = u32::from_le_bytes(payload[..4].try_into().unwrap()) as usize;
1242            (tag, idx)
1243        };
1244
1245        assert_eq!(type_tag, TYPE_FORMULA);
1246        let formula = read_string(&buf, st_start, str_idx);
1247        assert_eq!(formula, "A2+B2");
1248    }
1249
1250    #[test]
1251    fn test_shared_formula_followers_shift_relative_references() {
1252        let sst = SharedStringTable::new();
1253        let mut master = make_cell("B2", 2, CellTypeTag::None, Some("1"));
1254        master.f = Some(Box::new(CellFormula {
1255            t: Some("shared".to_string()),
1256            reference: Some("B2:C3".to_string()),
1257            si: Some(7),
1258            value: Some("A2+$A$1".to_string()),
1259        }));
1260        let mut across = make_cell("C2", 3, CellTypeTag::None, Some("2"));
1261        across.f = Some(Box::new(CellFormula {
1262            t: Some("shared".to_string()),
1263            reference: None,
1264            si: Some(7),
1265            value: None,
1266        }));
1267        let mut down = make_cell("B3", 2, CellTypeTag::None, Some("3"));
1268        down.f = Some(Box::new(CellFormula {
1269            t: Some("shared".to_string()),
1270            reference: None,
1271            si: Some(7),
1272            value: None,
1273        }));
1274        let ws = make_worksheet(vec![
1275            make_row(2, vec![master, across]),
1276            make_row(3, vec![down]),
1277        ]);
1278        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1279        let (st_start, _, cd_start, flags) = parse_sections(&buf);
1280        assert_ne!(flags & FLAG_SPARSE, 0);
1281        let row2 = read_sparse_row(&buf, cd_start);
1282        let row3_offset = read_u32_le(&buf, HEADER_SIZE + 12) as usize;
1283        let row3 = read_sparse_row(&buf, cd_start + row3_offset);
1284
1285        for ((_, tag, payload), expected) in row2
1286            .into_iter()
1287            .chain(row3)
1288            .zip(["A2+$A$1", "B2+$A$1", "A3+$A$1"])
1289        {
1290            assert_eq!(tag, TYPE_FORMULA);
1291            let string_idx = u32::from_le_bytes(payload[..4].try_into().unwrap()) as usize;
1292            assert_eq!(read_string(&buf, st_start, string_idx), expected);
1293        }
1294    }
1295
1296    #[test]
1297    fn test_shared_formula_without_master_uses_cached_value_or_empty() {
1298        let sst = SharedStringTable::new();
1299        let mut cached = make_cell("A1", 1, CellTypeTag::None, Some("17"));
1300        cached.f = Some(Box::new(CellFormula {
1301            t: Some("shared".to_string()),
1302            reference: None,
1303            si: Some(99),
1304            value: None,
1305        }));
1306        let mut missing = make_cell("B1", 2, CellTypeTag::None, None);
1307        missing.f = Some(Box::new(CellFormula {
1308            t: Some("shared".to_string()),
1309            reference: None,
1310            si: Some(99),
1311            value: None,
1312        }));
1313        let ws = make_worksheet(vec![make_row(1, vec![cached, missing])]);
1314        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1315        let (_, _, cd_start, flags) = parse_sections(&buf);
1316        assert_ne!(flags & FLAG_SPARSE, 0);
1317        let cells = read_sparse_row(&buf, cd_start);
1318        let (_, cached_tag, cached_payload) = cells[0];
1319        assert_eq!(cached_tag, TYPE_NUMBER);
1320        assert_eq!(f64::from_le_bytes(cached_payload.try_into().unwrap()), 17.0);
1321        let (_, missing_tag, _) = cells[1];
1322        assert_eq!(missing_tag, TYPE_EMPTY);
1323    }
1324
1325    #[test]
1326    fn shared_formula_master_clone_obeys_exact_preallocation_budget() {
1327        let formula = "SUM(A1:B2)+C3";
1328        let mut master = make_cell("A1", 1, CellTypeTag::None, Some("1"));
1329        master.f = Some(Box::new(CellFormula {
1330            t: Some("shared".to_string()),
1331            reference: Some("A1:A2".to_string()),
1332            si: Some(3),
1333            value: Some(formula.to_string()),
1334        }));
1335        let ws = make_worksheet(vec![make_row(1, vec![master])]);
1336
1337        let exact_limits = TraversalLimits::new(1, 1, 1, formula.len() as u64).unwrap();
1338        let mut exact_budget = RawValueBudget::new(exact_limits);
1339        SharedFormulaResolver::new(&ws, &mut exact_budget).unwrap();
1340
1341        let under_limits = TraversalLimits::new(1, 1, 1, formula.len() as u64 - 1).unwrap();
1342        let mut under_budget = RawValueBudget::new(under_limits);
1343        let error = SharedFormulaResolver::new(&ws, &mut under_budget).unwrap_err();
1344        let Error::ResourceLimitExceeded(metadata) = error else {
1345            panic!("expected resource limit error");
1346        };
1347        assert_eq!(metadata.dimension(), ResourceDimension::OutputBytes);
1348        assert_eq!(metadata.observed(), formula.len() as u64);
1349    }
1350
1351    #[test]
1352    fn shared_formula_rewrites_share_one_cumulative_budget() {
1353        let formula = "A1+B1";
1354        let mut master = make_cell("A1", 1, CellTypeTag::None, Some("1"));
1355        master.f = Some(Box::new(CellFormula {
1356            t: Some("shared".to_string()),
1357            reference: Some("A1:B1".to_string()),
1358            si: Some(4),
1359            value: Some(formula.to_string()),
1360        }));
1361        let mut follower = make_cell("B1", 2, CellTypeTag::None, Some("2"));
1362        follower.f = Some(Box::new(CellFormula {
1363            t: Some("shared".to_string()),
1364            reference: None,
1365            si: Some(4),
1366            value: None,
1367        }));
1368        let ws = make_worksheet(vec![make_row(1, vec![master, follower.clone()])]);
1369        let total = (formula.len() * 3) as u64;
1370
1371        let exact_limits = TraversalLimits::new(1, 2, 2, total).unwrap();
1372        let mut exact_budget = RawValueBudget::new(exact_limits);
1373        let resolver = SharedFormulaResolver::new(&ws, &mut exact_budget).unwrap();
1374        assert_eq!(
1375            resolver
1376                .formula_for(&follower, &mut exact_budget)
1377                .unwrap()
1378                .as_deref(),
1379            Some("B1+C1")
1380        );
1381
1382        let under_limits = TraversalLimits::new(1, 2, 2, total - 1).unwrap();
1383        let mut under_budget = RawValueBudget::new(under_limits);
1384        let resolver = SharedFormulaResolver::new(&ws, &mut under_budget).unwrap();
1385        let error = resolver
1386            .formula_for(&follower, &mut under_budget)
1387            .unwrap_err();
1388        let Error::ResourceLimitExceeded(metadata) = error else {
1389            panic!("expected resource limit error");
1390        };
1391        assert_eq!(metadata.observed(), total);
1392
1393        let preflight_limit = (formula.len() * 2 - 1) as u64;
1394        let preflight_limits = TraversalLimits::new(1, 2, 2, preflight_limit).unwrap();
1395        let mut preflight_budget = RawValueBudget::new(preflight_limits);
1396        let resolver = SharedFormulaResolver::new(&ws, &mut preflight_budget).unwrap();
1397        let error = resolver
1398            .formula_for(&follower, &mut preflight_budget)
1399            .unwrap_err();
1400        let Error::ResourceLimitExceeded(metadata) = error else {
1401            panic!("expected resource limit error");
1402        };
1403        assert_eq!(metadata.observed(), (formula.len() * 2) as u64);
1404    }
1405
1406    #[test]
1407    fn inline_rich_text_collection_obeys_exact_and_cumulative_budgets() {
1408        let inline = InlineString {
1409            t: None,
1410            r: vec![
1411                R {
1412                    r_pr: None,
1413                    t: T {
1414                        xml_space: None,
1415                        value: "Bold".to_string(),
1416                    },
1417                },
1418                R {
1419                    r_pr: None,
1420                    t: T {
1421                        xml_space: None,
1422                        value: " Text".to_string(),
1423                    },
1424                },
1425            ],
1426            r_ph: vec![],
1427        };
1428        let charged_per_call = (inline.r.len() + "Bold Text".len()) as u64;
1429
1430        let exact_limits = TraversalLimits::new(1, 1, 1, charged_per_call * 2).unwrap();
1431        let mut exact_budget = RawValueBudget::new(exact_limits);
1432        assert_eq!(
1433            inline_string_visible_text(&inline, &mut exact_budget)
1434                .unwrap()
1435                .as_ref(),
1436            "Bold Text"
1437        );
1438        inline_string_visible_text(&inline, &mut exact_budget).unwrap();
1439
1440        let under_limits = TraversalLimits::new(1, 1, 1, charged_per_call * 2 - 1).unwrap();
1441        let mut under_budget = RawValueBudget::new(under_limits);
1442        inline_string_visible_text(&inline, &mut under_budget).unwrap();
1443        let error = inline_string_visible_text(&inline, &mut under_budget).unwrap_err();
1444        let Error::ResourceLimitExceeded(metadata) = error else {
1445            panic!("expected resource limit error");
1446        };
1447        assert_eq!(metadata.observed(), charged_per_call * 2);
1448    }
1449
1450    #[test]
1451    fn empty_inline_rich_runs_are_charged_before_iteration() {
1452        let run_count = 16usize;
1453        let inline = InlineString {
1454            t: None,
1455            r: (0..run_count)
1456                .map(|_| R {
1457                    r_pr: None,
1458                    t: T {
1459                        xml_space: None,
1460                        value: String::new(),
1461                    },
1462                })
1463                .collect(),
1464            r_ph: vec![],
1465        };
1466
1467        let exact_limits = TraversalLimits::new(1, 1, 1, (run_count * 2) as u64).unwrap();
1468        let mut exact_budget = RawValueBudget::new(exact_limits);
1469        assert_eq!(
1470            inline_string_visible_text(&inline, &mut exact_budget)
1471                .unwrap()
1472                .as_ref(),
1473            ""
1474        );
1475        inline_string_visible_text(&inline, &mut exact_budget).unwrap();
1476
1477        let under_limits = TraversalLimits::new(1, 1, 1, (run_count * 2 - 1) as u64).unwrap();
1478        let mut under_budget = RawValueBudget::new(under_limits);
1479        inline_string_visible_text(&inline, &mut under_budget).unwrap();
1480        let error = inline_string_visible_text(&inline, &mut under_budget).unwrap_err();
1481        let Error::ResourceLimitExceeded(metadata) = error else {
1482            panic!("expected resource limit error");
1483        };
1484        assert_eq!(metadata.observed(), (run_count * 2) as u64);
1485    }
1486
1487    #[test]
1488    fn shared_formula_extreme_offsets_stay_inside_the_excel_grid() {
1489        let mut master = make_cell("A1", 1, CellTypeTag::None, Some("1"));
1490        master.f = Some(Box::new(CellFormula {
1491            t: Some("shared".to_string()),
1492            reference: Some("A1:XFD1048576".to_string()),
1493            si: Some(8),
1494            value: Some("A1+XFD1048576".to_string()),
1495        }));
1496        let mut follower = make_cell("XFD1048576", 16_384, CellTypeTag::None, Some("2"));
1497        follower.f = Some(Box::new(CellFormula {
1498            t: Some("shared".to_string()),
1499            reference: None,
1500            si: Some(8),
1501            value: None,
1502        }));
1503        let ws = make_worksheet(vec![
1504            make_row(1, vec![master]),
1505            make_row(1_048_576, vec![follower.clone()]),
1506        ]);
1507        let mut budget = RawValueBudget::new(TraversalLimits::default());
1508        let resolver = SharedFormulaResolver::new(&ws, &mut budget).unwrap();
1509
1510        assert_eq!(
1511            resolver
1512                .formula_for(&follower, &mut budget)
1513                .unwrap()
1514                .as_deref(),
1515            Some("XFD1048576+XFD1048576")
1516        );
1517    }
1518
1519    #[test]
1520    fn test_inline_string_cell() {
1521        let sst = SharedStringTable::new();
1522        let mut cell = make_cell("A1", 1, CellTypeTag::InlineString, None);
1523        cell.is = Some(Box::new(InlineString {
1524            t: Some("Inline Text".to_string()),
1525            r: vec![],
1526            r_ph: vec![],
1527        }));
1528        let ws = make_worksheet(vec![make_row(1, vec![cell])]);
1529        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1530
1531        let (st_start, _, cd_start, flags) = parse_sections(&buf);
1532        let is_sparse = flags & FLAG_SPARSE != 0;
1533
1534        let (type_tag, str_idx) = if is_sparse {
1535            let cells = read_sparse_row(&buf, cd_start);
1536            let idx = u32::from_le_bytes(cells[0].2[..4].try_into().unwrap()) as usize;
1537            (cells[0].1, idx)
1538        } else {
1539            let (tag, payload) = read_cell_at(&buf, cd_start, false, 0);
1540            let idx = u32::from_le_bytes(payload[..4].try_into().unwrap()) as usize;
1541            (tag, idx)
1542        };
1543
1544        assert_eq!(type_tag, TYPE_STRING);
1545        let text = read_string(&buf, st_start, str_idx);
1546        assert_eq!(text, "Inline Text");
1547    }
1548
1549    #[test]
1550    fn test_inline_string_preserves_escaped_visible_text() {
1551        let sst = SharedStringTable::new();
1552        let mut cell = make_cell("A1", 1, CellTypeTag::InlineString, None);
1553        cell.is = Some(Box::new(InlineString {
1554            t: Some("A < B & C".to_string()),
1555            r: vec![],
1556            r_ph: vec![],
1557        }));
1558        let ws = make_worksheet(vec![make_row(1, vec![cell])]);
1559        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1560        let (st_start, _, cd_start, _) = parse_sections(&buf);
1561        let cells = read_sparse_row(&buf, cd_start);
1562        let (_, tag, payload) = cells[0];
1563        assert_eq!(tag, TYPE_STRING);
1564        let string_idx = u32::from_le_bytes(payload[..4].try_into().unwrap()) as usize;
1565        assert_eq!(read_string(&buf, st_start, string_idx), "A < B & C");
1566    }
1567
1568    #[test]
1569    fn test_inline_rich_text_concatenates_runs_without_phonetics() {
1570        let sst = SharedStringTable::new();
1571        let mut cell = make_cell("A1", 1, CellTypeTag::InlineString, None);
1572        cell.is = Some(Box::new(InlineString {
1573            t: None,
1574            r: vec![
1575                R {
1576                    r_pr: None,
1577                    t: T {
1578                        xml_space: None,
1579                        value: "Bold".to_string(),
1580                    },
1581                },
1582                R {
1583                    r_pr: None,
1584                    t: T {
1585                        xml_space: Some("preserve".to_string()),
1586                        value: " Text & More".to_string(),
1587                    },
1588                },
1589            ],
1590            r_ph: vec![sheetkit_xml::worksheet::PhoneticRun {
1591                sb: Some(0),
1592                eb: Some(4),
1593                value: "phonetic".to_string(),
1594            }],
1595        }));
1596        let ws = make_worksheet(vec![make_row(1, vec![cell])]);
1597        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1598        let (st_start, _, cd_start, _) = parse_sections(&buf);
1599        let cells = read_sparse_row(&buf, cd_start);
1600        let (_, tag, payload) = cells[0];
1601        assert_eq!(tag, TYPE_STRING);
1602        let string_idx = u32::from_le_bytes(payload[..4].try_into().unwrap()) as usize;
1603        assert_eq!(read_string(&buf, st_start, string_idx), "Bold Text & More");
1604    }
1605
1606    #[test]
1607    fn test_date_cell() {
1608        let sst = SharedStringTable::new();
1609        let ws = make_worksheet(vec![make_row(
1610            1,
1611            vec![make_cell("A1", 1, CellTypeTag::Date, Some("44927.0"))],
1612        )]);
1613        let buf = sheet_to_raw_buffer_with_options(
1614            &ws,
1615            &sst,
1616            TraversalOptions::new(TraversalMode::Dense),
1617        )
1618        .unwrap();
1619
1620        let (_, _, cd_start, flags) = parse_sections(&buf);
1621        let is_sparse = flags & FLAG_SPARSE != 0;
1622
1623        if is_sparse {
1624            let cells = read_sparse_row(&buf, cd_start);
1625            assert_eq!(cells[0].1, TYPE_DATE);
1626            let val = f64::from_le_bytes(cells[0].2.try_into().unwrap());
1627            assert!((val - 44927.0).abs() < f64::EPSILON);
1628        } else {
1629            let (tag, payload) = read_cell_at(&buf, cd_start, false, 0);
1630            assert_eq!(tag, TYPE_DATE);
1631            let val = f64::from_le_bytes(payload.try_into().unwrap());
1632            assert!((val - 44927.0).abs() < f64::EPSILON);
1633        }
1634    }
1635
1636    #[test]
1637    fn test_mixed_types_row() {
1638        let sst = make_sst(&["Hello"]);
1639        let ws = make_worksheet(vec![make_row(
1640            1,
1641            vec![
1642                make_cell("A1", 1, CellTypeTag::None, Some("3.14")),
1643                make_cell("B1", 2, CellTypeTag::SharedString, Some("0")),
1644                make_cell("C1", 3, CellTypeTag::Boolean, Some("1")),
1645            ],
1646        )]);
1647        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1648
1649        let col_count = read_u16_le(&buf, 10) as usize;
1650        assert_eq!(col_count, 3);
1651
1652        let (_, _, cd_start, flags) = parse_sections(&buf);
1653        let is_sparse = flags & FLAG_SPARSE != 0;
1654
1655        if is_sparse {
1656            let cells = read_sparse_row(&buf, cd_start);
1657            assert_eq!(cells.len(), 3);
1658            assert_eq!(cells[0].1, TYPE_NUMBER);
1659            assert_eq!(cells[1].1, TYPE_STRING);
1660            assert_eq!(cells[2].1, TYPE_BOOL);
1661        } else {
1662            let (t0, p0) = read_cell_at(&buf, cd_start, false, 0);
1663            assert_eq!(t0, TYPE_NUMBER);
1664            let val = f64::from_le_bytes(p0.try_into().unwrap());
1665            assert!((val - 3.14).abs() < f64::EPSILON);
1666
1667            let (t1, _) = read_cell_at(&buf, cd_start, false, 1);
1668            assert_eq!(t1, TYPE_STRING);
1669
1670            let (t2, p2) = read_cell_at(&buf, cd_start, false, 2);
1671            assert_eq!(t2, TYPE_BOOL);
1672            assert_eq!(p2[0], 1);
1673        }
1674    }
1675
1676    #[test]
1677    fn test_dense_format() {
1678        let sst = SharedStringTable::new();
1679        let mut rows = Vec::new();
1680        for r in 1..=5u32 {
1681            let mut cells = Vec::new();
1682            for c in 1..=5u32 {
1683                let col_letter = match c {
1684                    1 => "A",
1685                    2 => "B",
1686                    3 => "C",
1687                    4 => "D",
1688                    5 => "E",
1689                    _ => unreachable!(),
1690                };
1691                let cell_ref = format!("{col_letter}{r}");
1692                cells.push(make_cell(
1693                    &cell_ref,
1694                    c,
1695                    CellTypeTag::None,
1696                    Some(&format!("{}", r * 10 + c)),
1697                ));
1698            }
1699            rows.push(make_row(r, cells));
1700        }
1701        let ws = make_worksheet(rows);
1702        let buf = sheet_to_raw_buffer_with_options(
1703            &ws,
1704            &sst,
1705            TraversalOptions::new(TraversalMode::Dense),
1706        )
1707        .unwrap();
1708
1709        let flags = read_u32_le(&buf, 12);
1710        assert_eq!(
1711            flags & FLAG_SPARSE,
1712            0,
1713            "5x5 fully populated should be dense"
1714        );
1715
1716        let row_count = read_u32_le(&buf, 6) as usize;
1717        let col_count = read_u16_le(&buf, 10) as usize;
1718        assert_eq!(row_count, 5);
1719        assert_eq!(col_count, 5);
1720
1721        let (_, _, cd_start, _) = parse_sections(&buf);
1722        let cell_data_size = row_count * col_count * CELL_STRIDE;
1723        assert_eq!(
1724            buf.len() - cd_start,
1725            cell_data_size,
1726            "dense cell data should be exactly row_count * col_count * CELL_STRIDE"
1727        );
1728
1729        for r in 0..5usize {
1730            for c in 0..5usize {
1731                let idx = r * col_count + c;
1732                let (tag, payload) = read_cell_at(&buf, cd_start, false, idx);
1733                assert_eq!(tag, TYPE_NUMBER);
1734                let val = f64::from_le_bytes(payload.try_into().unwrap());
1735                let expected = ((r + 1) * 10 + (c + 1)) as f64;
1736                assert!(
1737                    (val - expected).abs() < f64::EPSILON,
1738                    "cell ({r},{c}) expected {expected}, got {val}"
1739                );
1740            }
1741        }
1742    }
1743
1744    #[test]
1745    fn test_sparse_format() {
1746        let sst = SharedStringTable::new();
1747        let rows = vec![
1748            make_row(1, vec![make_cell("A1", 1, CellTypeTag::None, Some("1"))]),
1749            make_row(
1750                100,
1751                vec![make_cell("T100", 20, CellTypeTag::None, Some("2"))],
1752            ),
1753        ];
1754        let ws = make_worksheet(rows);
1755        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1756
1757        let flags = read_u32_le(&buf, 12);
1758        assert_ne!(
1759            flags & FLAG_SPARSE,
1760            0,
1761            "2 cells in 100x20 grid should be sparse"
1762        );
1763
1764        let row_count = read_u32_le(&buf, 6) as usize;
1765        assert_eq!(row_count, 2);
1766        let col_count = read_u16_le(&buf, 10) as usize;
1767        assert_eq!(col_count, 20);
1768    }
1769
1770    #[test]
1771    fn test_header_format() {
1772        let sst = SharedStringTable::new();
1773        let ws = make_worksheet(vec![
1774            make_row(
1775                2,
1776                vec![
1777                    make_cell("B2", 2, CellTypeTag::None, Some("10")),
1778                    make_cell("D2", 4, CellTypeTag::None, Some("20")),
1779                ],
1780            ),
1781            make_row(5, vec![make_cell("C5", 3, CellTypeTag::None, Some("30"))]),
1782        ]);
1783        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1784
1785        assert_eq!(read_u32_le(&buf, 0), MAGIC);
1786        assert_eq!(read_u16_le(&buf, 4), VERSION);
1787        let row_count = read_u32_le(&buf, 6);
1788        assert_eq!(row_count, 2, "only occupied rows are indexed");
1789        let col_count = read_u16_le(&buf, 10);
1790        assert_eq!(col_count, 3, "cols B-D = 3 columns");
1791    }
1792
1793    #[test]
1794    fn test_string_table_format() {
1795        let sst = make_sst(&["Alpha", "Beta", "Gamma"]);
1796        let ws = make_worksheet(vec![make_row(
1797            1,
1798            vec![
1799                make_cell("A1", 1, CellTypeTag::SharedString, Some("0")),
1800                make_cell("B1", 2, CellTypeTag::SharedString, Some("2")),
1801            ],
1802        )]);
1803        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1804
1805        let (st_start, _, _, _) = parse_sections(&buf);
1806        let string_count = read_u32_le(&buf, st_start) as usize;
1807        assert_eq!(
1808            string_count, 2,
1809            "only strings used by this sheet are retained"
1810        );
1811
1812        let s0 = read_string(&buf, st_start, 0);
1813        let s1 = read_string(&buf, st_start, 1);
1814        assert_eq!(s0, "Alpha");
1815        assert_eq!(s1, "Gamma");
1816    }
1817
1818    #[test]
1819    fn test_string_table_ignores_unused_global_sst_entries() {
1820        let stale = "x".repeat(100);
1821        let sst = make_sst(&[stale.as_str(), "x"]);
1822        let ws = make_worksheet(vec![make_row(
1823            1,
1824            vec![make_cell("A1", 1, CellTypeTag::SharedString, Some("1"))],
1825        )]);
1826
1827        for max_cells in [1, 2] {
1828            let limits = TraversalLimits::new(1, 1, max_cells, 85).unwrap();
1829            let options = TraversalOptions::new(TraversalMode::Dense).with_limits(limits);
1830            let buf = sheet_to_raw_buffer_with_options(&ws, &sst, options).unwrap();
1831            let (st_start, _, _, _) = parse_sections(&buf);
1832
1833            assert_eq!(read_u32_le(&buf, st_start), 1);
1834            assert_eq!(read_string(&buf, st_start, 0), "x");
1835            assert!(buf.len() <= 85);
1836        }
1837    }
1838
1839    #[test]
1840    fn test_large_sheet_dimensions() {
1841        let sst = SharedStringTable::new();
1842        let mut rows = Vec::new();
1843        for r in [1u32, 500, 1000] {
1844            let mut cells = Vec::new();
1845            for c in [1u32, 10, 50] {
1846                let col_name = crate::utils::cell_ref::column_number_to_name(c).unwrap();
1847                let cell_ref = format!("{col_name}{r}");
1848                cells.push(make_cell(
1849                    &cell_ref,
1850                    c,
1851                    CellTypeTag::None,
1852                    Some(&format!("{}", r + c)),
1853                ));
1854            }
1855            rows.push(make_row(r, cells));
1856        }
1857        let ws = make_worksheet(rows);
1858        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
1859
1860        let row_count = read_u32_le(&buf, 6);
1861        assert_eq!(row_count, 3, "only occupied rows are indexed");
1862        let col_count = read_u16_le(&buf, 10);
1863        assert_eq!(col_count, 50, "cols A-AX = 50 columns");
1864
1865        let flags = read_u32_le(&buf, 12);
1866        assert_ne!(
1867            flags & FLAG_SPARSE,
1868            0,
1869            "9 cells in 1000x50 should be sparse"
1870        );
1871    }
1872
1873    #[test]
1874    fn sparse_default_size_depends_on_occupied_rows_not_row_distance() {
1875        let sst = SharedStringTable::new();
1876        let near = make_worksheet(vec![
1877            make_row(1, vec![make_cell("A1", 1, CellTypeTag::None, Some("1"))]),
1878            make_row(2, vec![make_cell("A2", 1, CellTypeTag::None, Some("2"))]),
1879        ]);
1880        let far = make_worksheet(vec![
1881            make_row(1, vec![make_cell("A1", 1, CellTypeTag::None, Some("1"))]),
1882            make_row(
1883                1_048_576,
1884                vec![make_cell("A1048576", 1, CellTypeTag::None, Some("2"))],
1885            ),
1886        ]);
1887
1888        let near_buffer = sheet_to_raw_buffer(&near, &sst).unwrap();
1889        let far_buffer = sheet_to_raw_buffer(&far, &sst).unwrap();
1890
1891        assert_eq!(read_u32_le(&near_buffer, 6), 2);
1892        assert_eq!(read_u32_le(&far_buffer, 6), 2);
1893        assert_eq!(near_buffer.len(), far_buffer.len());
1894        assert_eq!(read_u32_le(&far_buffer, HEADER_SIZE + 8), 1_048_576);
1895        let decoded = crate::raw_transfer_write::raw_buffer_to_cells(&far_buffer).unwrap();
1896        assert_eq!(decoded[0].0, 1);
1897        assert_eq!(decoded[1].0, 1_048_576);
1898    }
1899
1900    #[test]
1901    fn explicit_dense_mode_is_bounded_by_the_rectangle_cell_limit() {
1902        let sst = SharedStringTable::new();
1903        let ws = make_worksheet(vec![
1904            make_row(1, vec![make_cell("A1", 1, CellTypeTag::None, Some("1"))]),
1905            make_row(3, vec![make_cell("B3", 2, CellTypeTag::None, Some("2"))]),
1906        ]);
1907        let exact = TraversalLimits::new(3, 2, 6, 1024).unwrap();
1908        let buffer = sheet_to_raw_buffer_with_options(
1909            &ws,
1910            &sst,
1911            TraversalOptions::new(TraversalMode::Dense).with_limits(exact),
1912        )
1913        .unwrap();
1914        assert_eq!(read_u32_le(&buffer, 6), 3);
1915        assert_eq!(read_u32_le(&buffer, 12) & FLAG_SPARSE, 0);
1916
1917        let too_small = TraversalLimits::new(3, 2, 5, 1024).unwrap();
1918        let error = sheet_to_raw_buffer_with_options(
1919            &ws,
1920            &sst,
1921            TraversalOptions::new(TraversalMode::Dense).with_limits(too_small),
1922        )
1923        .unwrap_err();
1924        let Error::ResourceLimitExceeded(metadata) = error else {
1925            panic!("expected resource limit error");
1926        };
1927        assert_eq!(metadata.dimension(), ResourceDimension::CellCount);
1928        assert_eq!(metadata.limit(), 5);
1929        assert_eq!(metadata.observed(), 6);
1930    }
1931
1932    #[test]
1933    fn sparse_mode_enforces_occupied_cell_and_output_exact_boundaries() {
1934        let sst = SharedStringTable::new();
1935        let ws = make_worksheet(vec![make_row(
1936            1,
1937            vec![
1938                make_cell("A1", 1, CellTypeTag::None, Some("1")),
1939                make_cell("B1", 2, CellTypeTag::None, Some("2")),
1940            ],
1941        )]);
1942        let baseline = sheet_to_raw_buffer(&ws, &sst).unwrap();
1943        let exact = TraversalLimits::new(1, 2, 2, baseline.len() as u64).unwrap();
1944        sheet_to_raw_buffer_with_options(
1945            &ws,
1946            &sst,
1947            TraversalOptions::new(TraversalMode::Sparse).with_limits(exact),
1948        )
1949        .unwrap();
1950
1951        let cell_error = sheet_to_raw_buffer_with_options(
1952            &ws,
1953            &sst,
1954            TraversalOptions::new(TraversalMode::Sparse)
1955                .with_limits(TraversalLimits::new(1, 2, 1, 1024).unwrap()),
1956        )
1957        .unwrap_err();
1958        let Error::ResourceLimitExceeded(cell_metadata) = cell_error else {
1959            panic!("expected resource limit error");
1960        };
1961        assert_eq!(cell_metadata.dimension(), ResourceDimension::CellCount);
1962        assert_eq!(cell_metadata.observed(), 2);
1963
1964        let output_error = sheet_to_raw_buffer_with_options(
1965            &ws,
1966            &sst,
1967            TraversalOptions::new(TraversalMode::Sparse)
1968                .with_limits(TraversalLimits::new(1, 2, 2, baseline.len() as u64 - 1).unwrap()),
1969        )
1970        .unwrap_err();
1971        let Error::ResourceLimitExceeded(output_metadata) = output_error else {
1972            panic!("expected resource limit error");
1973        };
1974        assert_eq!(output_metadata.dimension(), ResourceDimension::OutputBytes);
1975        assert_eq!(output_metadata.observed(), baseline.len() as u64);
1976    }
1977
1978    #[test]
1979    fn empty_output_still_obeys_the_output_limit() {
1980        let limits = TraversalLimits::new(1, 1, 1, HEADER_SIZE as u64 - 1).unwrap();
1981        let error = sheet_to_raw_buffer_with_options(
1982            &make_worksheet(vec![]),
1983            &SharedStringTable::new(),
1984            TraversalOptions::default().with_limits(limits),
1985        )
1986        .unwrap_err();
1987        let Error::ResourceLimitExceeded(metadata) = error else {
1988            panic!("expected resource limit error");
1989        };
1990        assert_eq!(metadata.dimension(), ResourceDimension::OutputBytes);
1991        assert_eq!(metadata.observed(), HEADER_SIZE as u64);
1992    }
1993
1994    #[test]
1995    fn test_row_index_entries() {
1996        let sst = SharedStringTable::new();
1997        let ws = make_worksheet(vec![
1998            make_row(1, vec![make_cell("A1", 1, CellTypeTag::None, Some("1"))]),
1999            make_row(3, vec![make_cell("A3", 1, CellTypeTag::None, Some("3"))]),
2000        ]);
2001        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
2002
2003        let row_count = read_u32_le(&buf, 6) as usize;
2004        assert_eq!(row_count, 2);
2005
2006        let row_index_start = HEADER_SIZE;
2007        let row1_num = read_u32_le(&buf, row_index_start);
2008        let row1_offset = read_u32_le(&buf, row_index_start + 4);
2009        assert_eq!(row1_num, 1);
2010        assert_ne!(row1_offset, EMPTY_ROW_OFFSET);
2011
2012        let row3_num = read_u32_le(&buf, row_index_start + 8);
2013        let row3_offset = read_u32_le(&buf, row_index_start + 12);
2014        assert_eq!(row3_num, 3);
2015        assert_ne!(row3_offset, EMPTY_ROW_OFFSET);
2016    }
2017
2018    #[test]
2019    fn test_string_deduplication() {
2020        let sst = SharedStringTable::new();
2021        let ws = make_worksheet(vec![make_row(
2022            1,
2023            vec![
2024                make_cell("A1", 1, CellTypeTag::Error, Some("#N/A")),
2025                make_cell("B1", 2, CellTypeTag::Error, Some("#N/A")),
2026            ],
2027        )]);
2028        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
2029
2030        let (st_start, _, _, _) = parse_sections(&buf);
2031        let string_count = read_u32_le(&buf, st_start) as usize;
2032        assert_eq!(
2033            string_count, 1,
2034            "duplicate error strings should be deduplicated"
2035        );
2036        let s = read_string(&buf, st_start, 0);
2037        assert_eq!(s, "#N/A");
2038    }
2039
2040    #[test]
2041    fn test_formula_string_type() {
2042        let sst = SharedStringTable::new();
2043        let ws = make_worksheet(vec![make_row(
2044            1,
2045            vec![make_cell(
2046                "A1",
2047                1,
2048                CellTypeTag::FormulaString,
2049                Some("computed"),
2050            )],
2051        )]);
2052        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
2053
2054        let (_, _, cd_start, flags) = parse_sections(&buf);
2055        let is_sparse = flags & FLAG_SPARSE != 0;
2056
2057        if is_sparse {
2058            let cells = read_sparse_row(&buf, cd_start);
2059            assert_eq!(cells[0].1, TYPE_STRING);
2060        } else {
2061            let (tag, _) = read_cell_at(&buf, cd_start, false, 0);
2062            assert_eq!(tag, TYPE_STRING);
2063        }
2064    }
2065
2066    #[test]
2067    fn test_number_with_explicit_type() {
2068        let sst = SharedStringTable::new();
2069        let ws = make_worksheet(vec![make_row(
2070            1,
2071            vec![make_cell("A1", 1, CellTypeTag::Number, Some("99.9"))],
2072        )]);
2073        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
2074
2075        let (_, _, cd_start, flags) = parse_sections(&buf);
2076        let is_sparse = flags & FLAG_SPARSE != 0;
2077
2078        if is_sparse {
2079            let cells = read_sparse_row(&buf, cd_start);
2080            assert_eq!(cells[0].1, TYPE_NUMBER);
2081            let val = f64::from_le_bytes(cells[0].2.try_into().unwrap());
2082            assert!((val - 99.9).abs() < f64::EPSILON);
2083        } else {
2084            let (tag, payload) = read_cell_at(&buf, cd_start, false, 0);
2085            assert_eq!(tag, TYPE_NUMBER);
2086            let val = f64::from_le_bytes(payload.try_into().unwrap());
2087            assert!((val - 99.9).abs() < f64::EPSILON);
2088        }
2089    }
2090
2091    #[test]
2092    fn test_cell_without_col_uses_ref_parsing() {
2093        let sst = SharedStringTable::new();
2094        let mut cell = make_cell("C5", 0, CellTypeTag::None, Some("42"));
2095        cell.col = 0;
2096        let ws = make_worksheet(vec![make_row(5, vec![cell])]);
2097        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
2098
2099        let row_count = read_u32_le(&buf, 6);
2100        assert_eq!(row_count, 1);
2101        let col_count = read_u16_le(&buf, 10);
2102        assert_eq!(col_count, 1);
2103    }
2104
2105    #[test]
2106    fn test_rich_string_from_sst() {
2107        use crate::rich_text::RichTextRun;
2108
2109        let mut sst = SharedStringTable::new();
2110        sst.add("plain");
2111        sst.add_rich_text(&[
2112            RichTextRun {
2113                text: "Bold".to_string(),
2114                font: None,
2115                size: None,
2116                bold: true,
2117                italic: false,
2118                color: None,
2119            },
2120            RichTextRun {
2121                text: " Normal".to_string(),
2122                font: None,
2123                size: None,
2124                bold: false,
2125                italic: false,
2126                color: None,
2127            },
2128        ]);
2129
2130        let ws = make_worksheet(vec![make_row(
2131            1,
2132            vec![make_cell("A1", 1, CellTypeTag::SharedString, Some("1"))],
2133        )]);
2134        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
2135
2136        let (st_start, _, cd_start, flags) = parse_sections(&buf);
2137        let is_sparse = flags & FLAG_SPARSE != 0;
2138
2139        let (type_tag, str_idx) = if is_sparse {
2140            let cells = read_sparse_row(&buf, cd_start);
2141            let idx = u32::from_le_bytes(cells[0].2[..4].try_into().unwrap()) as usize;
2142            (cells[0].1, idx)
2143        } else {
2144            let (tag, payload) = read_cell_at(&buf, cd_start, false, 0);
2145            let idx = u32::from_le_bytes(payload[..4].try_into().unwrap()) as usize;
2146            (tag, idx)
2147        };
2148
2149        assert_eq!(type_tag, TYPE_RICH_STRING);
2150        let text = read_string(&buf, st_start, str_idx);
2151        assert_eq!(text, "Bold Normal");
2152    }
2153
2154    fn with_formula(mut cell: Cell, t: Option<&str>, si: Option<u32>, value: Option<&str>) -> Cell {
2155        cell.f = Some(Box::new(CellFormula {
2156            t: t.map(str::to_string),
2157            reference: None,
2158            si,
2159            value: value.map(str::to_string),
2160        }));
2161        cell
2162    }
2163
2164    fn formula_cells_sheet() -> WorksheetXml {
2165        make_worksheet(vec![
2166            make_row(
2167                1,
2168                vec![
2169                    with_formula(
2170                        make_cell("A1", 1, CellTypeTag::FormulaString, Some("xy")),
2171                        None,
2172                        None,
2173                        Some("C3&\"y\""),
2174                    ),
2175                    with_formula(
2176                        make_cell("B1", 2, CellTypeTag::Boolean, Some("1")),
2177                        None,
2178                        None,
2179                        Some("TRUE()"),
2180                    ),
2181                    with_formula(
2182                        make_cell("C1", 3, CellTypeTag::Error, Some("#DIV/0!")),
2183                        None,
2184                        None,
2185                        Some("1/0"),
2186                    ),
2187                    with_formula(
2188                        make_cell("D1", 4, CellTypeTag::None, Some("3")),
2189                        None,
2190                        None,
2191                        Some("1+2"),
2192                    ),
2193                    with_formula(
2194                        make_cell("E1", 5, CellTypeTag::None, None),
2195                        None,
2196                        None,
2197                        Some("1+1"),
2198                    ),
2199                ],
2200            ),
2201            make_row(
2202                2,
2203                vec![with_formula(
2204                    make_cell("A2", 1, CellTypeTag::None, Some("2")),
2205                    Some("shared"),
2206                    Some(4),
2207                    Some("D1-1"),
2208                )],
2209            ),
2210            make_row(
2211                3,
2212                vec![
2213                    with_formula(
2214                        make_cell("A3", 1, CellTypeTag::None, Some("2")),
2215                        Some("shared"),
2216                        Some(4),
2217                        None,
2218                    ),
2219                    with_formula(
2220                        make_cell("B3", 2, CellTypeTag::None, Some("9")),
2221                        Some("shared"),
2222                        Some(8),
2223                        None,
2224                    ),
2225                    make_cell("C3", 3, CellTypeTag::None, Some("5")),
2226                ],
2227            ),
2228        ])
2229    }
2230
2231    #[test]
2232    fn sheet_formula_cells_report_encoded_expressions_with_cached_results() {
2233        let ws = formula_cells_sheet();
2234        let sst = SharedStringTable::new();
2235        let cells = sheet_formula_cells(&ws, &sst, &[], TraversalOptions::default(), 0).unwrap();
2236        let formula = |row: u32, col: u32, expr: &str, result: Option<CellValue>| FormulaCell {
2237            row,
2238            col,
2239            value: CellValue::Formula {
2240                expr: expr.to_string(),
2241                result: result.map(Box::new),
2242            },
2243        };
2244        assert_eq!(
2245            cells,
2246            vec![
2247                formula(1, 1, "C3&\"y\"", Some(CellValue::String("xy".to_string()))),
2248                formula(1, 2, "TRUE()", Some(CellValue::Bool(true))),
2249                formula(1, 3, "1/0", Some(CellValue::Error("#DIV/0!".to_string()))),
2250                formula(1, 4, "1+2", Some(CellValue::Number(3.0))),
2251                formula(1, 5, "1+1", None),
2252                formula(2, 1, "D1-1", Some(CellValue::Number(2.0))),
2253                formula(3, 1, "D2-1", Some(CellValue::Number(2.0))),
2254            ]
2255        );
2256
2257        // Every formula record in the encoded buffer appears with the same expression.
2258        let buf = sheet_to_raw_buffer(&ws, &sst).unwrap();
2259        let (st_start, _, cd_start, flags) = parse_sections(&buf);
2260        let min_col = flags >> 16;
2261        let mut encoded = Vec::new();
2262        for index in 0..read_u32_le(&buf, 6) as usize {
2263            let row = read_u32_le(&buf, HEADER_SIZE + index * 8);
2264            let offset = read_u32_le(&buf, HEADER_SIZE + index * 8 + 4) as usize;
2265            for (col, tag, payload) in read_sparse_row(&buf, cd_start + offset) {
2266                if tag == TYPE_FORMULA {
2267                    let idx = u32::from_le_bytes(payload[..4].try_into().unwrap()) as usize;
2268                    encoded.push((
2269                        row,
2270                        u32::from(col) + min_col,
2271                        read_string(&buf, st_start, idx),
2272                    ));
2273                }
2274            }
2275        }
2276        let reported: Vec<(u32, u32, String)> = cells
2277            .iter()
2278            .map(|cell| match &cell.value {
2279                CellValue::Formula { expr, .. } => (cell.row, cell.col, expr.clone()),
2280                other => panic!("expected formula, got {other:?}"),
2281            })
2282            .collect();
2283        assert_eq!(reported, encoded);
2284    }
2285
2286    #[test]
2287    fn sheet_formula_cells_share_the_traversal_limits_of_the_buffer() {
2288        let ws = formula_cells_sheet();
2289        let sst = SharedStringTable::new();
2290        let limits = TraversalLimits::new(3, 5, 9, 4096).unwrap();
2291        let options = TraversalOptions::new(TraversalMode::Sparse).with_limits(limits);
2292        assert_eq!(
2293            sheet_formula_cells(&ws, &sst, &[], options, 0)
2294                .unwrap()
2295                .len(),
2296            7
2297        );
2298
2299        let output_error = sheet_formula_cells(&ws, &sst, &[], options, 4096).unwrap_err();
2300        let Error::ResourceLimitExceeded(output_metadata) = output_error else {
2301            panic!("expected resource limit error");
2302        };
2303        assert_eq!(output_metadata.dimension(), ResourceDimension::OutputBytes);
2304
2305        // Dense mode admits the spanned rectangle (3 x 5) exactly like the dense buffer.
2306        let dense = TraversalOptions::new(TraversalMode::Dense).with_limits(limits);
2307        assert!(sheet_to_raw_buffer_with_options(&ws, &sst, dense).is_err());
2308        assert!(sheet_formula_cells(&ws, &sst, &[], dense, 0).is_err());
2309        let dense = TraversalOptions::new(TraversalMode::Dense)
2310            .with_limits(TraversalLimits::new(3, 5, 15, 4096).unwrap());
2311        assert_eq!(
2312            sheet_formula_cells(&ws, &sst, &[], dense, 0).unwrap().len(),
2313            7
2314        );
2315
2316        let cell_limits = TraversalLimits::new(3, 5, 8, 4096).unwrap();
2317        let cell_error = sheet_formula_cells(
2318            &ws,
2319            &sst,
2320            &[],
2321            TraversalOptions::new(TraversalMode::Sparse).with_limits(cell_limits),
2322            0,
2323        )
2324        .unwrap_err();
2325        let Error::ResourceLimitExceeded(cell_metadata) = cell_error else {
2326            panic!("expected resource limit error");
2327        };
2328        assert_eq!(cell_metadata.dimension(), ResourceDimension::CellCount);
2329    }
2330}