calamine/

xls.rs

// SPDX-License-Identifier: MIT
//
// Copyright 2016-2026, Johann Tuffe.

use std::cmp::min;
use std::collections::BTreeMap;
use std::fmt::{self, Write};
use std::io::{Read, Seek, SeekFrom};

use log::debug;

use crate::cfb::{Cfb, XlsEncoding};
use crate::formats::{
    builtin_format_by_code, detect_custom_number_format, format_excel_f64, format_excel_i64,
    CellFormat,
};
#[cfg(feature = "picture")]
use crate::utils::read_usize;
use crate::utils::{push_column, read_f64, read_i16, read_i32, read_u16, read_u32};
use crate::vba::VbaProject;
use crate::{
    Cell, CellErrorType, Data, Dimensions, HeaderRow, Metadata, Range, Reader, Sheet, SheetType,
    SheetVisible,
};

#[derive(Debug)]
/// An enum to handle Xls specific errors
pub enum XlsError {
    /// Io error
    Io(std::io::Error),
    /// Cfb error
    Cfb(crate::cfb::CfbError),
    /// Vba error
    Vba(crate::vba::VbaError),

    /// Cannot parse formula, stack is too short
    StackLen,
    /// Unrecognized data
    Unrecognized {
        /// data type
        typ: &'static str,
        /// value found
        val: u8,
    },
    /// Workbook is password protected
    Password,
    /// Invalid length
    Len {
        /// expected length
        expected: usize,
        /// found length
        found: usize,
        /// length type
        typ: &'static str,
    },
    /// Continue Record is too short
    ContinueRecordTooShort,
    /// End of stream
    EoStream(&'static str),

    /// Invalid Formula
    InvalidFormula {
        /// stack size
        stack_size: usize,
    },
    /// Invalid or unknown iftab
    IfTab(usize),
    /// Invalid etpg
    Etpg(u8),
    /// No vba project
    NoVba,

    /// Invalid OfficeArt Record.
    #[cfg(feature = "picture")]
    #[cfg_attr(docsrs, doc(cfg(feature = "picture")))]
    Art(&'static str),

    /// Worksheet not found
    WorksheetNotFound(String),
    /// Invalid iFmt value
    InvalidFormat {
        /// iFmt value, See 2.4.126 Format
        ifmt: u16,
    },
}

from_err!(std::io::Error, XlsError, Io);
from_err!(crate::cfb::CfbError, XlsError, Cfb);
from_err!(crate::vba::VbaError, XlsError, Vba);

impl std::fmt::Display for XlsError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            XlsError::Io(e) => write!(f, "I/O error: {e}"),
            XlsError::Cfb(e) => write!(f, "Cfb error: {e}"),
            XlsError::Vba(e) => write!(f, "Vba error: {e}"),
            XlsError::StackLen => write!(f, "Invalid stack length"),
            XlsError::Unrecognized { typ, val } => write!(f, "Unrecognized {typ}: 0x{val:0X}"),
            XlsError::Password => write!(f, "Workbook is password protected"),
            XlsError::Len {
                expected,
                found,
                typ,
            } => write!(
                f,
                "Invalid {typ} length, expected at least {expected}, found {found}",
            ),
            XlsError::ContinueRecordTooShort => write!(
                f,
                "Continued record too short while reading extended string"
            ),
            XlsError::EoStream(s) => write!(f, "End of stream '{s}'"),
            XlsError::InvalidFormula { stack_size } => {
                write!(f, "Invalid formula (stack size: {stack_size})")
            }
            XlsError::IfTab(iftab) => write!(f, "Invalid iftab {iftab:X}"),
            XlsError::Etpg(etpg) => write!(f, "Invalid etpg {etpg:X}"),
            XlsError::NoVba => write!(f, "No VBA project"),
            #[cfg(feature = "picture")]
            XlsError::Art(s) => write!(f, "Invalid art record '{s}'"),
            XlsError::WorksheetNotFound(name) => write!(f, "Worksheet '{name}' not found"),
            XlsError::InvalidFormat { ifmt } => write!(f, "Invalid ifmt value: '{ifmt}'"),
        }
    }
}

impl std::error::Error for XlsError {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        match self {
            XlsError::Io(e) => Some(e),
            XlsError::Cfb(e) => Some(e),
            XlsError::Vba(e) => Some(e),
            _ => None,
        }
    }
}

/// Options to perform specialized parsing.
#[derive(Debug, Clone, Default)]
#[non_exhaustive]
pub struct XlsOptions {
    /// Force a spreadsheet to be interpreted using a particular code page.
    ///
    /// XLS files can contain [code page] identifiers. If this identifier is missing or incorrect,
    /// strings in the parsed spreadsheet may be decoded incorrectly. Setting this field causes
    /// `calamine::Xls` to interpret strings using the specified code page, which may allow such
    /// spreadsheets to be decoded properly.
    ///
    /// [code page]: https://docs.microsoft.com/en-us/windows/win32/intl/code-page-identifiers
    pub force_codepage: Option<u16>,
    /// Row to use as header
    pub header_row: HeaderRow,
}

struct SheetData {
    range: Range<Data>,
    formula: Range<String>,
    merge_cells: Vec<Dimensions>,
}

/// A struct representing an old xls format file (CFB)
pub struct Xls<RS> {
    sheets: BTreeMap<String, SheetData>,
    metadata: Metadata,
    cfb: Cfb,
    reader: RS,
    options: XlsOptions,
    formats: Vec<CellFormat>,
    is_1904: bool,
    #[cfg(feature = "picture")]
    pictures: Option<Vec<(String, Vec<u8>)>>,
}

fn cfb<RS: Seek + Read>(reader: &mut RS) -> Result<Cfb, XlsError> {
    let offset_end = reader.seek(SeekFrom::End(0))? as usize;
    reader.seek(SeekFrom::Start(0))?;
    let cfb = Cfb::new(reader, offset_end)?;
    Ok(cfb)
}

impl<RS: Read + Seek> Xls<RS> {
    /// Creates a new instance using `Options` to inform parsing.
    ///
    /// ```
    /// use calamine::{Xls,XlsOptions};
    /// # use std::io::Cursor;
    /// # const BYTES: &[u8] = b"";
    ///
    /// # fn run() -> Result<Xls<Cursor<&'static [u8]>>, calamine::XlsError> {
    /// # let reader = std::io::Cursor::new(BYTES);
    /// let mut options = XlsOptions::default();
    /// // ...set options...
    /// let workbook = Xls::new_with_options(reader, options)?;
    /// # Ok(workbook) }
    /// # fn main() { assert!(run().is_err()); }
    /// ```
    pub fn new_with_options(mut reader: RS, options: XlsOptions) -> Result<Self, XlsError> {
        let cfb = cfb(&mut reader)?;

        debug!("cfb loaded");

        let mut xls = Xls {
            sheets: BTreeMap::new(),
            cfb,
            reader,
            metadata: Metadata::default(),
            options,
            is_1904: false,
            formats: Vec::new(),
            #[cfg(feature = "picture")]
            pictures: None,
        };

        xls.parse_workbook()?;

        debug!("xls parsed");

        Ok(xls)
    }

