miniexcel 0.4.0

use std::collections::HashMap;
use std::fs::File;
use std::io::{BufReader, Cursor, Read, Seek};
use std::path::{Path, PathBuf};
use std::sync::mpsc::{self, Receiver, SyncSender};
use std::sync::{
    Arc,
    atomic::{AtomicBool, Ordering},
};
use std::thread::{self, JoinHandle};

use calamine::{CellErrorType, Data, DataType, ExcelDateTime, ExcelDateTimeType};
use quick_xml::Reader;
use quick_xml::encoding::Decoder;
use quick_xml::events::{BytesRef, BytesStart, Event};
use zip::ZipArchive;
use zip::result::ZipError;

use crate::cell::MAX_EXCEL_COLUMN;
use crate::reader::{SelectedCellMetadata, SelectedRow};
use crate::{
    CellReference, Error, ExcelRange, ReadOptions, Result, SheetInfo as PublicSheetInfo, SheetType,
    SheetVisibility,
};

use super::shared_strings::SharedStrings;

const ROW_BUFFER_SIZE: usize = 8;
const MAX_PREALLOCATED_ROW_CELLS: usize = 256;

pub(super) struct StreamingRawRows {
    receiver: Option<Receiver<Result<SelectedRow>>>,
    worker: Option<JoinHandle<()>>,
    sheet_name: String,
    cancelled: Arc<AtomicBool>,
}

pub(super) struct StreamingTableRawRows {
    receiver: Option<Receiver<Result<SelectedRow>>>,
    worker: Option<JoinHandle<()>>,
    sheet_name: String,
    headers: Vec<Option<String>>,
    cancelled: Arc<AtomicBool>,
}

struct ResolvedTable {
    sheet_name: String,
    sheet_path: String,
    headers: Vec<Option<String>>,
    options: ReadOptions,
    empty: bool,
}

pub(super) struct TableReady {
    pub(super) sheet_name: String,
    pub(super) headers: Vec<Option<String>>,
}

pub(super) fn visit_raw_rows<F>(
    bytes: &[u8],
    options: &ReadOptions,
    preserve_structure: bool,
    visitor: F,
) -> Result<String>
where
    F: FnMut(&str, SelectedRow) -> Result<bool>,
{
    visit_raw_rows_from_reader(Cursor::new(bytes), options, preserve_structure, false, visitor)
}

pub(super) fn visit_raw_rows_from_reader<R, F>(
    reader: R,
    options: &ReadOptions,
    preserve_structure: bool,
    allow_disk_cache: bool,
    mut visitor: F,
) -> Result<String>
where
    R: Read + Seek,
    F: FnMut(&str, SelectedRow) -> Result<bool>,
{
    validate_range(options)?;
    let mut archive =
        ZipArchive::new(reader).map_err(|error| stream_error("cannot open XLSX reader:", error))?;
    let context = prepare_workbook(&mut archive, options, preserve_structure, allow_disk_cache)?;
    let sheet_name = context.sheet_name.clone();
    let cancelled = AtomicBool::new(false);
    let scan = prepare_query_scan(
        &mut archive,
        &context.sheet_path,
        options,
        preserve_structure,
        &cancelled,
    )?;
    let mut visitor_error = None;
    stream_worksheet(&mut archive, context, scan, options, &cancelled, &mut |row| match visitor(
        &sheet_name,
        row,
    ) {
        Ok(should_continue) => should_continue,
        Err(error) => {
            visitor_error = Some(error);
            false
        }
    })?;
    if let Some(error) = visitor_error {
        return Err(error);
    }
    Ok(sheet_name)
}

pub(super) fn visit_table_raw_rows_from_reader<R, F>(
    reader: R,
    table_name: &str,
    sheet_name: Option<&str>,
    allow_disk_cache: bool,
    mut visitor: F,
) -> Result<TableReady>
where
    R: Read + Seek,
    F: FnMut(&str, &[Option<String>], SelectedRow) -> Result<bool>,
{
    let mut archive =
        ZipArchive::new(reader).map_err(|error| stream_error("cannot open XLSX reader:", error))?;
    let resolved = resolve_table(&mut archive, table_name, sheet_name)?;
    let ready =
        TableReady { sheet_name: resolved.sheet_name.clone(), headers: resolved.headers.clone() };
    if resolved.empty {
        return Ok(ready);
    }
    let context = prepare_resolved_table(&mut archive, &resolved, allow_disk_cache)?;
    let cancelled = AtomicBool::new(false);
    let scan = scan_worksheet(&mut archive, &resolved.sheet_path, &cancelled)?;
    let mut visitor_error = None;
    stream_worksheet(&mut archive, context, scan, &resolved.options, &cancelled, &mut |row| {
        match visitor(&ready.sheet_name, &ready.headers, row) {
            Ok(should_continue) => should_continue,
            Err(error) => {
                visitor_error = Some(error);
                false
            }
        }
    })?;
    if let Some(error) = visitor_error {
        return Err(error);
    }
    Ok(ready)
}

pub(super) fn visit_table_raw_rows<F>(
    bytes: &[u8],
    table_name: &str,
    sheet_name: Option<&str>,
    visitor: F,
) -> Result<TableReady>
where
    F: FnMut(&str, &[Option<String>], SelectedRow) -> Result<bool>,
{
    visit_table_raw_rows_from_reader(Cursor::new(bytes), table_name, sheet_name, false, visitor)
}

pub(super) fn sheet_names_from_bytes(bytes: &[u8]) -> Result<Vec<String>> {
    sheet_names_from_reader(Cursor::new(bytes))
}

pub(super) fn sheet_names_from_reader<R>(reader: R) -> Result<Vec<String>>
where
    R: Read + Seek,
{
    let mut archive =
        ZipArchive::new(reader).map_err(|error| stream_error("cannot open XLSX reader:", error))?;
    Ok(read_workbook_info(&mut archive)?.sheets.into_iter().map(|sheet| sheet.name).collect())
}

pub(super) fn sheet_names(path: impl AsRef<Path>) -> Result<Vec<String>> {
    let file = File::open(path)?;
    let mut archive = ZipArchive::new(BufReader::new(file))
        .map_err(|error| stream_error("cannot open XLSX workbook:", error))?;
    Ok(read_workbook_info(&mut archive)?.sheets.into_iter().map(|sheet| sheet.name).collect())
}

pub(super) fn sheet_info(path: impl AsRef<Path>) -> Result<Vec<PublicSheetInfo>> {
    let file = File::open(path)?;
    let mut archive = ZipArchive::new(BufReader::new(file))
        .map_err(|error| stream_error("cannot open XLSX workbook:", error))?;
    read_sheet_info(&mut archive)
}

pub(super) fn sheet_info_from_bytes(bytes: &[u8]) -> Result<Vec<PublicSheetInfo>> {
    sheet_info_from_reader(Cursor::new(bytes))
}

pub(super) fn sheet_info_from_reader<R>(reader: R) -> Result<Vec<PublicSheetInfo>>
where
    R: Read + Seek,
{
    let mut archive =
        ZipArchive::new(reader).map_err(|error| stream_error("cannot open XLSX reader:", error))?;
    read_sheet_info(&mut archive)
}

fn read_sheet_info<R>(archive: &mut ZipArchive<R>) -> Result<Vec<PublicSheetInfo>>
where
    R: Read + Seek,
{
    let workbook = read_workbook_info(archive)?;
    let relationships = read_workbook_relationships(archive)?;
    workbook
        .sheets
        .into_iter()
        .enumerate()
        .map(|(index, sheet)| {
            let relationship = relationships.get(&sheet.relationship_id).ok_or_else(|| {
                Error::stream(format!(
                    "worksheet relationship '{}' was not found",
                    sheet.relationship_id
                ))
            })?;
            let sheet_type = sheet_type_from_relationship(&relationship.relationship_type)?;
            Ok(PublicSheetInfo::new(
                sheet.id,
                index,
                sheet.name,
                sheet_type,
                sheet.visibility,
                index == workbook.active_sheet_index,
            ))
        })
        .collect()
}

pub(super) fn sheet_dimensions(path: impl AsRef<Path>) -> Result<Vec<ExcelRange>> {
    let file = File::open(path)?;
    let mut archive = ZipArchive::new(BufReader::new(file))
        .map_err(|error| stream_error("cannot open XLSX workbook:", error))?;
    read_sheet_dimensions(&mut archive)
}

pub(super) fn sheet_dimensions_from_bytes(bytes: &[u8]) -> Result<Vec<ExcelRange>> {
    sheet_dimensions_from_reader(Cursor::new(bytes))
}