    /// Gets the worksheet merge cell dimensions
    #[doc(hidden)]
    #[deprecated(
        since = "0.36.0",
        note = "use `merge_cells_by_sheet_name()` or `merge_cells_by_sheet_id()` instead"
    )]
    pub fn worksheet_merge_cells(&self, name: &str) -> Option<Vec<Dimensions>> {
        self.sheets.get(name).map(|r| r.merge_cells.clone())
    }

    /// Get the nth worksheet. Shortcut for getting the nth
    /// sheet name, then the corresponding worksheet.
    #[doc(hidden)]
    #[deprecated(
        since = "0.36.0",
        note = "use `merge_cells_by_sheet_name()` or `merge_cells_by_sheet_id()` instead"
    )]
    pub fn worksheet_merge_cells_at(&self, n: usize) -> Option<Vec<Dimensions>> {
        let sheet = self.metadata().sheets.get(n)?;

        #[allow(deprecated)]
        self.worksheet_merge_cells(&sheet.name)
    }

    /// Get the merged cells/regions in a worksheet by sheet name.
    ///
    /// Merged cells in Excel are a range of cells that have been merged to act
    /// as a single cell. It is often used to create headers or titles that span
    /// multiple columns or rows.
    ///
    /// The function returns a vector of [`Dimensions`] for the merged cells in
    /// the named worksheet.
    ///
    /// Note: unlike the equivalent [`crate::Xlsx`] method, this method takes
    /// `&self` because XLS data is fully parsed at construction time and held
    /// in memory.
    ///
    /// # Parameters
    ///
    /// - `name`: The name of the worksheet.
    ///
    /// # Errors
    ///
    /// - [`XlsError::WorksheetNotFound`] if no worksheet with the given name
    ///   exists.
    ///
    /// # Examples
    ///
    /// ```
    /// use calamine::{open_workbook, Error, Reader, Xls};
    ///
    /// fn main() -> Result<(), Error> {
    ///     let path = "tests/merge_cells.xls";
    ///
    ///     // Open the workbook.
    ///     let workbook: Xls<_> = open_workbook(path)?;
    ///
    ///     // Get the names of all the sheets in the workbook.
    ///     let sheet_names = workbook.sheet_names();
    ///
    ///     for sheet_name in &sheet_names {
    ///         println!("{sheet_name}:");
    ///
    ///         // Get the merged cells in the current sheet.
    ///         let merge_cells = workbook.merge_cells_by_sheet_name(sheet_name)?;
    ///
    ///         // Print the dimensions of each merged region.
    ///         for dimension in &merge_cells {
    ///             println!("    {dimension:?}");
    ///         }
    ///     }
    ///
    ///     Ok(())
    /// }
    /// ```
    ///
    /// Output:
    ///
    /// ```text
    /// Dimensions { start: (0, 0), end: (0, 1) }
    /// Dimensions { start: (1, 0), end: (3, 0) }
    /// Dimensions { start: (1, 1), end: (3, 3) }
    /// ```
    ///
    pub fn merge_cells_by_sheet_name(&self, name: &str) -> Result<Vec<Dimensions>, XlsError> {
        self.sheets
            .get(name)
            .map(|r| r.merge_cells.clone())
            .ok_or_else(|| XlsError::WorksheetNotFound(name.into()))
    }

    /// Get the merged cells/regions in a worksheet by sheet index.
    ///
    /// Merged cells in Excel are a range of cells that have been merged to act
    /// as a single cell. It is often used to create headers or titles that span
    /// multiple columns or rows.
    ///
    /// The function returns a vector of [`Dimensions`] for the merged cells in
    /// the worksheet at the given index.
    ///
    /// Note: unlike the equivalent [`crate::Xlsx`] method, this method takes
    /// `&self` because XLS data is fully parsed at construction time and held
    /// in memory.
    ///
    /// # Parameters
    ///
    /// - `id`: The zero-based index of the worksheet.
    ///
    /// # Errors
    ///
    /// - [`XlsError::WorksheetNotFound`] if `id` is out of range.
    ///
    /// # Examples
    ///
    /// ```
    /// use calamine::{open_workbook, Error, Xls};
    ///
    /// fn main() -> Result<(), Error> {
    ///     let path = "tests/merge_cells.xls";
    ///
    ///     // Open the workbook.
    ///     let workbook: Xls<_> = open_workbook(path)?;
    ///
    ///     // Get the merged cells in the first worksheet.
    ///     let merge_cells = workbook.merge_cells_by_sheet_id(0)?;
    ///
    ///     // Print the dimensions of each merged region.
    ///     for dimension in &merge_cells {
    ///         println!("{dimension:?}");
    ///     }
    ///
    ///     Ok(())
    /// }
    /// ```
    ///
    /// Output:
    ///
    /// ```text
    /// Dimensions { start: (0, 0), end: (0, 1) }
    /// Dimensions { start: (1, 0), end: (3, 0) }
    /// Dimensions { start: (1, 1), end: (3, 3) }
    /// ```
    ///
    pub fn merge_cells_by_sheet_id(&self, id: usize) -> Result<Vec<Dimensions>, XlsError> {
        let name = self
            .metadata()
            .sheets
            .get(id)
            .map(|sheet| sheet.name.clone())
            .ok_or_else(|| XlsError::WorksheetNotFound(format!("Sheet index {id} out of range")))?;

        self.merge_cells_by_sheet_name(&name)
    }

    /// Check if the workbook uses the 1904 date system.
    ///
    /// Returns `true` if the workbook uses the 1904 date epoch (used by some older
    /// Mac versions of Excel), or `false` if it uses the standard 1900 date epoch.
    ///
    /// # Examples
    ///
    /// ```
    /// use calamine::{open_workbook, Error, Xls};
    ///
    /// fn main() -> Result<(), Error> {
    ///     let workbook: Xls<_> = open_workbook("tests/date_1904.xls")?;
    ///     let is_1904 = workbook.has_1904_epoch();
    ///     println!("Uses 1904 date system: {}", is_1904);
    ///     Ok(())
    /// }
    /// ```
    pub fn has_1904_epoch(&self) -> bool {
        self.is_1904
    }
}

impl<RS: Read + Seek> Reader<RS> for Xls<RS> {
    type Error = XlsError;

    fn new(reader: RS) -> Result<Self, XlsError> {
        Self::new_with_options(reader, XlsOptions::default())
    }

    fn with_header_row(&mut self, header_row: HeaderRow) -> &mut Self {
        self.options.header_row = header_row;
        self
    }

    fn vba_project(&mut self) -> Result<Option<VbaProject>, XlsError> {
        // Reads vba once for all (better than reading all worksheets once for all)
        if !self.cfb.has_directory("_VBA_PROJECT_CUR") {
            return Ok(None);
        }
        let vba = VbaProject::from_cfb(&mut self.reader, &mut self.cfb)?;
        Ok(Some(vba))
    }

    /// Parses Workbook stream, no need for the relationships variable
    fn metadata(&self) -> &Metadata {
        &self.metadata
    }

    fn worksheet_range(&mut self, name: &str) -> Result<Range<Data>, XlsError> {
        let sheet = self
            .sheets
            .get(name)
            .map(|r| r.range.clone())
            .ok_or_else(|| XlsError::WorksheetNotFound(name.into()))?;

        match self.options.header_row {
            HeaderRow::FirstNonEmptyRow => Ok(sheet),
            HeaderRow::Row(header_row_idx) => {
                // If `header_row` is a row index, adjust the range
                if let (Some(start), Some(end)) = (sheet.start(), sheet.end()) {
                    Ok(sheet.range((header_row_idx, start.1), end))
                } else {
                    Ok(sheet)
                }
            }
        }
    }

    fn worksheets(&mut self) -> Vec<(String, Range<Data>)> {
        self.sheets
            .iter()
            .map(|(name, sheet)| (name.to_owned(), sheet.range.clone()))
            .collect()
    }

    fn worksheet_formula(&mut self, name: &str) -> Result<Range<String>, XlsError> {
        self.sheets
            .get(name)
            .ok_or_else(|| XlsError::WorksheetNotFound(name.into()))
            .map(|r| r.formula.clone())
    }

    #[cfg(feature = "picture")]
    fn pictures(&self) -> Option<Vec<(String, Vec<u8>)>> {
        self.pictures.to_owned()
    }
}

#[derive(Debug, Clone, Copy)]
struct Xti {
    _isup_book: u16,
    itab_first: i16,
    _itab_last: i16,
}

impl<RS: Read + Seek> Xls<RS> {
    fn parse_workbook(&mut self) -> Result<(), XlsError> {
        use super::cfb::CfbError::StreamNotFound;
        // gets workbook and worksheets stream, or early exit
        let stream = match self
            .cfb
            .get_stream("Workbook", &mut self.reader)
            .or_else(|_| self.cfb.get_stream("Book", &mut self.reader))
            .or_else(|_| self.cfb.get_stream("WORKBOOK", &mut self.reader))
            .or_else(|_| self.cfb.get_stream("BOOK", &mut self.reader))
        {
            Ok(s) => s,
            Err(StreamNotFound(_)) => return Err(StreamNotFound("Workbook".to_string()).into()),
            Err(e) => return Err(e.into()),
        };

        let mut sheet_names = Vec::new();
        let mut strings = Vec::new();
        let mut defined_names = Vec::new();
        let mut xtis = Vec::new();
        let mut formats = BTreeMap::new();
        let mut xfs = Vec::new();
        let mut biff = Biff::Biff8; // Binary Interchange File Format (BIFF) version
        let codepage = self.options.force_codepage.unwrap_or(1200);
        let mut encoding = XlsEncoding::from_codepage(codepage)?;
        #[cfg(feature = "picture")]
        let mut draw_group: Vec<u8> = Vec::new();
        {
            let wb = &stream;
            let records = RecordIter { stream: wb };
            for record in records {
                // Record docs/specs -
                // https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-xls/6fba0383-0d7a-4c7a-afe9-642ff70cbd36
                let mut r = record?;
                match r.typ {
                    // FilePass (MS-XLS 2.4.117)
                    0x002F if read_u16(r.data) != 0 => return Err(XlsError::Password),
                    // CodePage (MS-XLS 2.4.52)
                    0x0042 if self.options.force_codepage.is_none() => {
                        encoding = XlsEncoding::from_codepage(read_u16(r.data))?;
                    }
                    // RRTabId (MS-XLS 2.4.241)
                    0x013D => {
                        let sheet_len = r.data.len() / 2;
                        sheet_names.reserve(sheet_len);
                        self.metadata.sheets.reserve(sheet_len);
                    }
                    // DateMode (MS-XLS 2.4.77)
                    0x0022 if read_u16(r.data) == 1 => {
                        self.is_1904 = true;
                    }
                    // Format (MS-XLS 2.4.126)
                    0x041E => match parse_format(&mut r, &encoding, biff) {
                        Ok((idx, format)) => {
                            formats.insert(idx, format);
                        }
                        Err(e) => log::warn!("{e}"),
                    },
                    // XF (MS-XLS 2.4.353)
                    0x00E0 => {
                        xfs.push(parse_xf(&r)?);
                    }
                    // BoundSheet8 (MS-XLS 2.4.28)
                    0x0085 => {
                        let (pos, sheet) = parse_sheet_metadata(&mut r, &encoding, biff)?;
                        self.metadata.sheets.push(sheet.clone());
                        sheet_names.push((pos, sheet.name));
                    }
                    // BOF (MS-XLS 2.4.21)
                    0x0809 => {
                        let bof = parse_bof(&mut r)?;
                        biff = bof.biff;
                    }
                    // Lbl (MS-XLS 2.4.150)
                    0x0018 => defined_names.push(parse_lbl(&r, &encoding, biff)?),
                    // ExternSheet (MS-XLS 2.4.106)
                    0x0017 => xtis.extend(parse_extern_sheet(&r, biff)),
                    // SST (MS-XLS 2.4.265)
                    0x00FC => strings = parse_sst(&mut r, &encoding)?,
                    #[cfg(feature = "picture")]
                    // MsoDrawingGroup (MS-XLS 2.4.171)
                    0x00EB => {
                        draw_group.extend(r.data);
                        draw_group.extend(r.cont.iter().flat_map(|v| *v));
                    }
                    // EOF (MS-XLS 2.4.103)
                    0x000A => break,
                    _ => (),
                }
            }
        }

        // Before BIFF8, formula tokens embed sheet indices directly (itabFirst),
        // so create identity-mapped XTI entries to reuse the BIFF8 lookup code.
        if matches!(biff, Biff::Biff2 | Biff::Biff3 | Biff::Biff4 | Biff::Biff5) && xtis.is_empty()
        {
            xtis = (0..sheet_names.len())
                .map(|i| Xti {
                    _isup_book: 0,
                    itab_first: i as i16,
                    _itab_last: i as i16,
                })
                .collect();
        }
        self.formats = xfs
            .into_iter()
            .map(|fmt| match formats.get(&fmt) {
                Some(s) => *s,
                _ => builtin_format_by_code(fmt),
            })
            .collect();

        debug!("formats: {:?}", self.formats);

        let defined_names = defined_names
            .into_iter()
            .map(|(name, (i, mut f))| {
                if let Some(i) = i {
                    let sh = xtis
                        .get(i)
                        .and_then(|xti| sheet_names.get(xti.itab_first as usize))
                        .map_or("#REF", |sh| &sh.1);
                    f = format!("{sh}!{f}");
                }
                (name, f)
            })
            .collect::<Vec<_>>();

        debug!("defined_names: {defined_names:?}");

        let mut sheets = BTreeMap::new();
        let fmla_sheet_names = sheet_names
            .iter()
            .map(|(_, n)| n.clone())
            .collect::<Vec<_>>();
        for (pos, name) in sheet_names {
            let sh = &stream[pos..];
            let records = RecordIter { stream: sh };
            let mut cells = Vec::new();
            let mut formulas = Vec::new();
            let mut fmla_pos = (0, 0);
            let mut merge_cells = Vec::new();
            // Nested substreams (embedded charts) carry cell-like records; skip them.
            // The first BOF belongs to the worksheet itself.
            let mut seen_sheet_bof = false;
            let mut substream_depth = 0usize;
            for record in records {
                let r = record?;
                if substream_depth > 0 {
                    match r.typ {
                        0x0809 => substream_depth += 1,
                        0x000A => substream_depth -= 1,
                        _ => (),
                    }
                    continue;
                }
                match r.typ {
                    // BOF of a nested substream (embedded chart, macro sheet, ...)
                    0x0809 => {
                        if seen_sheet_bof {
                            substream_depth += 1;
                        } else {
                            seen_sheet_bof = true;
                        }
                    }
                    // 512: Dimensions
                    0x0200 => {
                        let Dimensions { start, end } = parse_dimensions(r.data)?;
                        let rows = (end.0 - start.0 + 1) as usize;
                        let cols = (end.1 - start.1 + 1) as usize;
                        cells.reserve(rows.saturating_mul(cols));
                    }
                    //0x0201 => cells.push(parse_blank(r.data)?), // 513: Blank
                    0x0203 => cells.push(parse_number(r.data, &self.formats, self.is_1904)?), // 515: Number
                    0x0204 => cells.push(parse_label(r.data, &encoding, biff)?), // 516: Label [MS-XLS 2.4.148]
                    0x00D6 => cells.push(parse_label(r.data, &encoding, biff)?), // RString
                    0x0205 => cells.push(parse_bool_err(r.data)?),               // 517: BoolErr
                    0x0207 => {
                        // 519 String (formula value)
                        let val = Data::String(parse_string(r.data, &encoding, biff)?);
                        cells.push(Cell::new(fmla_pos, val));
                    }
                    0x027E => cells.push(parse_rk(r.data, &self.formats, self.is_1904)?), // 638: Rk
                    0x00FD => cells.extend(parse_label_sst(r.data, &strings)?), // LabelSst
                    0x00BD => parse_mul_rk(r.data, &mut cells, &self.formats, self.is_1904)?, // 189: MulRk
                    0x00E5 => parse_merge_cells(r.data, &mut merge_cells)?, // 229: Merge Cells
                    0x000A => break,                                        // 10: EOF,
                    0x0006 => {
                        // 6: Formula
                        if r.data.len() < 20 {
                            return Err(XlsError::Len {
                                expected: 20,
                                found: r.data.len(),
                                typ: "Formula",
                            });
                        }
                        let row = read_u16(r.data);
                        let col = read_u16(&r.data[2..]);
                        let format = self.formats.get(read_u16(&r.data[4..]) as usize);
                        fmla_pos = (row as u32, col as u32);
                        if let Some(val) =
                            parse_formula_value(&r.data[6..14], format, self.is_1904)?
                        {
                            // If the value is a string
                            // it will appear in 0x0207 record coming next
                            cells.push(Cell::new(fmla_pos, val));
                        }
                        let fmla = parse_formula(
                            &r.data[20..],
                            &fmla_sheet_names,
                            &defined_names,
                            &xtis,
                            &encoding,
                            biff,
                        )
                        .unwrap_or_else(|e| {
                            debug!("{e}");
                            format!(
                                "Unrecognised formula \
                                 for cell ({row}, {col}): {e:?}"
                            )
                        });
                        formulas.push(Cell::new(fmla_pos, fmla));
                    }
                    _ => (),
                }
            }
            let range = Range::from_sparse(cells);
            let formula = Range::from_sparse(formulas);
            sheets.insert(
                name,
                SheetData {
                    range,
                    formula,
                    merge_cells,
                },
            );
        }

        self.sheets = sheets;
        self.metadata.names = defined_names;

        #[cfg(feature = "picture")]
        if !draw_group.is_empty() {
            let pics = parse_pictures(&draw_group)?;
            if !pics.is_empty() {
                self.pictures = Some(pics);
            }
        }

        Ok(())
    }
}

/// <https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-xls/4d6a3d1e-d7c5-405f-bbae-d01e9cb79366>
struct Bof {
    /// Binary Interchange File Format
    biff: Biff,
}

/// <https://www.loc.gov/preservation/digital/formats/fdd/fdd000510.shtml#notes>
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Biff {
    Biff2,
    Biff3,
    Biff4,
    Biff5,
    Biff8,
    // Used by MS-XLSB Workbook(2.1.7.61) or Worksheet(2.1.7.61) which are not supported yet.
    // Biff12,
}

/// BOF [MS-XLS] 2.4.21
fn parse_bof(r: &mut Record<'_>) -> Result<Bof, XlsError> {
    let mut dt = 0;
    let biff_version = read_u16(&r.data[..2]);

    if r.data.len() >= 4 {
        dt = read_u16(&r.data[2..]);
    }

    let biff = match biff_version {
        0x0200 | 0x0002 | 0x0007 => Biff::Biff2,
        0x0300 => Biff::Biff3,
        0x0400 => Biff::Biff4,
        0x0500 => Biff::Biff5,
        0x0600 => Biff::Biff8,
        0 => {
            if dt == 0x1000 {
                Biff::Biff5
            } else {
                Biff::Biff8
            }
        }
        _ => Biff::Biff8,
    };

    Ok(Bof { biff })
}