pub(super) fn sheet_dimensions_from_reader<R>(reader: R) -> Result<Vec<ExcelRange>>
where
    R: Read + Seek,
{
    let mut archive =
        ZipArchive::new(reader).map_err(|error| stream_error("cannot open XLSX reader:", error))?;
    read_sheet_dimensions(&mut archive)
}

fn read_sheet_dimensions<R>(archive: &mut ZipArchive<R>) -> Result<Vec<ExcelRange>>
where
    R: Read + Seek,
{
    let workbook = read_workbook_info(archive)?;
    let relationships = read_workbook_relationships(archive)?;
    let cancelled = AtomicBool::new(false);
    let mut dimensions = Vec::with_capacity(workbook.sheets.len());
    for sheet in workbook.sheets {
        let sheet_path = &relationships
            .get(&sheet.relationship_id)
            .ok_or_else(|| {
                Error::stream(format!(
                    "worksheet relationship '{}' was not found",
                    sheet.relationship_id
                ))
            })?
            .target;
        let extent = match read_declared_worksheet_extent(archive, sheet_path)? {
            Some(extent) => extent,
            None => scan_worksheet(archive, sheet_path, &cancelled)?.extent,
        };
        dimensions.push(ExcelRange::from_bounds(
            extent.start_row,
            extent.start_column,
            extent.end_row,
            extent.end_column,
        ));
    }
    Ok(dimensions)
}

impl StreamingRawRows {
    pub(super) fn open(
        path: impl AsRef<Path>,
        options: &ReadOptions,
        preserve_structure: bool,
    ) -> Result<Self> {
        validate_range(options)?;
        let path = path.as_ref().to_owned();
        let file = File::open(&path)?;
        let (ready_sender, ready_receiver) = mpsc::sync_channel(0);
        let (row_sender, row_receiver) = mpsc::sync_channel(ROW_BUFFER_SIZE);
        let cancelled = Arc::new(AtomicBool::new(false));
        let worker_cancelled = Arc::clone(&cancelled);
        let options = options.clone();
        let worker =
            thread::Builder::new().name("miniexcel-xlsx-stream".to_owned()).spawn(move || {
                worker_main(
                    path,
                    BufReader::new(file),
                    options,
                    preserve_structure,
                    worker_cancelled,
                    ready_sender,
                    row_sender,
                )
            })?;

        let ready = match ready_receiver.recv() {
            Ok(ready) => ready,
            Err(_) => Err(Error::stream(
                "the XLSX streaming worker stopped during initialization".to_owned(),
            )),
        };
        match ready {
            Ok(sheet_name) => Ok(Self {
                receiver: Some(row_receiver),
                worker: Some(worker),
                sheet_name,
                cancelled,
            }),
            Err(error) => {
                drop(row_receiver);
                let _ = worker.join();
                Err(error)
            }
        }
    }

    pub(super) fn sheet_name(&self) -> &str {
        &self.sheet_name
    }
}

impl StreamingTableRawRows {
    pub(super) fn open(
        path: impl AsRef<Path>,
        table_name: &str,
        sheet_name: Option<&str>,
    ) -> Result<Self> {
        let path = path.as_ref().to_owned();
        let file = File::open(&path)?;
        let (ready_sender, ready_receiver) = mpsc::sync_channel(0);
        let (row_sender, row_receiver) = mpsc::sync_channel(ROW_BUFFER_SIZE);
        let cancelled = Arc::new(AtomicBool::new(false));
        let worker_cancelled = Arc::clone(&cancelled);
        let table_name = table_name.to_owned();
        let sheet_name = sheet_name.map(str::to_owned);
        let worker = thread::Builder::new().name("miniexcel-xlsx-table-stream".to_owned()).spawn(
            move || {
                table_worker_main(
                    path,
                    BufReader::new(file),
                    table_name,
                    sheet_name,
                    worker_cancelled,
                    ready_sender,
                    row_sender,
                )
            },
        )?;

        let ready = match ready_receiver.recv() {
            Ok(ready) => ready,
            Err(_) => {
                Err(Error::stream("the XLSX table worker stopped during initialization".to_owned()))
            }
        };
        match ready {
            Ok(ready) => Ok(Self {
                receiver: Some(row_receiver),
                worker: Some(worker),
                sheet_name: ready.sheet_name,
                headers: ready.headers,
                cancelled,
            }),
            Err(error) => {
                drop(row_receiver);
                let _ = worker.join();
                Err(error)
            }
        }
    }

    pub(super) fn sheet_name(&self) -> &str {
        &self.sheet_name
    }

    pub(super) fn headers(&self) -> &[Option<String>] {
        &self.headers
    }
}

impl Iterator for StreamingTableRawRows {
    type Item = Result<SelectedRow>;

    fn next(&mut self) -> Option<Self::Item> {
        self.receiver.as_ref()?.recv().ok()
    }
}

impl Drop for StreamingTableRawRows {
    fn drop(&mut self) {
        self.cancelled.store(true, Ordering::Relaxed);
        self.receiver.take();
        if let Some(worker) = self.worker.take() {
            let _ = worker.join();
        }
    }
}

impl Iterator for StreamingRawRows {
    type Item = Result<SelectedRow>;

    fn next(&mut self) -> Option<Self::Item> {
        self.receiver.as_ref()?.recv().ok()
    }
}

impl Drop for StreamingRawRows {
    fn drop(&mut self) {
        self.cancelled.store(true, Ordering::Relaxed);
        self.receiver.take();
        if let Some(worker) = self.worker.take() {
            let _ = worker.join();
        }
    }
}

struct WorkbookContext {
    sheet_name: String,
    sheet_path: String,
    shared_strings: SharedStrings,
    styles: Vec<CellStyle>,
    is_1904: bool,
    preserve_structure: bool,
}

#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
enum CellFormat {
    #[default]
    Other,
    DateTime,
    TimeDelta,
}

struct CellStyle {
    format: CellFormat,
    number_format: Option<Arc<str>>,
}

#[derive(Default)]
struct WorkbookInfo {
    sheets: Vec<WorkbookSheet>,
    is_1904: bool,
    active_sheet_index: usize,
}

struct WorkbookSheet {
    id: u32,
    name: String,
    relationship_id: String,
    visibility: SheetVisibility,
}

struct WorkbookRelationship {
    target: String,
    relationship_type: String,
}

fn worker_main<R>(
    path: PathBuf,
    reader: R,
    options: ReadOptions,
    preserve_structure: bool,
    cancelled: Arc<AtomicBool>,
    ready_sender: SyncSender<Result<String>>,
    row_sender: SyncSender<Result<SelectedRow>>,
) where
    R: Read + Seek,
{
    let mut archive = match ZipArchive::new(reader) {
        Ok(archive) => archive,
        Err(error) => {
            let _ = ready_sender
                .send(Err(stream_error(format!("cannot open '{}':", path.display()), error)));
            return;
        }
    };
    let context = match prepare_workbook(&mut archive, &options, preserve_structure, true) {
        Ok(context) => context,
        Err(error) => {
            let _ = ready_sender.send(Err(error));
            return;
        }
    };
    if ready_sender.send(Ok(context.sheet_name.clone())).is_err() {
        return;
    }
    let scan = match prepare_query_scan(
        &mut archive,
        &context.sheet_path,
        &options,
        preserve_structure,
        &cancelled,
    ) {
        Ok(scan) => scan,
        Err(error) => {
            let _ = row_sender.send(Err(error));
            return;
        }
    };
    if cancelled.load(Ordering::Relaxed) {
        return;
    }
    let mut emit = |row| row_sender.send(Ok(row)).is_ok();
    if let Err(error) =
        stream_worksheet(&mut archive, context, scan, &options, &cancelled, &mut emit)
    {
        let _ = row_sender.send(Err(error));
    }
}

fn table_worker_main<R>(
    path: PathBuf,
    reader: R,
    table_name: String,
    sheet_name: Option<String>,
    cancelled: Arc<AtomicBool>,
    ready_sender: SyncSender<Result<TableReady>>,
    row_sender: SyncSender<Result<SelectedRow>>,
) where
    R: Read + Seek,
{
    let mut archive = match ZipArchive::new(reader) {
        Ok(archive) => archive,
        Err(error) => {
            let _ = ready_sender
                .send(Err(stream_error(format!("cannot open '{}':", path.display()), error)));
            return;
        }
    };
    let resolved = match resolve_table(&mut archive, &table_name, sheet_name.as_deref()) {
        Ok(resolved) => resolved,
        Err(error) => {
            let _ = ready_sender.send(Err(error));
            return;
        }
    };
    let ready =
        TableReady { sheet_name: resolved.sheet_name.clone(), headers: resolved.headers.clone() };
    if ready_sender.send(Ok(ready)).is_err() || resolved.empty {
        return;
    }
    let context = match prepare_resolved_table(&mut archive, &resolved, true) {
        Ok(context) => context,
        Err(error) => {
            let _ = row_sender.send(Err(error));
            return;
        }
    };
    let scan = match scan_worksheet(&mut archive, &resolved.sheet_path, &cancelled) {
        Ok(scan) => scan,
        Err(error) => {
            let _ = row_sender.send(Err(error));
            return;
        }
    };
    let mut emit = |row| row_sender.send(Ok(row)).is_ok();
    if let Err(error) =
        stream_worksheet(&mut archive, context, scan, &resolved.options, &cancelled, &mut emit)
    {
        let _ = row_sender.send(Err(error));
    }
}

fn prepare_resolved_table<R>(
    archive: &mut ZipArchive<R>,
    table: &ResolvedTable,
    allow_disk_cache: bool,
) -> Result<WorkbookContext>
where
    R: Read + Seek,
{
    let workbook = read_workbook_info(archive)?;
    let shared_strings = read_shared_strings(archive, &table.options, allow_disk_cache)?;
    let styles = read_styles(archive, false)?;
    Ok(WorkbookContext {
        sheet_name: table.sheet_name.clone(),
        sheet_path: table.sheet_path.clone(),
        shared_strings,
        styles,
        is_1904: workbook.is_1904,
        preserve_structure: false,
    })
}

fn resolve_table<R>(
    archive: &mut ZipArchive<R>,
    table_name: &str,
    sheet_name: Option<&str>,
) -> Result<ResolvedTable>
where
    R: Read + Seek,
{
    if table_name.is_empty() {
        return Err(Error::table_not_found(table_name));
    }
    let workbook = read_workbook_info(archive)?;
    let sheet = match sheet_name {
        Some(name) => workbook
            .sheets
            .iter()
            .find(|sheet| sheet.name == name)
            .ok_or_else(|| Error::sheet_not_found(name))?,
        None => workbook.sheets.first().ok_or_else(Error::no_worksheets)?,
    };
    let sheet_path = read_relationship_target(archive, &sheet.relationship_id)?;
    let relationship_path = relationship_part_path(&sheet_path)?;
    let file = match archive.by_name(&relationship_path) {
        Ok(file) => file,
        Err(ZipError::FileNotFound) => return Err(Error::table_not_found(table_name)),
        Err(error) => return Err(stream_error("cannot read worksheet relationships:", error)),
    };
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    let mut table_targets = Vec::new();
    loop {
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid worksheet relationships:", error))?
        {
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"Relationship") =>
            {
                let relationship_type = attribute(&event, xml.decoder(), b"Type")?;
                let target_mode = attribute(&event, xml.decoder(), b"TargetMode")?;
                if relationship_type.as_deref().and_then(|value| value.rsplit('/').next())
                    == Some("table")
                    && !target_mode
                        .as_deref()
                        .is_some_and(|value| value.eq_ignore_ascii_case("External"))
                {
                    let target = attribute(&event, xml.decoder(), b"Target")?.ok_or_else(|| {
                        Error::invalid_table(table_name, "table relationship has no target")
                    })?;
                    table_targets.push(resolve_part_target(&sheet_path, &target)?);
                }
            }
            Event::Eof => break,
            _ => {}
        }
        buffer.clear();
    }
    drop(xml);

    for target in table_targets {
        let file = match archive.by_name(&target) {
            Ok(file) => file,
            Err(ZipError::FileNotFound) => continue,
            Err(error) => return Err(stream_error("cannot read table metadata:", error)),
        };
        let mut xml = Reader::from_reader(BufReader::new(file));
        let mut buffer = Vec::new();
        let mut matched = false;
        let mut reference = None;
        let mut header_row_count = 1_u32;
        let mut headers = Vec::new();
        loop {
            match xml
                .read_event_into(&mut buffer)
                .map_err(|error| stream_error("invalid table metadata:", error))?
            {
                Event::Start(event) | Event::Empty(event)
                    if is_name(event.name().as_ref(), b"table") =>
                {
                    matched = attribute(&event, xml.decoder(), b"name")?
                        .is_some_and(|name| name.eq_ignore_ascii_case(table_name));
                    if matched {
                        reference = attribute(&event, xml.decoder(), b"ref")?;
                        header_row_count = attribute(&event, xml.decoder(), b"headerRowCount")?
                            .and_then(|value| value.parse().ok())
                            .unwrap_or(1);
                    }
                }
                Event::Start(event) | Event::Empty(event)
                    if matched && is_name(event.name().as_ref(), b"tableColumn") =>
                {
                    let index = headers.len();
                    headers.push(Some(
                        attribute(&event, xml.decoder(), b"name")?
                            .unwrap_or_else(|| format!("Column{index}")),
                    ));
                }
                Event::Eof => break,
                _ => {}
            }
            buffer.clear();
        }
        if !matched {
            continue;
        }
        if headers.is_empty() {
            return Err(Error::table_not_found(table_name));
        }
        let reference = reference
            .ok_or_else(|| Error::invalid_table(table_name, "table metadata has no range"))?;
        let (start, end) = parse_table_range(table_name, &reference)?;
        let width = end.column() - start.column() + 1;
        let fallback = crate::reader::column_names(start.column(), width);
        headers.resize_with(width, || None);
        for (index, header) in headers.iter_mut().enumerate().take(width) {
            if header.is_none() {
                *header = fallback[index].clone();
            }
        }
        headers.truncate(width);
        let body_start_row = start.row().saturating_add(usize::from(header_row_count != 0));
        let empty = body_start_row > end.row();
        let body_start =
            if empty { start } else { CellReference::new(body_start_row, start.column())? };
        let options = ReadOptions::new()
            .with_sheet_name(&sheet.name)
            .with_start_cell(body_start)
            .with_end_cell(end)
            .with_header_mode(crate::HeaderMode::None);
        return Ok(ResolvedTable {
            sheet_name: sheet.name.clone(),
            sheet_path,
            headers,
            options,
            empty,
        });
    }
    Err(Error::table_not_found(table_name))
}

fn parse_table_range(table_name: &str, reference: &str) -> Result<(CellReference, CellReference)> {
    let mut cells = reference.split(':');
    let start =
        cells.next().ok_or_else(|| Error::invalid_table(table_name, "table range is empty"))?;
    let end = cells
        .next()
        .ok_or_else(|| Error::invalid_table(table_name, "table range must contain two cells"))?;
    if cells.next().is_some() {
        return Err(Error::invalid_table(table_name, "table range contains too many cells"));
    }
    let start = start.parse::<CellReference>().map_err(|_| {
        Error::invalid_table(table_name, format!("invalid table range '{reference}'"))
    })?;
    let end = end.parse::<CellReference>().map_err(|_| {
        Error::invalid_table(table_name, format!("invalid table range '{reference}'"))
    })?;
    if end.row() < start.row() || end.column() < start.column() {
        return Err(Error::invalid_table(
            table_name,
            format!("reversed table range '{reference}'"),
        ));
    }
    Ok((start, end))
}

fn relationship_part_path(source: &str) -> Result<String> {
    let (directory, file) = source
        .rsplit_once('/')
        .ok_or_else(|| Error::stream(format!("invalid worksheet path '{source}'")))?;
    Ok(format!("{directory}/_rels/{file}.rels"))
}

fn resolve_part_target(source: &str, target: &str) -> Result<String> {
    if target.contains('\\') || target.contains(['?', '#']) {
        return Err(Error::stream(format!("unsafe relationship target '{target}'")));
    }
    let base = source.rsplit_once('/').map_or("", |(directory, _)| directory);
    let combined = if target.starts_with('/') {
        target.trim_start_matches('/').to_owned()
    } else {
        format!("{base}/{target}")
    };
    let mut parts = Vec::new();
    for part in combined.split('/') {
        match part {
            "" | "." => {}
            ".." => {
                if parts.pop().is_none() {
                    return Err(Error::stream(format!(
                        "relationship target '{target}' escapes the package root"
                    )));
                }
            }
            part => parts.push(part),
        }
    }
    if parts.is_empty() {
        return Err(Error::stream(format!("relationship target '{target}' is empty")));
    }
    Ok(parts.join("/"))
}