/// `BoundSheet8` [MS-XLS 2.4.28]
fn parse_sheet_metadata(
    r: &mut Record<'_>,
    encoding: &XlsEncoding,
    biff: Biff,
) -> Result<(usize, Sheet), XlsError> {
    let pos = read_u32(r.data) as usize;
    let visible = match r.data[4] & 0b0011_1111 {
        0x00 => SheetVisible::Visible,
        0x01 => SheetVisible::Hidden,
        0x02 => SheetVisible::VeryHidden,
        e => {
            return Err(XlsError::Unrecognized {
                typ: "BoundSheet8:hsState",
                val: e,
            });
        }
    };
    let typ = match r.data[5] {
        0x00 => SheetType::WorkSheet,
        0x01 => SheetType::MacroSheet,
        0x02 => SheetType::ChartSheet,
        0x06 => SheetType::Vba,
        e => {
            return Err(XlsError::Unrecognized {
                typ: "BoundSheet8:dt",
                val: e,
            });
        }
    };
    r.data = &r.data[6..];
    let mut name = parse_short_string(r, encoding, biff)?;
    name.retain(|c| c != '\0');
    Ok((pos, Sheet { name, typ, visible }))
}

fn parse_lbl(
    r: &Record<'_>,
    encoding: &XlsEncoding,
    biff: Biff,
) -> Result<(String, (Option<usize>, String)), XlsError> {
    let cch = r.data[3] as usize;
    let cce = read_u16(&r.data[4..]) as usize;
    let mut name = String::with_capacity(cch);
    match biff {
        Biff::Biff2 | Biff::Biff3 | Biff::Biff4 | Biff::Biff5 => {
            // BIFF5 and earlier: plain byte string, no flags byte
            encoding.decode_to(&r.data[14..], cch, &mut name, None);
        }
        Biff::Biff8 => {
            read_unicode_string_no_cch(encoding, &r.data[14..], cch, &mut name)?;
        }
    }
    let rgce = &r.data[r.data.len() - cce..];
    let formula = parse_defined_names(rgce, biff)?;
    Ok((name, formula))
}

fn parse_extern_sheet(r: &Record<'_>, biff: Biff) -> Vec<Xti> {
    match biff {
        Biff::Biff8 => {
            // Single record with cXTI count + array of 6-byte XTI structs
            let cxti = read_u16(r.data) as usize;
            r.data[2..]
                .as_chunks::<6>()
                .0
                .iter()
                .take(cxti)
                .map(|xti| Xti {
                    _isup_book: read_u16(&xti[..2]),
                    itab_first: read_i16(&xti[2..4]),
                    _itab_last: read_i16(&xti[4..]),
                })
                .collect()
        }
        // BIFF5 and earlier: individual sheet name references; formula
        // tokens embed sheet indices directly, so no XTI table needed.
        Biff::Biff2 | Biff::Biff3 | Biff::Biff4 | Biff::Biff5 => Vec::new(),
    }
}

fn parse_number(r: &[u8], formats: &[CellFormat], is_1904: bool) -> Result<Cell<Data>, XlsError> {
    if r.len() < 14 {
        return Err(XlsError::Len {
            typ: "number",
            expected: 14,
            found: r.len(),
        });
    }
    let row = read_u16(r) as u32;
    let col = read_u16(&r[2..]) as u32;
    let v = read_f64(&r[6..]);
    let format = formats.get(read_u16(&r[4..]) as usize);

    Ok(Cell::new((row, col), format_excel_f64(v, format, is_1904)))
}

fn parse_bool_err(r: &[u8]) -> Result<Cell<Data>, XlsError> {
    if r.len() < 8 {
        return Err(XlsError::Len {
            typ: "BoolErr",
            expected: 8,
            found: r.len(),
        });
    }
    let row = read_u16(r);
    let col = read_u16(&r[2..]);
    let pos = (row as u32, col as u32);
    match r[7] {
        0x00 => Ok(Cell::new(pos, Data::Bool(r[6] != 0))),
        0x01 => Ok(Cell::new(pos, parse_err(r[6])?)),
        e => Err(XlsError::Unrecognized {
            typ: "fError",
            val: e,
        }),
    }
}

fn parse_err(e: u8) -> Result<Data, XlsError> {
    match e {
        0x00 => Ok(Data::Error(CellErrorType::Null)),
        0x07 => Ok(Data::Error(CellErrorType::Div0)),
        0x0F => Ok(Data::Error(CellErrorType::Value)),
        0x17 => Ok(Data::Error(CellErrorType::Ref)),
        0x1D => Ok(Data::Error(CellErrorType::Name)),
        0x24 => Ok(Data::Error(CellErrorType::Num)),
        0x2A => Ok(Data::Error(CellErrorType::NA)),
        0x2B => Ok(Data::Error(CellErrorType::GettingData)),
        e => Err(XlsError::Unrecognized {
            typ: "error",
            val: e,
        }),
    }
}

fn parse_rk(r: &[u8], formats: &[CellFormat], is_1904: bool) -> Result<Cell<Data>, XlsError> {
    if r.len() < 10 {
        return Err(XlsError::Len {
            typ: "rk",
            expected: 10,
            found: r.len(),
        });
    }
    let row = read_u16(r);
    let col = read_u16(&r[2..]);

    Ok(Cell::new(
        (row as u32, col as u32),
        rk_num(&r[4..10], formats, is_1904),
    ))
}

fn parse_merge_cells(r: &[u8], merge_cells: &mut Vec<Dimensions>) -> Result<(), XlsError> {
    let count = read_u16(r);

    for i in 0..count {
        let offset: usize = (2 + i * 8).into();

        let rf = read_u16(&r[offset..]);
        let rl = read_u16(&r[offset + 2..]);
        let cf = read_u16(&r[offset + 4..]);
        let cl = read_u16(&r[offset + 6..]);

        merge_cells.push(Dimensions {
            start: (rf.into(), cf.into()),
            end: (rl.into(), cl.into()),
        });
    }

    Ok(())
}

fn parse_mul_rk(
    r: &[u8],
    cells: &mut Vec<Cell<Data>>,
    formats: &[CellFormat],
    is_1904: bool,
) -> Result<(), XlsError> {
    if r.len() < 6 {
        return Err(XlsError::Len {
            typ: "rk",
            expected: 6,
            found: r.len(),
        });
    }

    let row = read_u16(r);
    let col_first = read_u16(&r[2..]);
    let col_last = read_u16(&r[r.len() - 2..]);

    if r.len() != 6 + 6 * (col_last - col_first + 1) as usize {
        return Err(XlsError::Len {
            typ: "rk",
            expected: 6 + 6 * (col_last - col_first + 1) as usize,
            found: r.len(),
        });
    }

    for (col, rk) in (col_first as u32..).zip(r[4..r.len() - 2].chunks(6)) {
        cells.push(Cell::new((row as u32, col), rk_num(rk, formats, is_1904)));
    }
    Ok(())
}

fn rk_num(rk: &[u8], formats: &[CellFormat], is_1904: bool) -> Data {
    let d100 = (rk[2] & 1) != 0;
    let is_int = (rk[2] & 2) != 0;
    let format = formats.get(read_u16(rk) as usize);

    let mut v = [0u8; 8];
    v[4..].copy_from_slice(&rk[2..]);
    v[4] &= 0xFC;
    if is_int {
        let v = (read_i32(&v[4..8]) >> 2) as i64;
        if d100 && v % 100 != 0 {
            format_excel_f64(v as f64 / 100.0, format, is_1904)
        } else {
            format_excel_i64(if d100 { v / 100 } else { v }, format, is_1904)
        }
    } else {
        let v = read_f64(&v);
        format_excel_f64(if d100 { v / 100.0 } else { v }, format, is_1904)
    }
}

/// `ShortXLUnicodeString` [MS-XLS 2.5.240]
fn parse_short_string(
    r: &mut Record<'_>,
    encoding: &XlsEncoding,
    biff: Biff,
) -> Result<String, XlsError> {
    let biff8 = matches!(biff, Biff::Biff8);
    if r.data.is_empty() || r.data.len() < 2 && biff8 {
        return Err(XlsError::Len {
            typ: "short string",
            expected: if biff8 { 2 } else { 1 },
            found: r.data.len(),
        });
    }

    let cch = r.data[0] as usize;
    r.data = &r.data[1..];
    let mut high_byte = None;

    if biff8 {
        high_byte = Some(r.data[0] & 0x1 != 0);
        r.data = &r.data[1..];
    }

    let mut s = String::with_capacity(cch);
    encoding.decode_to(r.data, cch, &mut s, high_byte);
    Ok(s)
}

/// `XLUnicodeString` [MS-XLS 2.5.294]
fn parse_string(r: &[u8], encoding: &XlsEncoding, biff: Biff) -> Result<String, XlsError> {
    let (mut high_byte, expected) = match biff {
        Biff::Biff2 | Biff::Biff3 | Biff::Biff4 | Biff::Biff5 => (None, 2),
        Biff::Biff8 => (Some(false), 3),
    };
    if r.len() < expected {
        if 2 == r.len() && read_u16(r) == 0 {
            // tests/OOM_alloc2.xls
            return Ok(String::new());
        }
        return Err(XlsError::Len {
            typ: "string",
            expected,
            found: r.len(),
        });
    }
    // delay populating Some(_) variant until length checks guarantee r[2] can't crash
    high_byte = high_byte.map(|_| r[2] & 0x1 != 0);

    let cch = read_u16(r) as usize;
    let mut s = String::with_capacity(cch);
    encoding.decode_to(&r[expected..], cch, &mut s, high_byte);
    Ok(s)
}

fn parse_label(r: &[u8], encoding: &XlsEncoding, biff: Biff) -> Result<Cell<Data>, XlsError> {
    if r.len() < 6 {
        return Err(XlsError::Len {
            typ: "label",
            expected: 6,
            found: r.len(),
        });
    }
    let row = read_u16(r);
    let col = read_u16(&r[2..]);
    let _ixfe = read_u16(&r[4..]);
    Ok(Cell::new(
        (row as u32, col as u32),
        Data::String(parse_string(&r[6..], encoding, biff)?),
    ))
}

fn parse_label_sst(r: &[u8], strings: &[String]) -> Result<Option<Cell<Data>>, XlsError> {
    if r.len() < 10 {
        return Err(XlsError::Len {
            typ: "label sst",
            expected: 10,
            found: r.len(),
        });
    }
    let row = read_u16(r);
    let col = read_u16(&r[2..]);
    let i = read_u32(&r[6..]) as usize;
    if let Some(s) = strings.get(i) {
        return Ok(Some(Cell::new(
            (row as u32, col as u32),
            Data::String(s.clone()),
        )));
    }
    Ok(None)
}

fn parse_dimensions(r: &[u8]) -> Result<Dimensions, XlsError> {
    let (rf, rl, mut cf, cl) = match r.len() {
        10 => (
            read_u16(&r[0..2]) as u32,
            read_u16(&r[2..4]) as u32,
            read_u16(&r[4..6]) as u32,
            read_u16(&r[6..8]) as u32,
        ),
        // The BIFF8 record is 14 bytes but some writers add 2 more, which are
        // ignored.
        14 | 16 => (
            read_u32(&r[0..4]),
            read_u32(&r[4..8]),
            read_u16(&r[8..10]) as u32,
            read_u16(&r[10..12]) as u32,
        ),
        _ => {
            return Err(XlsError::Len {
                typ: "dimensions",
                expected: 14,
                found: r.len(),
            });
        }
    };
    // 2.5.53 ColU must be <= 0xFF, if larger, reasonable to assume
    // starts at 0
    // tests/OOM_alloc2.xls
    if 0xFF < cf || cl < cf {
        cf = 0;
    }
    if 1 <= rl && 1 <= cl {
        Ok(Dimensions {
            start: (rf, cf),
            end: (rl - 1, cl - 1),
        })
    } else {
        Ok(Dimensions {
            start: (rf, cf),
            end: (rf, cf),
        })
    }
}

// Parse the Excel xls Shared String Table (SST). See [MS-XLS] 2.4.265.
//
// https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-xls/b6231b92-d32e-4626-badd-c3310a672bab
fn parse_sst(r: &mut Record<'_>, encoding: &XlsEncoding) -> Result<Vec<String>, XlsError> {
    if r.data.len() < 8 {
        return Err(XlsError::Len {
            typ: "sst",
            expected: 8,
            found: r.data.len(),
        });
    }
    let mut sst = vec![];

    // Skip cstTotal and cstUnique headers in SST record.
    r.data = &r.data[8..];

    while !r.data.is_empty() || r.continue_record() {
        sst.push(read_rich_extended_string(r, encoding)?);
    }

    Ok(sst)
}

/// Decode XF (extract only ifmt - Format identifier)
///
/// See: <https://learn.microsoft.com/ru-ru/openspecs/office_file_formats/ms-xls/993d15c4-ec04-43e9-ba36-594dfb336c6d>
fn parse_xf(r: &Record<'_>) -> Result<u16, XlsError> {
    if r.data.len() < 4 {
        return Err(XlsError::Len {
            typ: "xf",
            expected: 4,
            found: r.data.len(),
        });
    }

    Ok(read_u16(&r.data[2..]))
}

/// Decode Format [MS-XLS 2.4.126]
///
/// See: <https://learn.microsoft.com/ru-ru/openspecs/office_file_formats/ms-xls/300280fd-e4fe-4675-a924-4d383af48d3b>
fn parse_format(
    r: &mut Record<'_>,
    encoding: &XlsEncoding,
    biff: Biff,
) -> Result<(u16, CellFormat), XlsError> {
    if r.data.len() < 2 {
        return Err(XlsError::Len {
            typ: "format",
            expected: 2,
            found: r.data.len(),
        });
    }
    let ifmt = read_u16(r.data);
    match ifmt {
        5..=8 | 23..=26 | 41..=44 | 63..=66 | 164..=382 => (),
        _ => return Err(XlsError::InvalidFormat { ifmt }),
    }

    let s = parse_string(&r.data[2..], encoding, biff)?;
    Ok((ifmt, detect_custom_number_format(&s)))
}

/// Decode `XLUnicodeRichExtendedString` [MS-XLS 2.5.293].
///
/// See: <https://docs.microsoft.com/en-us/openspecs/office_file_formats/ms-xls/173d9f51-e5d3-43da-8de2-be7f22e119b9>
fn read_rich_extended_string(
    r: &mut Record<'_>,
    encoding: &XlsEncoding,
) -> Result<String, XlsError> {
    if r.data.is_empty() {
        // spec violation: at very least cch and flags should be present
        return Ok(String::new());
    }
    if r.data.len() < 3 {
        return Err(XlsError::Len {
            typ: "rich extended string",
            expected: 3,
            found: r.data.len(),
        });
    }

    let cch = read_u16(r.data) as usize;
    let flags = r.data[2];

    r.data = &r.data[3..];

    let high_byte = flags & 0x1 != 0;

    // how many FormatRun in rgRun data block
    let mut c_run = 0;

    // how many bytes in ExtRst data block
    let mut cb_ext_rst = 0;

    // if flag fRichSt exists, read cRun and forward.
    if flags & 0x8 != 0 {
        c_run = read_u16(r.data) as usize;
        r.data = &r.data[2..];
    }

    // if flag fExtSt exists, read cbExtRst and forward.
    if flags & 0x4 != 0 {
        cb_ext_rst = read_i32(r.data) as usize;
        r.data = &r.data[4..];
    }

    // read rgb data block for the string we want
    let s = read_dbcs(encoding, cch, r, high_byte)?;

    // skip rgRun data block. Note: each FormatRun contain 4 bytes.
    r.skip(c_run * 4)?;

    // skip ExtRst data block.
    r.skip(cb_ext_rst)?;

    Ok(s)
}

fn read_dbcs(
    encoding: &XlsEncoding,
    mut len: usize,
    r: &mut Record<'_>,
    mut high_byte: bool,
) -> Result<String, XlsError> {
    let mut s = String::with_capacity(len);
    while len > 0 {
        let (l, at) = encoding.decode_to(r.data, len, &mut s, Some(high_byte));
        r.data = &r.data[at..];
        len -= l;
        if len > 0 {
            if r.continue_record() {
                high_byte = r.data[0] & 0x1 != 0;
                r.data = &r.data[1..];
            } else {
                return Err(XlsError::EoStream("dbcs"));
            }
        }
    }
    Ok(s)
}

/// Reads an `XLUnicodeStringNoCch` of `len` characters and
/// returns the number of bytes consumed.
///
/// The character data is 1 byte per character when `fHighByte` is 0, and
/// 2 bytes per character (UTF-16LE) when `fHighByte` is 1.
fn read_unicode_string_no_cch(
    encoding: &XlsEncoding,
    buf: &[u8],
    len: usize,
    s: &mut String,
) -> Result<usize, XlsError> {
    let Some(&flags) = buf.first() else {
        return Err(XlsError::Len {
            expected: 1,
            found: 0,
            typ: "XLUnicodeStringNoCch",
        });
    };
    let high_byte = flags & 0x1 != 0;
    let consumed = 1 + if high_byte { 2 * len } else { len };
    if buf.len() < consumed {
        return Err(XlsError::Len {
            expected: consumed,
            found: buf.len(),
            typ: "XLUnicodeStringNoCch",
        });
    }
    encoding.decode_to(&buf[1..consumed], len, s, Some(high_byte));
    Ok(consumed)
}