fn prepare_workbook<R>(
    archive: &mut ZipArchive<R>,
    options: &ReadOptions,
    preserve_structure: bool,
    allow_disk_cache: bool,
) -> Result<WorkbookContext>
where
    R: Read + Seek,
{
    let workbook = read_workbook_info(archive)?;
    let sheet = match options.sheet_name() {
        Some(sheet_name) => workbook
            .sheets
            .iter()
            .find(|sheet| sheet.name == sheet_name)
            .ok_or_else(|| Error::sheet_not_found(sheet_name))?,
        None => workbook.sheets.first().ok_or_else(Error::no_worksheets)?,
    };
    let sheet_path = read_relationship_target(archive, &sheet.relationship_id)?;
    let shared_strings = read_shared_strings(archive, options, allow_disk_cache)?;
    let styles = read_styles(archive, preserve_structure)?;
    Ok(WorkbookContext {
        sheet_name: sheet.name.clone(),
        sheet_path,
        shared_strings,
        styles,
        is_1904: workbook.is_1904,
        preserve_structure,
    })
}

fn read_workbook_info<R>(archive: &mut ZipArchive<R>) -> Result<WorkbookInfo>
where
    R: Read + Seek,
{
    let file = archive
        .by_name("xl/workbook.xml")
        .map_err(|error| stream_error("cannot read xl/workbook.xml:", error))?;
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    let mut workbook = WorkbookInfo::default();
    loop {
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid xl/workbook.xml:", error))?
        {
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"workbookPr") =>
            {
                workbook.is_1904 = attribute(&event, xml.decoder(), b"date1904")?
                    .is_some_and(|value| value == "1" || value.eq_ignore_ascii_case("true"));
            }
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"workbookView") =>
            {
                if let Some(index) = attribute(&event, xml.decoder(), b"activeTab")?
                    .and_then(|value| value.parse().ok())
                {
                    workbook.active_sheet_index = index;
                }
            }
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"sheet") =>
            {
                let Some(name) =
                    attribute(&event, xml.decoder(), b"name")?.filter(|name| !name.is_empty())
                else {
                    buffer.clear();
                    continue;
                };
                let Some(relationship_id) = attribute(&event, xml.decoder(), b"id")? else {
                    buffer.clear();
                    continue;
                };
                let id = attribute(&event, xml.decoder(), b"sheetId")?
                    .and_then(|value| value.parse().ok())
                    .unwrap_or(0);
                let visibility = match attribute(&event, xml.decoder(), b"state")? {
                    None => SheetVisibility::Visible,
                    Some(state) if state.eq_ignore_ascii_case("visible") => {
                        SheetVisibility::Visible
                    }
                    Some(state) if state.eq_ignore_ascii_case("hidden") => SheetVisibility::Hidden,
                    Some(state) if state.eq_ignore_ascii_case("veryHidden") => {
                        SheetVisibility::VeryHidden
                    }
                    Some(state) => {
                        return Err(Error::stream(format!(
                            "unable to parse state '{state}' for worksheet '{name}'"
                        )));
                    }
                };
                workbook.sheets.push(WorkbookSheet { id, name, relationship_id, visibility });
            }
            Event::Eof => break,
            _ => {}
        }
        buffer.clear();
    }
    Ok(workbook)
}

fn read_relationship_target<R>(archive: &mut ZipArchive<R>, relationship_id: &str) -> Result<String>
where
    R: Read + Seek,
{
    let file = archive
        .by_name("xl/_rels/workbook.xml.rels")
        .map_err(|error| stream_error("cannot read workbook relationships:", error))?;
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    loop {
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid workbook relationships:", error))?
        {
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"Relationship") =>
            {
                if attribute(&event, xml.decoder(), b"Id")?.as_deref() == Some(relationship_id) {
                    let target = attribute(&event, xml.decoder(), b"Target")?.ok_or_else(|| {
                        Error::stream(format!(
                            "worksheet relationship '{relationship_id}' has no target"
                        ))
                    })?;
                    return Ok(normalize_zip_path(&target));
                }
            }
            Event::Eof => break,
            _ => {}
        }
        buffer.clear();
    }
    Err(Error::stream(format!("worksheet relationship '{relationship_id}' was not found")))
}

fn read_workbook_relationships<R>(
    archive: &mut ZipArchive<R>,
) -> Result<HashMap<String, WorkbookRelationship>>
where
    R: Read + Seek,
{
    let file = archive
        .by_name("xl/_rels/workbook.xml.rels")
        .map_err(|error| stream_error("cannot read workbook relationships:", error))?;
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    let mut relationships = HashMap::new();
    loop {
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid workbook relationships:", error))?
        {
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"Relationship") =>
            {
                if let (Some(id), Some(target), Some(relationship_type)) = (
                    attribute(&event, xml.decoder(), b"Id")?,
                    attribute(&event, xml.decoder(), b"Target")?,
                    attribute(&event, xml.decoder(), b"Type")?,
                ) {
                    relationships.insert(
                        id,
                        WorkbookRelationship {
                            target: normalize_zip_path(&target),
                            relationship_type,
                        },
                    );
                }
            }
            Event::Eof => break,
            _ => {}
        }
        buffer.clear();
    }
    Ok(relationships)
}

fn sheet_type_from_relationship(relationship_type: &str) -> Result<SheetType> {
    match relationship_type.rsplit('/').next() {
        Some("worksheet") => Ok(SheetType::Worksheet),
        Some("dialogsheet") => Ok(SheetType::DialogSheet),
        Some("macrosheet") => Ok(SheetType::MacroSheet),
        Some("chartsheet") => Ok(SheetType::ChartSheet),
        Some("vbaProject") => Ok(SheetType::Vba),
        _ => Err(Error::stream(format!(
            "unsupported worksheet relationship type '{relationship_type}'"
        ))),
    }
}

fn read_shared_strings<R>(
    archive: &mut ZipArchive<R>,
    options: &ReadOptions,
    allow_disk_cache: bool,
) -> Result<SharedStrings>
where
    R: Read + Seek,
{
    let file = match archive.by_name("xl/sharedStrings.xml") {
        Ok(file) => file,
        Err(ZipError::FileNotFound) => return Ok(SharedStrings::memory()),
        Err(error) => return Err(stream_error("cannot read shared strings:", error)),
    };
    let use_disk = allow_disk_cache
        && options.shared_string_disk_cache()
        && file.size() >= options.shared_string_cache_size();
    let mut strings = if use_disk {
        SharedStrings::disk(options.shared_string_cache_path())?
    } else {
        SharedStrings::memory()
    };
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    let mut current = String::new();
    let mut in_item = false;
    let mut in_text = false;
    loop {
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid shared strings XML:", error))?
        {
            Event::Start(event) if is_name(event.name().as_ref(), b"si") => {
                current.clear();
                in_item = true;
            }
            Event::Empty(event) if is_name(event.name().as_ref(), b"si") => {
                strings.push(String::new())?;
            }
            Event::Start(event) if in_item && is_name(event.name().as_ref(), b"t") => {
                in_text = true;
            }
            Event::Text(text) if in_text => append_text(&text, &mut current)?,
            Event::GeneralRef(reference) if in_text => append_reference(&reference, &mut current)?,
            Event::End(event) if is_name(event.name().as_ref(), b"t") => in_text = false,
            Event::End(event) if is_name(event.name().as_ref(), b"si") => {
                strings.push(decode_excel_escapes(&current))?;
                in_item = false;
            }
            Event::Eof => break,
            _ => {}
        }
        buffer.clear();
    }
    Ok(strings)
}