struct Record<'a> {
    typ: u16,
    data: &'a [u8],
    cont: Vec<&'a [u8]>,
}

impl<'a> Record<'a> {
    fn continue_record(&mut self) -> bool {
        if self.cont.is_empty() {
            false
        } else {
            self.data = self.cont.remove(0);
            true
        }
    }

    fn skip(&mut self, mut len: usize) -> Result<(), XlsError> {
        while len > 0 {
            if self.data.is_empty() && !self.continue_record() {
                return Err(XlsError::ContinueRecordTooShort);
            }
            let l = min(len, self.data.len());
            let (_, next) = self.data.split_at(l);
            self.data = next;
            len -= l;
        }
        Ok(())
    }
}

// Simple Debug impl to dump record data in hex format.
impl fmt::Debug for Record<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(
            f,
            "\nRecord = 0x{:04X}, Length = 0x{:04X}, {}",
            self.typ,
            self.data.len(),
            self.data.len()
        )?;

        let mut iter = self.data.chunks(16);
        for chunk in iter.by_ref() {
            for byte in chunk {
                write!(f, "{byte:02X} ")?;
            }
            writeln!(f)?;
        }

        Ok(())
    }
}

struct RecordIter<'a> {
    stream: &'a [u8],
}

impl<'a> Iterator for RecordIter<'a> {
    type Item = Result<Record<'a>, XlsError>;
    fn next(&mut self) -> Option<Self::Item> {
        if self.stream.len() < 4 {
            return if self.stream.is_empty() {
                None
            } else {
                Some(Err(XlsError::EoStream("record type and length")))
            };
        }
        let t = read_u16(self.stream);
        let mut len = read_u16(&self.stream[2..]) as usize;
        if self.stream.len() < len + 4 {
            return Some(Err(XlsError::EoStream("record length")));
        }
        let (data, next) = self.stream.split_at(len + 4);
        self.stream = next;
        let d = &data[4..];

        // Append next record data if it is a Continue record
        let mut cont = Vec::new();
        if next.len() > 4 && read_u16(next) == 0x003C {
            while self.stream.len() > 4 && read_u16(self.stream) == 0x003C {
                len = read_u16(&self.stream[2..]) as usize;
                if self.stream.len() < len + 4 {
                    return Some(Err(XlsError::EoStream("continue record length")));
                }
                let sp = self.stream.split_at(len + 4);
                cont.push(&sp.0[4..]);
                self.stream = sp.1;
            }
        }

        Some(Ok(Record {
            typ: t,
            data: d,
            cont,
        }))
    }
}

/// Write an absolute cell reference (eg: `$B$3`) into `f`.
fn write_absolute_cell_ref(f: &mut String, col: u32, row: u32) {
    f.push('$');
    push_column(col, f);
    write!(f, "${}", row + 1).unwrap();
}

/// Formula parsing
///
/// Does not implement ALL possibilities, only Area are parsed
fn parse_defined_names(rgce: &[u8], biff: Biff) -> Result<(Option<usize>, String), XlsError> {
    if rgce.is_empty() {
        // TODO: do something better here ...
        return Ok((None, "empty rgce".to_string()));
    }
    let ptg = rgce[0];
    let res = match ptg {
        0x3a | 0x5a | 0x7a => {
            // PtgRef3d
            let (sheet_idx, row, col) = match biff {
                Biff::Biff2 | Biff::Biff3 | Biff::Biff4 | Biff::Biff5 => {
                    // ixals(2) + reserved(8) + itabFirst(2) + itabLast(2) + row(2) + col(1)
                    (
                        read_u16(&rgce[11..13]) as usize,
                        read_u16(&rgce[15..17]) as u32 & 0x3FFF,
                        rgce[17] as u32,
                    )
                }
                Biff::Biff8 => {
                    // ixti(2) + row(2) + col(2)
                    (
                        read_u16(&rgce[1..3]) as usize,
                        read_u16(&rgce[3..5]) as u32,
                        read_u16(&rgce[5..7]) as u32,
                    )
                }
            };
            // TODO: check with relative columns
            let mut f = String::new();
            write_absolute_cell_ref(&mut f, col, row);
            (Some(sheet_idx), f)
        }
        0x3b | 0x5b | 0x7b => {
            // PtgArea3d
            let (sheet_idx, row_first, row_last, col_first, col_last) = match biff {
                Biff::Biff2 | Biff::Biff3 | Biff::Biff4 | Biff::Biff5 => {
                    // ixals(2) + reserved(8) + itabFirst(2) + itabLast(2) + rowFirst(2) + rowLast(2) + colFirst(1) + colLast(1)
                    (
                        read_u16(&rgce[11..13]) as usize,
                        read_u16(&rgce[15..17]) as u32 & 0x3FFF,
                        read_u16(&rgce[17..19]) as u32 & 0x3FFF,
                        rgce[19] as u32,
                        rgce[20] as u32,
                    )
                }
                Biff::Biff8 => {
                    // ixti(2) + rowFirst(2) + rowLast(2) + colFirst(2) + colLast(2)
                    (
                        read_u16(&rgce[1..3]) as usize,
                        read_u16(&rgce[3..5]) as u32,
                        read_u16(&rgce[5..7]) as u32,
                        read_u16(&rgce[7..9]) as u32,
                        read_u16(&rgce[9..11]) as u32,
                    )
                }
            };
            // TODO: check with relative columns
            let mut f = String::new();
            write_absolute_cell_ref(&mut f, col_first, row_first);
            f.push(':');
            write_absolute_cell_ref(&mut f, col_last, row_last);
            (Some(sheet_idx), f)
        }
        0x3c | 0x5c | 0x7c | 0x3d | 0x5d | 0x7d => {
            // PtgAreaErr3d or PtgRefErr3d
            let sheet_idx = match biff {
                Biff::Biff8 => read_u16(&rgce[1..3]) as usize,
                Biff::Biff2 | Biff::Biff3 | Biff::Biff4 | Biff::Biff5 => {
                    read_u16(&rgce[11..13]) as usize
                }
            };
            (Some(sheet_idx), "#REF!".to_string())
        }
        _ => (None, format!("Unsupported ptg: {ptg:x}")),
    };
    Ok(res)
}

/// Formula parsing
///
/// `CellParsedFormula` [MS-XLS 2.5.198.3]
fn parse_formula(
    mut rgce: &[u8],
    sheets: &[String],
    names: &[(String, String)],
    xtis: &[Xti],
    encoding: &XlsEncoding,
    biff: Biff,
) -> Result<String, XlsError> {
    let is_pre_biff8 = matches!(biff, Biff::Biff2 | Biff::Biff3 | Biff::Biff4 | Biff::Biff5);
    let mut stack = Vec::new();
    let mut formula = String::with_capacity(rgce.len());
    let cce = read_u16(rgce) as usize;
    rgce = &rgce[2..2 + cce];
    while !rgce.is_empty() {
        let ptg = rgce[0];
        rgce = &rgce[1..];
        match ptg {
            0x3a | 0x5a | 0x7a => {
                // PtgRef3d
                let ixti = read_u16(&rgce[0..2]);
                let rowu = read_u16(&rgce[2..]);
                let colu = read_u16(&rgce[4..]);
                let sh = xtis
                    .get(ixti as usize)
                    .and_then(|xti| sheets.get(xti.itab_first as usize))
                    .map_or("#REF", |sh| sh);
                stack.push(formula.len());
                formula.push_str(sh);
                formula.push('!');
                let col = colu << 2; // first 14 bits only
                if colu & 2 != 0 {
                    formula.push('$');
                }
                push_column(col as u32, &mut formula);
                if colu & 1 != 0 {
                    formula.push('$');
                }
                write!(&mut formula, "{}", rowu + 1).unwrap();
                rgce = &rgce[6..];
            }
            0x3b | 0x5b | 0x7b => {
                // PtgArea3d
                let ixti = read_u16(&rgce[0..2]);
                stack.push(formula.len());
                formula.push_str(sheets.get(ixti as usize).map_or("#REF", |s| &**s));
                formula.push('!');
                // TODO: check with relative columns
                formula.push('$');
                push_column(read_u16(&rgce[6..8]) as u32, &mut formula);
                write!(&mut formula, "${}:$", read_u16(&rgce[2..4]) as u32 + 1).unwrap();
                push_column(read_u16(&rgce[8..10]) as u32, &mut formula);
                write!(&mut formula, "${}", read_u16(&rgce[4..6]) as u32 + 1).unwrap();
                rgce = &rgce[10..];
            }
            0x3c | 0x5c | 0x7c => {
                // PtfRefErr3d
                let ixti = read_u16(&rgce[0..2]);
                stack.push(formula.len());
                formula.push_str(sheets.get(ixti as usize).map_or("#REF", |s| &**s));
                formula.push('!');
                formula.push_str("#REF!");
                rgce = &rgce[6..];
            }
            0x3d | 0x5d | 0x7d => {
                // PtgAreaErr3d
                let ixti = read_u16(&rgce[0..2]);
                stack.push(formula.len());
                formula.push_str(sheets.get(ixti as usize).map_or("#REF", |s| &**s));
                formula.push('!');
                formula.push_str("#REF!");
                rgce = &rgce[10..];
            }
            0x01 => {
                // PtgExp: array/shared formula, ignore
                debug!("ignoring PtgExp array/shared formula");
                stack.push(formula.len());
                // Ensure PtgExp carries a 4-byte operand for the row/column
                // of the array or shared formula it points at.
                if rgce.len() < 4 {
                    return Err(XlsError::Len {
                        expected: 4,
                        found: rgce.len(),
                        typ: "PtgExp",
                    });
                }
                rgce = &rgce[4..];
            }
            0x03..=0x11 => {
                // binary operation
                let e2 = stack.pop().ok_or(XlsError::StackLen)?;
                // imaginary 'e1' will actually already be the start of the binary op
                let op = match ptg {
                    0x03 => "+",
                    0x04 => "-",
                    0x05 => "*",
                    0x06 => "/",
                    0x07 => "^",
                    0x08 => "&",
                    0x09 => "<",
                    0x0A => "<=",
                    0x0B => "=",
                    0x0C => ">",
                    0x0D => ">=",
                    0x0E => "<>",
                    0x0F => " ",
                    0x10 => ",",
                    0x11 => ":",
                    _ => unreachable!(),
                };
                let e2 = formula.split_off(e2);
                write!(&mut formula, "{op}{e2}").unwrap();
            }
            0x12 => {
                let e = stack.last().ok_or(XlsError::StackLen)?;
                formula.insert(*e, '+');
            }
            0x13 => {
                let e = stack.last().ok_or(XlsError::StackLen)?;
                formula.insert(*e, '-');
            }
            0x14 => {
                formula.push('%');
            }
            0x15 => {
                let e = stack.last().ok_or(XlsError::StackLen)?;
                formula.insert(*e, '(');
                formula.push(')');
            }
            0x16 => {
                stack.push(formula.len());
            }
            0x17 => {
                stack.push(formula.len());
                formula.push('\"');
                // PtgStr: cch (1 byte) followed by an XLUnicodeStringNoCch
                let Some(&cch) = rgce.first() else {
                    return Err(XlsError::Len {
                        expected: 1,
                        found: 0,
                        typ: "PtgStr",
                    });
                };
                let consumed =
                    read_unicode_string_no_cch(encoding, &rgce[1..], cch as usize, &mut formula)?;
                formula.push('\"');
                rgce = &rgce[1 + consumed..];
            }
            0x18 => {
                rgce = &rgce[5..];
            }
            0x19 => {
                let etpg = rgce[0];
                rgce = &rgce[1..];
                match etpg {
                    0x01 | 0x02 | 0x08 | 0x20 | 0x21 => rgce = &rgce[2..],
                    0x04 => {
                        // PtgAttrChoose
                        let n = read_u16(&rgce[..2]) as usize + 1;
                        rgce = &rgce[2 + 2 * n..]; // ignore
                    }
                    0x10 => {
                        rgce = &rgce[2..];
                        let e = *stack.last().ok_or(XlsError::StackLen)?;
                        let e = formula.split_off(e);
                        write!(&mut formula, "SUM({e})").unwrap();
                    }
                    0x40 | 0x41 => {
                        // PtfAttrSpace
                        let e = *stack.last().ok_or(XlsError::StackLen)?;
                        let space = match rgce[0] {
                            0x00 | 0x02 | 0x04 | 0x06 => ' ',
                            0x01 | 0x03 | 0x05 => '\r',
                            val => {
                                return Err(XlsError::Unrecognized {
                                    typ: "PtgAttrSpaceType",
                                    val,
                                });
                            }
                        };
                        let cch = rgce[1];
                        for _ in 0..cch {
                            formula.insert(e, space);
                        }
                        rgce = &rgce[2..];
                    }
                    e => return Err(XlsError::Etpg(e)),
                }
            }
            0x1C => {
                stack.push(formula.len());
                let err = rgce[0];
                rgce = &rgce[1..];
                match err {
                    0x00 => formula.push_str("#NULL!"),
                    0x07 => formula.push_str("#DIV/0!"),
                    0x0F => formula.push_str("#VALUE!"),
                    0x17 => formula.push_str("#REF!"),
                    0x1D => formula.push_str("#NAME?"),
                    0x24 => formula.push_str("#NUM!"),
                    0x2A => formula.push_str("#N/A"),
                    0x2B => formula.push_str("#GETTING_DATA"),
                    e => {
                        return Err(XlsError::Unrecognized {
                            typ: "BErr",
                            val: e,
                        });
                    }
                }
            }
            0x1D => {
                stack.push(formula.len());
                formula.push_str(if rgce[0] == 0 { "FALSE" } else { "TRUE" });
                rgce = &rgce[1..];
            }
            0x1E => {
                stack.push(formula.len());
                write!(&mut formula, "{}", read_u16(rgce)).unwrap();
                rgce = &rgce[2..];
            }
            0x1F => {
                stack.push(formula.len());
                write!(&mut formula, "{}", read_f64(rgce)).unwrap();
                rgce = &rgce[8..];
            }
            0x20 | 0x40 | 0x60 => {
                // PtgArray: ignore
                stack.push(formula.len());
                formula.push_str("{PtgArray}");
                rgce = &rgce[7..];
            }
            0x21 | 0x22 | 0x41 | 0x42 | 0x61 | 0x62 => {
                let (iftab, argc) = match ptg {
                    0x22 | 0x42 | 0x62 => {
                        let iftab = read_u16(&rgce[1..]) as usize;
                        let argc = rgce[0] as usize;
                        rgce = &rgce[3..];
                        (iftab, argc)
                    }
                    _ => {
                        let iftab = read_u16(rgce) as usize;
                        if iftab >= crate::utils::FTAB_LEN {
                            return Err(XlsError::IfTab(iftab));
                        }
                        rgce = &rgce[2..];
                        let argc = crate::utils::FTAB_ARGC[iftab] as usize;
                        (iftab, argc)
                    }
                };
                if stack.len() < argc {
                    return Err(XlsError::StackLen);
                }
                if argc > 0 {
                    let args_start = stack.len() - argc;
                    let mut args = stack.split_off(args_start);
                    let start = args[0];
                    for s in &mut args {
                        *s -= start;
                    }
                    let fargs = formula.split_off(start);
                    stack.push(formula.len());
                    args.push(fargs.len());
                    formula.push_str(
                        crate::utils::FTAB
                            .get(iftab)
                            .ok_or(XlsError::IfTab(iftab))?,
                    );
                    formula.push('(');
                    for w in args.windows(2) {
                        formula.push_str(&fargs[w[0]..w[1]]);
                        formula.push(',');
                    }
                    formula.pop();
                    formula.push(')');
                } else {
                    stack.push(formula.len());
                    formula.push_str(
                        crate::utils::FTAB
                            .get(iftab)
                            .ok_or(XlsError::IfTab(iftab))?,
                    );
                    formula.push_str("()");
                }
            }
            0x23 | 0x43 | 0x63 => {
                let iname = read_u32(rgce) as usize - 1; // one-based
                stack.push(formula.len());
                formula.push_str(names.get(iname).map_or("#REF!", |n| &*n.0));
                rgce = &rgce[4..];
            }
            0x24 | 0x44 | 0x64 => {
                stack.push(formula.len());
                if is_pre_biff8 {
                    // BIFF2-5 PtgRef: rw(2 bytes, 14-bit row + 2 rel flags) + col(1 byte)
                    let rw_raw = read_u16(rgce);
                    let row = (rw_raw & 0x3FFF) + 1;
                    let col = rgce[2];
                    if rw_raw & 0x4000 == 0 {
                        formula.push('$');
                    }
                    push_column(col as u32, &mut formula);
                    if rw_raw & 0x8000 == 0 {
                        formula.push('$');
                    }
                    formula.push_str(&format!("{row}"));
                    rgce = &rgce[3..];
                } else {
                    let row = read_u16(rgce) + 1;
                    let col = read_u16(&[rgce[2], rgce[3] & 0x3F]);
                    if rgce[3] & 0x80 != 0x80 {
                        formula.push('$');
                    }
                    push_column(col as u32, &mut formula);
                    if rgce[3] & 0x40 != 0x40 {
                        formula.push('$');
                    }
                    formula.push_str(&format!("{row}"));
                    rgce = &rgce[4..];
                }
            }
            0x25 | 0x45 | 0x65 => {
                stack.push(formula.len());
                if is_pre_biff8 {
                    // BIFF2-5 PtgArea: rwFirst(2) + rwLast(2) + colFirst(1) + colLast(1) = 6 bytes
                    let row_first = (read_u16(&rgce[0..2]) & 0x3FFF) as u32 + 1;
                    let row_last = (read_u16(&rgce[2..4]) & 0x3FFF) as u32 + 1;
                    let col_first = rgce[4] as u32;
                    let col_last = rgce[5] as u32;
                    formula.push('$');
                    push_column(col_first, &mut formula);
                    write!(&mut formula, "${row_first}:$").unwrap();
                    push_column(col_last, &mut formula);
                    write!(&mut formula, "${row_last}").unwrap();
                    rgce = &rgce[6..];
                } else {
                    // columnFirst/columnLast are ColRelU: 14-bit column + fColRel/fRwRel flags.
                    let col_first = read_u16(&[rgce[4], rgce[5] & 0x3F]);
                    let col_last = read_u16(&[rgce[6], rgce[7] & 0x3F]);
                    let row_first = read_u16(&rgce[0..2]) as u32 + 1;
                    let row_last = read_u16(&rgce[2..4]) as u32 + 1;
                    if rgce[5] & 0x80 != 0x80 {
                        formula.push('$');
                    }
                    push_column(col_first as u32, &mut formula);
                    if rgce[5] & 0x40 != 0x40 {
                        formula.push('$');
                    }
                    write!(&mut formula, "{row_first}:").unwrap();
                    if rgce[7] & 0x80 != 0x80 {
                        formula.push('$');
                    }
                    push_column(col_last as u32, &mut formula);
                    if rgce[7] & 0x40 != 0x40 {
                        formula.push('$');
                    }
                    write!(&mut formula, "{row_last}").unwrap();
                    rgce = &rgce[8..];
                }
            }
            0x2A | 0x4A | 0x6A => {
                stack.push(formula.len());
                formula.push_str("#REF!");
                rgce = &rgce[if is_pre_biff8 { 3 } else { 4 }..];
            }
            0x2B | 0x4B | 0x6B => {
                stack.push(formula.len());
                formula.push_str("#REF!");
                rgce = &rgce[if is_pre_biff8 { 6 } else { 8 }..];
            }
            0x39 | 0x59 => {
                // PfgNameX
                stack.push(formula.len());
                formula.push_str("[PtgNameX]");
                rgce = &rgce[6..];
            }
            _ => {
                return Err(XlsError::Unrecognized {
                    typ: "ptg",
                    val: ptg,
                });
            }
        }
    }
    if stack.len() == 1 {
        Ok(formula)
    } else {
        Err(XlsError::InvalidFormula {
            stack_size: stack.len(),
        })
    }
}