fn read_styles<R>(archive: &mut ZipArchive<R>, preserve_structure: bool) -> Result<Vec<CellStyle>>
where
    R: Read + Seek,
{
    let file = match archive.by_name("xl/styles.xml") {
        Ok(file) => file,
        Err(ZipError::FileNotFound) => return Ok(Vec::new()),
        Err(error) => return Err(stream_error("cannot read styles:", error)),
    };
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    let mut custom_formats = HashMap::new();
    let mut styles = Vec::new();
    let mut in_cell_formats = false;
    loop {
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid styles XML:", error))?
        {
            Event::Start(event) if is_name(event.name().as_ref(), b"cellXfs") => {
                in_cell_formats = true;
            }
            Event::End(event) if is_name(event.name().as_ref(), b"cellXfs") => {
                in_cell_formats = false;
            }
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"numFmt") =>
            {
                let id = attribute(&event, xml.decoder(), b"numFmtId")?
                    .and_then(|value| value.parse::<u32>().ok());
                let format = attribute(&event, xml.decoder(), b"formatCode")?;
                if let (Some(id), Some(format)) = (id, format) {
                    custom_formats.insert(
                        id,
                        (
                            classify_custom_format(&format),
                            preserve_structure.then(|| Arc::from(format)),
                        ),
                    );
                }
            }
            Event::Start(event) | Event::Empty(event)
                if in_cell_formats && is_name(event.name().as_ref(), b"xf") =>
            {
                let id = attribute(&event, xml.decoder(), b"numFmtId")?
                    .and_then(|value| value.parse::<u32>().ok())
                    .unwrap_or(0);
                let (format, number_format) = custom_formats.get(&id).map_or_else(
                    || {
                        (
                            builtin_format(id),
                            preserve_structure
                                .then(|| builtin_number_format(id).map(Arc::from))
                                .flatten(),
                        )
                    },
                    |(format, number_format)| (*format, number_format.clone()),
                );
                styles.push(CellStyle { format, number_format });
            }
            Event::Eof => break,
            _ => {}
        }
        buffer.clear();
    }
    Ok(styles)
}

#[derive(Clone, Copy, Default)]
enum CellKind {
    #[default]
    Number,
    SharedString,
    InlineString,
    Boolean,
    Error,
    String,
    IsoDate,
}

#[derive(Clone, Copy)]
enum Capture {
    Value,
    InlineText,
    Formula,
}

struct CellState {
    column: usize,
    style: u32,
    kind: CellKind,
    shared_string_index: Option<usize>,
    value: String,
    inline_text: String,
    formula: Option<String>,
    capture: Option<Capture>,
}

struct RowState {
    excel_row: usize,
    cells: Vec<ParsedCell>,
    next_column: usize,
}

struct ParsedCell {
    column: usize,
    value: Data,
    metadata: Option<ParsedCellMetadata>,
}

struct ParsedCellMetadata {
    formula: Option<String>,
    style_id: u32,
    number_format: Option<Arc<str>>,
}

#[derive(Clone, Copy, Default)]
struct WorksheetExtent {
    start_row: Option<usize>,
    start_column: Option<usize>,
    end_row: Option<usize>,
    end_column: Option<usize>,
}

#[derive(Default)]
struct WorksheetScan {
    extent: WorksheetExtent,
    merged_cells: Vec<MergedRange>,
}

#[derive(Clone, Copy)]
struct MergedRange {
    start_row: usize,
    start_column: usize,
    end_row: usize,
    end_column: usize,
}

struct MergeFillState {
    ranges: Vec<MergedRange>,
    anchor_values: Vec<Option<Data>>,
    active_ranges: Vec<usize>,
    next_range: usize,
}

impl MergeFillState {
    fn new(mut ranges: Vec<MergedRange>) -> Self {
        ranges.sort_by_key(|range| range.start_row);
        let anchor_values = vec![None; ranges.len()];
        Self { ranges, anchor_values, active_ranges: Vec::new(), next_range: 0 }
    }

    fn apply(&mut self, row: &mut RowState, start_column: usize, end_column: Option<usize>) {
        while self.ranges.get(self.next_range).is_some_and(|range| range.start_row <= row.excel_row)
        {
            if self.ranges[self.next_range].end_row >= row.excel_row {
                self.active_ranges.push(self.next_range);
            }
            self.next_range += 1;
        }
        self.active_ranges.retain(|index| self.ranges[*index].end_row >= row.excel_row);

        for &index in &self.active_ranges {
            let range = &self.ranges[index];
            if row.excel_row == range.start_row {
                self.anchor_values[index] = row
                    .cells
                    .iter()
                    .find(|cell| cell.column == range.start_column)
                    .map(|cell| cell.value.clone());
            }
            let Some(value) = self.anchor_values[index].as_ref() else {
                continue;
            };
            let first_column = range.start_column.max(start_column);
            let last_column = end_column.map_or(range.end_column, |end| range.end_column.min(end));
            if first_column > last_column {
                continue;
            }
            for column in first_column..=last_column {
                if row.cells.iter().all(|cell| cell.column != column) {
                    row.cells.push(ParsedCell { column, value: value.clone(), metadata: None });
                }
            }
        }
    }
}

fn read_declared_worksheet_extent<R>(
    archive: &mut ZipArchive<R>,
    sheet_path: &str,
) -> Result<Option<WorksheetExtent>>
where
    R: Read + Seek,
{
    let file = archive
        .by_name(sheet_path)
        .map_err(|error| stream_error("cannot read worksheet dimensions:", error))?;
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    loop {
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid worksheet XML dimensions:", error))?
        {
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"dimension") =>
            {
                let reference = attribute(&event, xml.decoder(), b"ref")?
                    .ok_or_else(|| Error::stream("worksheet dimension has no reference"))?;
                let mut cells = reference.split(':');
                let start = cells
                    .next()
                    .ok_or_else(|| Error::stream("worksheet dimension is empty"))?
                    .parse::<CellReference>()?;
                let end = cells.next().unwrap_or(&reference).parse::<CellReference>()?;
                return Ok(Some(WorksheetExtent {
                    start_row: Some(start.row()),
                    start_column: Some(start.column()),
                    end_row: Some(end.row()),
                    end_column: Some(end.column()),
                }));
            }
            Event::Start(event) if is_name(event.name().as_ref(), b"sheetData") => return Ok(None),
            Event::Eof => return Ok(None),
            _ => {}
        }
        buffer.clear();
    }
}

fn prepare_query_scan<R>(
    archive: &mut ZipArchive<R>,
    sheet_path: &str,
    options: &ReadOptions,
    preserve_structure: bool,
    cancelled: &AtomicBool,
) -> Result<WorksheetScan>
where
    R: Read + Seek,
{
    if !options.fill_merged_cells() || preserve_structure {
        if options.end_cell().is_some() {
            return Ok(WorksheetScan::default());
        }
        if let Ok(Some(extent)) = read_declared_worksheet_extent(archive, sheet_path) {
            return Ok(WorksheetScan { extent, merged_cells: Vec::new() });
        }
    }
    scan_worksheet(archive, sheet_path, cancelled)
}

fn scan_worksheet<R>(
    archive: &mut ZipArchive<R>,
    sheet_path: &str,
    cancelled: &AtomicBool,
) -> Result<WorksheetScan>
where
    R: Read + Seek,
{
    let file = archive
        .by_name(sheet_path)
        .map_err(|error| stream_error("cannot scan worksheet XML:", error))?;
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    let mut scan = WorksheetScan::default();
    let mut current_row = None;
    let mut last_declared_row = None;
    let mut next_column = 0;
    let mut in_sheet_data = false;

    loop {
        if cancelled.load(Ordering::Relaxed) {
            return Ok(scan);
        }
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid worksheet XML during scan:", error))?
        {
            Event::Start(event) if is_name(event.name().as_ref(), b"sheetData") => {
                in_sheet_data = true;
            }
            Event::End(event) if is_name(event.name().as_ref(), b"sheetData") => {
                in_sheet_data = false;
                current_row = None;
            }
            Event::Start(event) | Event::Empty(event)
                if in_sheet_data && is_name(event.name().as_ref(), b"row") =>
            {
                let row = row_index(&event, xml.decoder(), last_declared_row)?;
                current_row = Some(row);
                last_declared_row = Some(row);
                scan.extent.start_row =
                    Some(scan.extent.start_row.map_or(row, |start| start.min(row)));
                scan.extent.end_row = Some(scan.extent.end_row.map_or(row, |end| end.max(row)));
                next_column = 0;
            }
            Event::Start(event) | Event::Empty(event)
                if current_row.is_some() && is_name(event.name().as_ref(), b"c") =>
            {
                let column = attribute(&event, xml.decoder(), b"r")?
                    .and_then(|reference| parse_column(&reference))
                    .unwrap_or(next_column);
                next_column = column.saturating_add(1);
                scan.extent.start_column =
                    Some(scan.extent.start_column.map_or(column, |start| start.min(column)));
                scan.extent.end_column =
                    Some(scan.extent.end_column.map_or(column, |end| end.max(column)));
            }
            Event::End(event) if is_name(event.name().as_ref(), b"row") => {
                current_row = None;
            }
            Event::Start(event) | Event::Empty(event)
                if is_name(event.name().as_ref(), b"mergeCell") =>
            {
                let reference = attribute(&event, xml.decoder(), b"ref")?
                    .ok_or_else(|| Error::stream("merged cell has no reference"))?;
                let range = parse_merged_range(&reference)?;
                scan.extent.start_row = Some(
                    scan.extent.start_row.map_or(range.start_row, |row| row.min(range.start_row)),
                );
                scan.extent.end_row =
                    Some(scan.extent.end_row.map_or(range.end_row, |row| row.max(range.end_row)));
                scan.extent.start_column = Some(
                    scan.extent
                        .start_column
                        .map_or(range.start_column, |column| column.min(range.start_column)),
                );
                scan.extent.end_column = Some(
                    scan.extent
                        .end_column
                        .map_or(range.end_column, |column| column.max(range.end_column)),
                );
                scan.merged_cells.push(range);
            }
            Event::Eof => break,
            _ => {}
        }
        buffer.clear();
    }
    Ok(scan)
}