/// `FormulaValue` [MS-XLS 2.5.133]
fn parse_formula_value(
    r: &[u8],
    format: Option<&CellFormat>,
    is_1904: bool,
) -> Result<Option<Data>, XlsError> {
    match *r {
        // String, value should be in next record
        [0x00, .., 0xFF, 0xFF] => Ok(None),
        [0x01, _, b, .., 0xFF, 0xFF] => Ok(Some(Data::Bool(b != 0))),
        [0x02, _, e, .., 0xFF, 0xFF] => parse_err(e).map(Some),
        // ignore, return blank string value
        [0x03, _, .., 0xFF, 0xFF] => Ok(Some(Data::String("".to_string()))),
        [e, .., 0xFF, 0xFF] => Err(XlsError::Unrecognized {
            typ: "error",
            val: e,
        }),
        _ => Ok(Some(format_excel_f64(read_f64(r), format, is_1904))),
    }
}

// OfficeArtRecord [MS-ODRAW 1.3.1].
#[cfg(feature = "picture")]
struct ArtRecord<'a> {
    instance: u16,
    typ: u16,
    data: &'a [u8],
}

#[cfg(feature = "picture")]
struct ArtRecordIter<'a> {
    stream: &'a [u8],
}

#[cfg(feature = "picture")]
impl<'a> Iterator for ArtRecordIter<'a> {
    type Item = Result<ArtRecord<'a>, XlsError>;
    fn next(&mut self) -> Option<Self::Item> {
        if self.stream.len() < 8 {
            return if self.stream.is_empty() {
                None
            } else {
                Some(Err(XlsError::EoStream("art record header")))
            };
        }
        let ver_ins = read_u16(self.stream);
        let instance = ver_ins >> 4;
        let typ = read_u16(&self.stream[2..]);
        if typ < 0xF000 {
            return Some(Err(XlsError::Art("type range 0xF000 - 0xFFFF")));
        }
        let len = read_usize(&self.stream[4..]);
        if self.stream.len() < len + 8 {
            return Some(Err(XlsError::EoStream("art record length")));
        }
        let (d, next) = self.stream.split_at(len + 8);
        self.stream = next;
        let data = &d[8..];

        Some(Ok(ArtRecord {
            instance,
            typ,
            data,
        }))
    }
}

// Parsing pictures.
#[cfg(feature = "picture")]
fn parse_pictures(stream: &[u8]) -> Result<Vec<(String, Vec<u8>)>, XlsError> {
    let mut pics = Vec::new();
    let records = ArtRecordIter { stream };
    for record in records {
        let r = record?;
        match r.typ {
            // OfficeArtDggContainer [MS-ODRAW 2.2.12]
            // OfficeArtBStoreContainer [MS-ODRAW 2.2.20]
            0xF000 | 0xF001 => pics.extend(parse_pictures(r.data)?),
            // OfficeArtFBSE [MS-ODRAW 2.2.32]
            0xF007 => {
                let skip = 36 + r.data[33] as usize;
                pics.extend(parse_pictures(&r.data[skip..])?);
            }
            // OfficeArtBlip [MS-ODRAW 2.2.23]
            0xF01A | 0xF01B | 0xF01C | 0xF01D | 0xF01E | 0xF01F | 0xF029 | 0xF02A => {
                let ext_skip = match r.typ {
                    // OfficeArtBlipEMF [MS-ODRAW 2.2.24]
                    0xF01A => {
                        let skip = match r.instance {
                            0x3D4 => 50usize,
                            0x3D5 => 66,
                            _ => unreachable!(),
                        };
                        Ok(("emf", skip))
                    }
                    // OfficeArtBlipWMF [MS-ODRAW 2.2.25]
                    0xF01B => {
                        let skip = match r.instance {
                            0x216 => 50usize,
                            0x217 => 66,
                            _ => unreachable!(),
                        };
                        Ok(("wmf", skip))
                    }
                    // OfficeArtBlipPICT [MS-ODRAW 2.2.26]
                    0xF01C => {
                        let skip = match r.instance {
                            0x542 => 50usize,
                            0x543 => 66,
                            _ => unreachable!(),
                        };
                        Ok(("pict", skip))
                    }
                    // OfficeArtBlipJPEG [MS-ODRAW 2.2.27]
                    0xF01D | 0xF02A => {
                        let skip = match r.instance {
                            0x46A | 0x6E2 => 17usize,
                            0x46B | 0x6E3 => 33,
                            _ => unreachable!(),
                        };
                        Ok(("jpg", skip))
                    }
                    // OfficeArtBlipPNG [MS-ODRAW 2.2.28]
                    0xF01E => {
                        let skip = match r.instance {
                            0x6E0 => 17usize,
                            0x6E1 => 33,
                            _ => unreachable!(),
                        };
                        Ok(("png", skip))
                    }
                    // OfficeArtBlipDIB [MS-ODRAW 2.2.29]
                    0xF01F => {
                        let skip = match r.instance {
                            0x7A8 => 17usize,
                            0x7A9 => 33,
                            _ => unreachable!(),
                        };
                        Ok(("dib", skip))
                    }
                    // OfficeArtBlipTIFF [MS-ODRAW 2.2.30]
                    0xF029 => {
                        let skip = match r.instance {
                            0x6E4 => 17usize,
                            0x6E5 => 33,
                            _ => unreachable!(),
                        };
                        Ok(("tiff", skip))
                    }
                    _ => Err(XlsError::Art("picture type not support")),
                };
                let ext_skip = ext_skip?;
                pics.push((ext_skip.0.to_string(), Vec::from(&r.data[ext_skip.1..])));
            }
            _ => {}
        }
    }
    Ok(pics)
}

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

    #[test]
    fn test_parse_string() {
        let enc = XlsEncoding::from_codepage(1252).unwrap();
        parse_string(&[0, 1], &enc, Biff::Biff8).unwrap_err();
    }
}