fn parse_merged_range(reference: &str) -> Result<MergedRange> {
    let (start, end) = reference.split_once(':').unwrap_or((reference, reference));
    let start = start.parse::<CellReference>()?;
    let end = end.parse::<CellReference>()?;
    if end.row() < start.row() || end.column() < start.column() {
        return Err(Error::stream(format!("invalid merged-cell range '{reference}'")));
    }
    Ok(MergedRange {
        start_row: start.row(),
        start_column: start.column(),
        end_row: end.row(),
        end_column: end.column(),
    })
}

fn stream_worksheet<R, F>(
    archive: &mut ZipArchive<R>,
    context: WorkbookContext,
    scan: WorksheetScan,
    options: &ReadOptions,
    cancelled: &AtomicBool,
    emit: &mut F,
) -> Result<()>
where
    R: Read + Seek,
    F: FnMut(SelectedRow) -> bool,
{
    let file = archive
        .by_name(&context.sheet_path)
        .map_err(|error| stream_error("cannot read worksheet XML:", error))?;
    let mut xml = Reader::from_reader(BufReader::new(file));
    let mut buffer = Vec::new();
    let mut current_row = None;
    let mut current_cell = None;
    let mut last_declared_row = None;
    let mut next_output_row = options.start_cell().row();
    let mut in_sheet_data = false;
    let end_row = options.end_cell().map_or(scan.extent.end_row, |cell| Some(cell.row()));
    let end_column = options.end_cell().map_or(scan.extent.end_column, |cell| Some(cell.column()));
    let row_cell_capacity = end_column
        .and_then(|column| column.checked_sub(options.start_cell().column()))
        .map_or(0, |width| width.saturating_add(1).min(MAX_PREALLOCATED_ROW_CELLS));
    let mut merge_fill = (options.fill_merged_cells() && !context.preserve_structure)
        .then(|| MergeFillState::new(scan.merged_cells));

    loop {
        if cancelled.load(Ordering::Relaxed) {
            return Ok(());
        }
        match xml
            .read_event_into(&mut buffer)
            .map_err(|error| stream_error("invalid worksheet XML:", error))?
        {
            Event::Start(event) if is_name(event.name().as_ref(), b"sheetData") => {
                in_sheet_data = true;
            }
            Event::End(event) if is_name(event.name().as_ref(), b"sheetData") => break,
            Event::Start(event) if in_sheet_data && is_name(event.name().as_ref(), b"row") => {
                let excel_row = row_index(&event, xml.decoder(), last_declared_row)?;
                if end_row.is_none_or(|end_row| excel_row > end_row) {
                    break;
                }
                if !emit_missing_rows(
                    &mut next_output_row,
                    excel_row,
                    end_column,
                    options,
                    &mut merge_fill,
                    emit,
                ) {
                    return Ok(());
                }
                last_declared_row = Some(excel_row);
                current_row = Some(RowState {
                    excel_row,
                    cells: Vec::with_capacity(row_cell_capacity),
                    next_column: 0,
                });
            }
            Event::Empty(event) if in_sheet_data && is_name(event.name().as_ref(), b"row") => {
                let excel_row = row_index(&event, xml.decoder(), last_declared_row)?;
                if end_row.is_none_or(|end_row| excel_row > end_row) {
                    break;
                }
                if !emit_missing_rows(
                    &mut next_output_row,
                    excel_row,
                    end_column,
                    options,
                    &mut merge_fill,
                    emit,
                ) {
                    return Ok(());
                }
                last_declared_row = Some(excel_row);
                let row = RowState { excel_row, cells: Vec::new(), next_column: 0 };
                if !emit_row(row, &mut next_output_row, end_column, options, &mut merge_fill, emit)
                {
                    return Ok(());
                }
            }
            Event::Start(event)
                if current_row.is_some() && is_name(event.name().as_ref(), b"c") =>
            {
                current_cell = Some(start_cell(
                    &event,
                    xml.decoder(),
                    current_row.as_mut().expect("row checked above"),
                )?);
            }
            Event::Empty(event)
                if current_row.is_some() && is_name(event.name().as_ref(), b"c") =>
            {
                let cell = start_cell(
                    &event,
                    xml.decoder(),
                    current_row.as_mut().expect("row checked above"),
                )?;
                finish_cell(cell, current_row.as_mut().expect("row checked above"), &context)?;
            }
            Event::Start(event)
                if current_cell.is_some() && is_name(event.name().as_ref(), b"v") =>
            {
                current_cell.as_mut().expect("cell checked above").capture = Some(Capture::Value);
            }
            Event::Start(event)
                if current_cell.is_some() && is_name(event.name().as_ref(), b"t") =>
            {
                current_cell.as_mut().expect("cell checked above").capture =
                    Some(Capture::InlineText);
            }
            Event::Start(event)
                if current_cell.is_some() && is_name(event.name().as_ref(), b"f") =>
            {
                if context.preserve_structure {
                    let cell = current_cell.as_mut().expect("cell checked above");
                    cell.formula = Some(String::new());
                    cell.capture = Some(Capture::Formula);
                }
            }
            Event::Empty(event)
                if current_cell.is_some() && is_name(event.name().as_ref(), b"f") =>
            {
                if context.preserve_structure {
                    current_cell.as_mut().expect("cell checked above").formula =
                        Some(String::new());
                }
            }
            Event::Text(text) if current_cell.is_some() => {
                append_cell_text(&text, current_cell.as_mut().expect("cell checked above"))?;
            }
            Event::GeneralRef(reference) if current_cell.is_some() => {
                append_cell_reference(
                    &reference,
                    current_cell.as_mut().expect("cell checked above"),
                )?;
            }
            Event::End(event)
                if current_cell.is_some()
                    && (is_name(event.name().as_ref(), b"v")
                        || is_name(event.name().as_ref(), b"t")
                        || is_name(event.name().as_ref(), b"f")) =>
            {
                current_cell.as_mut().expect("cell checked above").capture = None;
            }
            Event::End(event) if is_name(event.name().as_ref(), b"c") => {
                if let (Some(cell), Some(row)) = (current_cell.take(), current_row.as_mut()) {
                    finish_cell(cell, row, &context)?;
                }
            }
            Event::End(event) if is_name(event.name().as_ref(), b"row") => {
                if let Some(row) = current_row.take() {
                    if !emit_row(
                        row,
                        &mut next_output_row,
                        end_column,
                        options,
                        &mut merge_fill,
                        emit,
                    ) {
                        return Ok(());
                    }
                }
            }
            Event::Eof => break,
            _ => {}
        }
        buffer.clear();
    }
    Ok(())
}

fn start_cell(event: &BytesStart<'_>, decoder: Decoder, row: &mut RowState) -> Result<CellState> {
    let mut column = None;
    let mut style = 0;
    let mut kind = CellKind::Number;
    for attribute in event.attributes().with_checks(false) {
        let attribute = attribute.map_err(|error| stream_error("invalid XML attribute:", error))?;
        if !matches!(
            attribute.key.as_ref().rsplit(|byte| *byte == b':').next(),
            Some(b"r" | b"s" | b"t")
        ) {
            continue;
        }
        let value = attribute
            .decode_and_unescape_value(decoder)
            .map_err(|error| stream_error("invalid XML attribute value:", error))?;
        match attribute.key.as_ref().rsplit(|byte| *byte == b':').next() {
            Some(b"r") => column = parse_column(&value),
            Some(b"s") => style = value.parse::<u32>().unwrap_or(0),
            Some(b"t") => {
                kind = match value.as_ref() {
                    "s" => CellKind::SharedString,
                    "inlineStr" => CellKind::InlineString,
                    "b" => CellKind::Boolean,
                    "e" => CellKind::Error,
                    "str" => CellKind::String,
                    "d" => CellKind::IsoDate,
                    _ => CellKind::Number,
                };
            }
            _ => {}
        }
    }
    let column = column.unwrap_or(row.next_column);
    row.next_column = column.saturating_add(1);
    Ok(CellState {
        column,
        style,
        kind,
        shared_string_index: None,
        value: String::new(),
        inline_text: String::new(),
        formula: None,
        capture: None,
    })
}

fn finish_cell(cell: CellState, row: &mut RowState, context: &WorkbookContext) -> Result<()> {
    let CellState {
        column,
        style,
        kind,
        shared_string_index,
        value,
        inline_text,
        formula,
        capture: _,
    } = cell;
    let cell_style = context.styles.get(style as usize);
    let format = cell_style.map_or(CellFormat::Other, |style| style.format);
    let number_format = cell_style.and_then(|style| style.number_format.clone());
    let data = match kind {
        CellKind::SharedString => {
            if let Some(index) = shared_string_index {
                Data::String(context.shared_strings.get(index)?.ok_or_else(|| {
                    Error::stream(format!("shared string index {index} is out of range"))
                })?)
            } else if value.is_empty() {
                Data::Empty
            } else {
                let index = value
                    .parse::<usize>()
                    .map_err(|error| stream_error("invalid shared string index:", error))?;
                Data::String(context.shared_strings.get(index)?.ok_or_else(|| {
                    Error::stream(format!("shared string index {index} is out of range"))
                })?)
            }
        }
        CellKind::InlineString => Data::String(decode_excel_escapes(&inline_text)),
        CellKind::Boolean => Data::Bool(value == "1" || value.eq_ignore_ascii_case("true")),
        CellKind::Error => Data::Error(parse_cell_error(&value)?),
        CellKind::String => Data::String(decode_excel_escapes(&value)),
        CellKind::IsoDate => Data::DateTimeIso(value),
        CellKind::Number if value.is_empty() => Data::Empty,
        CellKind::Number => {
            let value = value
                .parse::<f64>()
                .map_err(|error| stream_error("invalid numeric cell value:", error))?;
            match format {
                CellFormat::DateTime => Data::DateTime(ExcelDateTime::new(
                    value,
                    ExcelDateTimeType::DateTime,
                    context.is_1904,
                )),
                CellFormat::TimeDelta => Data::DateTime(ExcelDateTime::new(
                    value,
                    ExcelDateTimeType::TimeDelta,
                    context.is_1904,
                )),
                CellFormat::Other => Data::Float(value),
            }
        }
    };
    let metadata = context.preserve_structure.then_some(ParsedCellMetadata {
        formula,
        style_id: style,
        number_format,
    });
    row.cells.push(ParsedCell { column, value: data, metadata });
    Ok(())
}

fn emit_missing_rows<F>(
    next_output_row: &mut usize,
    target_row: usize,
    end_column: Option<usize>,
    options: &ReadOptions,
    merge_fill: &mut Option<MergeFillState>,
    emit: &mut F,
) -> bool
where
    F: FnMut(SelectedRow) -> bool,
{
    if options.ignore_empty_rows() && merge_fill.is_none() {
        *next_output_row = (*next_output_row).max(target_row);
        return true;
    }
    while *next_output_row < target_row {
        let row = RowState { excel_row: *next_output_row, cells: Vec::new(), next_column: 0 };
        if !emit_row(row, next_output_row, end_column, options, merge_fill, emit) {
            return false;
        }
    }
    true
}

fn emit_row<F>(
    mut row: RowState,
    next_output_row: &mut usize,
    end_column: Option<usize>,
    options: &ReadOptions,
    merge_fill: &mut Option<MergeFillState>,
    emit: &mut F,
) -> bool
where
    F: FnMut(SelectedRow) -> bool,
{
    if let Some(merge_fill) = merge_fill {
        merge_fill.apply(&mut row, options.start_cell().column(), end_column);
    }
    *next_output_row = (*next_output_row).max(row.excel_row.saturating_add(1));
    if row.excel_row < options.start_cell().row() {
        return true;
    }
    let start_column = options.start_cell().column();
    let width = end_column
        .filter(|column| *column >= start_column)
        .map_or(0, |column| column - start_column + 1);
    let mut values = vec![Data::Empty; width];
    let mut cells = Vec::new();
    for cell in row.cells {
        if cell.column >= start_column && end_column.is_some_and(|end| cell.column <= end) {
            values[cell.column - start_column] = cell.value;
            if let Some(metadata) = cell.metadata {
                cells.push(SelectedCellMetadata {
                    excel_column: cell.column,
                    formula: metadata.formula,
                    style_id: metadata.style_id,
                    number_format: metadata.number_format,
                });
            }
        }
    }
    if options.ignore_empty_rows() && values.iter().all(DataType::is_empty) {
        return true;
    }
    emit(SelectedRow { excel_row: row.excel_row, start_column, values, cells })
}

fn validate_range(options: &ReadOptions) -> Result<()> {
    let Some(end_cell) = options.end_cell() else {
        return Ok(());
    };
    let start_cell = options.start_cell();
    if end_cell.row() < start_cell.row() || end_cell.column() < start_cell.column() {
        return Err(Error::invalid_cell_range(start_cell.to_string(), end_cell.to_string()));
    }
    Ok(())
}

fn row_index(event: &BytesStart<'_>, decoder: Decoder, previous: Option<usize>) -> Result<usize> {
    for attribute in event.attributes().with_checks(false) {
        let attribute = attribute.map_err(|error| stream_error("invalid XML attribute:", error))?;
        if is_name(attribute.key.as_ref(), b"r") {
            let value = attribute
                .decode_and_unescape_value(decoder)
                .map_err(|error| stream_error("invalid XML attribute value:", error))?;
            if let Some(row) = value.parse::<usize>().ok().and_then(|value| value.checked_sub(1)) {
                return Ok(row);
            }
            break;
        }
    }
    Ok(previous.map_or(0, |row| row.saturating_add(1)))
}

fn append_cell_text(text: &quick_xml::events::BytesText<'_>, cell: &mut CellState) -> Result<()> {
    match cell.capture {
        Some(Capture::Value) if matches!(cell.kind, CellKind::SharedString) => {
            append_shared_string_index(text, &mut cell.shared_string_index)
        }
        Some(Capture::Value) => append_text(text, &mut cell.value),
        Some(Capture::InlineText) => append_text(text, &mut cell.inline_text),
        Some(Capture::Formula) => {
            append_text(text, cell.formula.as_mut().expect("formula capture initializes storage"))
        }
        None => Ok(()),
    }
}

fn append_shared_string_index(
    text: &quick_xml::events::BytesText<'_>,
    target: &mut Option<usize>,
) -> Result<()> {
    let decoded = text
        .xml10_content()
        .map_err(|error| stream_error("invalid shared string index:", error))?;
    let mut index = target.unwrap_or(0);
    for byte in decoded.bytes() {
        let digit = byte
            .checked_sub(b'0')
            .filter(|digit| *digit <= 9)
            .ok_or_else(|| Error::stream(format!("invalid shared string index '{decoded}'")))?;
        index = index
            .checked_mul(10)
            .and_then(|value| value.checked_add(usize::from(digit)))
            .ok_or_else(|| {
                Error::stream(format!("shared string index '{decoded}' is too large"))
            })?;
    }
    if !decoded.is_empty() {
        *target = Some(index);
    }
    Ok(())
}

fn append_cell_reference(reference: &BytesRef<'_>, cell: &mut CellState) -> Result<()> {
    match cell.capture {
        Some(Capture::Value) => append_reference(reference, &mut cell.value),
        Some(Capture::InlineText) => append_reference(reference, &mut cell.inline_text),
        Some(Capture::Formula) => append_reference(
            reference,
            cell.formula.as_mut().expect("formula capture initializes storage"),
        ),
        None => Ok(()),
    }
}

fn append_text(text: &quick_xml::events::BytesText<'_>, target: &mut String) -> Result<()> {
    let text = text.xml10_content().map_err(|error| stream_error("invalid XML text:", error))?;
    target.push_str(&text);
    Ok(())
}

fn append_reference(reference: &BytesRef<'_>, target: &mut String) -> Result<()> {
    let decoded =
        reference.decode().map_err(|error| stream_error("invalid XML reference:", error))?;
    match decoded.as_ref() {
        "lt" => target.push('<'),
        "gt" => target.push('>'),
        "amp" => target.push('&'),
        "quot" => target.push('"'),
        "apos" => target.push('\''),
        _ => {
            if let Some(value) = reference
                .resolve_char_ref()
                .map_err(|error| stream_error("invalid XML character reference:", error))?
            {
                target.push(value);
            } else {
                return Err(Error::stream(format!("unrecognized XML entity '&{decoded};'")));
            }
        }
    }
    Ok(())
}

fn attribute(event: &BytesStart<'_>, decoder: Decoder, name: &[u8]) -> Result<Option<String>> {
    for attribute in event.attributes().with_checks(false) {
        let attribute = attribute.map_err(|error| stream_error("invalid XML attribute:", error))?;
        if is_name(attribute.key.as_ref(), name) {
            return attribute
                .decode_and_unescape_value(decoder)
                .map(|value| Some(value.into_owned()))
                .map_err(|error| stream_error("invalid XML attribute value:", error));
        }
    }
    Ok(None)
}

fn is_name(actual: &[u8], expected: &[u8]) -> bool {
    actual.rsplit(|byte| *byte == b':').next() == Some(expected)
}

fn normalize_zip_path(target: &str) -> String {
    let target = target.replace('\\', "/");
    let path = if target.starts_with('/') {
        target.trim_start_matches('/').to_owned()
    } else if target.starts_with("xl/") {
        target
    } else {
        format!("xl/{target}")
    };
    let mut parts = Vec::new();
    for part in path.split('/') {
        match part {
            "" | "." => {}
            ".." => {
                parts.pop();
            }
            _ => parts.push(part),
        }
    }
    parts.join("/")
}

fn parse_column(reference: &str) -> Option<usize> {
    let mut column = 0usize;
    let mut found = false;
    for byte in reference.bytes() {
        if byte == b'$' && !found {
            continue;
        }
        if !byte.is_ascii_alphabetic() {
            break;
        }
        found = true;
        column = column
            .checked_mul(26)?
            .checked_add(usize::from(byte.to_ascii_uppercase() - b'A' + 1))?;
    }
    found.then(|| column - 1).filter(|column| *column <= MAX_EXCEL_COLUMN)
}

fn parse_cell_error(value: &str) -> Result<CellErrorType> {
    match value {
        "#DIV/0!" => Ok(CellErrorType::Div0),
        "#N/A" => Ok(CellErrorType::NA),
        "#NAME?" => Ok(CellErrorType::Name),
        "#NULL!" => Ok(CellErrorType::Null),
        "#NUM!" => Ok(CellErrorType::Num),
        "#REF!" => Ok(CellErrorType::Ref),
        "#VALUE!" => Ok(CellErrorType::Value),
        "#DATA!" | "#GETTING_DATA" => Ok(CellErrorType::GettingData),
        _ => Err(Error::stream(format!("unknown Excel cell error '{value}'"))),
    }
}

fn builtin_format(id: u32) -> CellFormat {
    match id {
        14..=22 | 45 | 47 => CellFormat::DateTime,
        46 => CellFormat::TimeDelta,
        _ => CellFormat::Other,
    }
}

fn builtin_number_format(id: u32) -> Option<&'static str> {
    match id {
        0 => Some("General"),
        1 => Some("0"),
        2 => Some("0.00"),
        3 => Some("#,##0"),
        4 => Some("#,##0.00"),
        9 => Some("0%"),
        10 => Some("0.00%"),
        11 => Some("0.00E+00"),
        12 => Some("# ?/?"),
        13 => Some("# ??/??"),
        14 => Some("mm-dd-yy"),
        15 => Some("d-mmm-yy"),
        16 => Some("d-mmm"),
        17 => Some("mmm-yy"),
        18 => Some("h:mm AM/PM"),
        19 => Some("h:mm:ss AM/PM"),
        20 => Some("h:mm"),
        21 => Some("h:mm:ss"),
        22 => Some("m/d/yy h:mm"),
        37 => Some("#,##0 ;(#,##0)"),
        38 => Some("#,##0 ;[Red](#,##0)"),
        39 => Some("#,##0.00;(#,##0.00)"),
        40 => Some("#,##0.00;[Red](#,##0.00)"),
        45 => Some("mm:ss"),
        46 => Some("[h]:mm:ss"),
        47 => Some("mmss.0"),
        48 => Some("##0.0E+0"),
        49 => Some("@"),
        _ => None,
    }
}

fn classify_custom_format(format: &str) -> CellFormat {
    let characters = format.as_bytes();
    let mut index = 0;
    while index < characters.len() {
        match characters[index] {
            b';' => break,
            b'\\' | b'_' | b'*' => index = index.saturating_add(2),
            b'"' => {
                index += 1;
                while index < characters.len() && characters[index] != b'"' {
                    index += 1;
                }
                index = index.saturating_add(1);
            }
            b'[' => {
                let start = index + 1;
                index = start;
                while index < characters.len() && characters[index] != b']' {
                    index += 1;
                }
                let token = &format[start..index];
                if !token.is_empty()
                    && token
                        .bytes()
                        .all(|byte| matches!(byte.to_ascii_lowercase(), b'h' | b'm' | b's'))
                {
                    return CellFormat::TimeDelta;
                }
                index = index.saturating_add(1);
            }
            byte if matches!(byte.to_ascii_lowercase(), b'd' | b'm' | b'y' | b'h' | b's') => {
                return CellFormat::DateTime;
            }
            _ => index += 1,
        }
    }
    CellFormat::Other
}

fn decode_excel_escapes(value: &str) -> String {
    let bytes = value.as_bytes();
    let mut result = String::with_capacity(value.len());
    let mut index = 0;
    while index < bytes.len() {
        if index + 7 <= bytes.len()
            && bytes[index] == b'_'
            && matches!(bytes[index + 1], b'x' | b'X')
            && bytes[index + 6] == b'_'
        {
            if let Ok(code) = u16::from_str_radix(&value[index + 2..index + 6], 16) {
                if let Some(character) = char::from_u32(u32::from(code)) {
                    result.push(character);
                    index += 7;
                    continue;
                }
            }
        }
        let character = value[index..].chars().next().expect("index is in bounds");
        result.push(character);
        index += character.len_utf8();
    }
    result
}

fn stream_error(context: impl std::fmt::Display, error: impl std::fmt::Display) -> Error {
    Error::stream(format!("{context} {error}"))
}

#[cfg(test)]
mod tests {
    use std::io::{Cursor, Write};

    use zip::write::SimpleFileOptions;
    use zip::{ZipArchive, ZipWriter};

    use super::{
        CellFormat, classify_custom_format, parse_column, prepare_query_scan, scan_worksheet,
    };
    use crate::ReadOptions;

    #[test]
    fn classifies_custom_excel_number_formats() {
        assert_eq!(classify_custom_format("yyyy-mm-dd"), CellFormat::DateTime);
        assert_eq!(classify_custom_format("h:mm AM/PM"), CellFormat::DateTime);
        assert_eq!(classify_custom_format("[h]:mm:ss"), CellFormat::TimeDelta);
        assert_eq!(classify_custom_format("0.00"), CellFormat::Other);
        assert_eq!(classify_custom_format("[Red][>=100]0.00"), CellFormat::Other);
        assert_eq!(classify_custom_format("\"days\" 0"), CellFormat::Other);
    }

    #[test]
    fn rejects_columns_beyond_excel_limits() {
        assert_eq!(parse_column("XFD1048576"), Some(16_383));
        assert_eq!(parse_column("XFE1"), None);
        assert_eq!(parse_column("ZZZZ1"), None);
    }

    #[test]
    fn query_scan_uses_declared_extent_without_scanning_the_worksheet() {
        let mut writer = ZipWriter::new(Cursor::new(Vec::new()));
        writer.start_file("sheet.xml", SimpleFileOptions::default()).unwrap();
        writer
            .write_all(
                br#"<worksheet><dimension ref="A1:J100000"/><sheetData/><broken attribute=""#,
            )
            .unwrap();
        let bytes = writer.finish().unwrap().into_inner();
        let mut archive = ZipArchive::new(Cursor::new(bytes)).unwrap();
        let cancelled = std::sync::atomic::AtomicBool::new(false);

        assert!(scan_worksheet(&mut archive, "sheet.xml", &cancelled).is_err());
        let scan = prepare_query_scan(
            &mut archive,
            "sheet.xml",
            &ReadOptions::default(),
            false,
            &cancelled,
        )
        .unwrap();

        assert_eq!(scan.extent.start_row, Some(0));
        assert_eq!(scan.extent.start_column, Some(0));
        assert_eq!(scan.extent.end_row, Some(99_999));
        assert_eq!(scan.extent.end_column, Some(9));
    }
}