formualizer_parse/

parser.rs

use crate::ParserLimits;
use crate::structured_ref;
use crate::tokenizer::{
    Associativity, Token, TokenSpan, TokenStream, TokenSubType, TokenType, TokenizerError,
};
use crate::types::{FormulaDialect, ParsingError};
use crate::{ExcelError, LiteralValue};

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

use crate::hasher::FormulaHasher;
use formualizer_common::coord::{
    col_index_from_letters_1based, col_letters_from_1based, parse_a1_1based,
};
use formualizer_common::{
    AxisBound, RelativeCoord, SheetCellRef, SheetLocator, SheetRangeRef, SheetRef,
};
use once_cell::sync::Lazy;
use smallvec::SmallVec;
use std::borrow::Cow;
use std::error::Error;
use std::fmt::{self, Display};
use std::hash::{Hash, Hasher};
use std::str::FromStr;
use std::sync::Arc;

type VolatilityFn = dyn Fn(&str) -> bool + Send + Sync + 'static;
type VolatilityClassifierBox = Box<VolatilityFn>;
type VolatilityClassifierArc = Arc<VolatilityFn>;

/// A custom error type for the parser.
#[derive(Debug)]
pub struct ParserError {
    pub message: String,
    /// Byte offset into the formula source where the error was found, when
    /// known. At the end of the input it is the source length.
    pub position: Option<usize>,
}

impl Display for ParserError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Some(pos) = self.position {
            write!(f, "ParserError at position {}: {}", pos, self.message)
        } else {
            write!(f, "ParserError: {}", self.message)
        }
    }
}

impl Error for ParserError {}

// Column lookup table for common columns (A-ZZ = 702 columns)
static COLUMN_LOOKUP: Lazy<Vec<String>> = Lazy::new(|| {
    let mut cols = Vec::with_capacity(702);
    // Single letters A-Z
    for c in b'A'..=b'Z' {
        cols.push(String::from(c as char));
    }
    // Double letters AA-ZZ
    for c1 in b'A'..=b'Z' {
        for c2 in b'A'..=b'Z' {
            cols.push(format!("{}{}", c1 as char, c2 as char));
        }
    }
    cols
});

/// A structured table reference specifier for accessing specific parts of a table
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq, Hash)]
pub enum TableSpecifier {
    /// The entire table
    All,
    /// The data area of the table (no headers or totals)
    Data,
    /// The headers row
    Headers,
    /// The totals row
    Totals,
    /// A specific row
    Row(TableRowSpecifier),
    /// A specific column
    Column(String),
    /// A range of columns
    ColumnRange(String, String),
    /// Special items like #Headers, #Data, #Totals, etc.
    SpecialItem(SpecialItem),
    /// A combination of specifiers, for complex references
    Combination(Vec<Box<TableSpecifier>>),
}

/// Specifies which row(s) to use in a table reference
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq, Hash)]
pub enum TableRowSpecifier {
    /// The current row (context dependent)
    Current,
    /// All rows
    All,
    /// Data rows only
    Data,
    /// Headers row
    Headers,
    /// Totals row
    Totals,
    /// Specific row by index (1-based)
    Index(u32),
}

/// Special items in structured references
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq, Hash)]
pub enum SpecialItem {
    /// The #Headers item
    Headers,
    /// The #Data item
    Data,
    /// The #Totals item
    Totals,
    /// The #All item (the whole table)
    All,
    /// The @ item (current row)
    ThisRow,
}

/// A reference to a table including specifiers
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq, Hash)]
pub struct TableReference {
    /// The name of the table
    pub name: String,
    /// Optional specifier for which part of the table to use
    pub specifier: Option<TableSpecifier>,
}

#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq, Hash)]
pub enum ExternalBookRef {
    Token(String),
}

impl ExternalBookRef {
    pub fn token(&self) -> &str {
        match self {
            ExternalBookRef::Token(s) => s,
        }
    }
}

#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum ExternalRefKind {
    Cell {
        row: u32,
        col: u32,
        row_abs: bool,
        col_abs: bool,
    },
    Range {
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
        start_row_abs: bool,
        start_col_abs: bool,
        end_row_abs: bool,
        end_col_abs: bool,
    },
}

impl ExternalRefKind {
    pub fn cell(row: u32, col: u32) -> Self {
        Self::Cell {
            row,
            col,
            row_abs: false,
            col_abs: false,
        }
    }

    pub fn cell_with_abs(row: u32, col: u32, row_abs: bool, col_abs: bool) -> Self {
        Self::Cell {
            row,
            col,
            row_abs,
            col_abs,
        }
    }

    pub fn range(
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
    ) -> Self {
        Self::Range {
            start_row,
            start_col,
            end_row,
            end_col,
            start_row_abs: false,
            start_col_abs: false,
            end_row_abs: false,
            end_col_abs: false,
        }
    }

    #[expect(
        clippy::too_many_arguments,
        reason = "constructor mirroring the enum fields; an explicit signature keeps callers readable"
    )]
    pub fn range_with_abs(
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
        start_row_abs: bool,
        start_col_abs: bool,
        end_row_abs: bool,
        end_col_abs: bool,
    ) -> Self {
        Self::Range {
            start_row,
            start_col,
            end_row,
            end_col,
            start_row_abs,
            start_col_abs,
            end_row_abs,
            end_col_abs,
        }
    }
}

#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq, Hash)]
pub struct ExternalReference {
    pub raw: String,
    pub book: ExternalBookRef,
    pub sheet: String,
    pub kind: ExternalRefKind,
}

/// A reference to something outside the cell.
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq, Hash)]
pub enum ReferenceType {
    Cell {
        sheet: Option<String>,
        row: u32,
        col: u32,
        row_abs: bool,
        col_abs: bool,
    },
    Range {
        sheet: Option<String>,
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
        start_row_abs: bool,
        start_col_abs: bool,
        end_row_abs: bool,
        end_col_abs: bool,
    },
    /// 3D cell reference (`Sheet1:Sheet3!A1`).
    ///
    /// Excel evaluates aggregating functions across each sheet between
    /// `sheet_first` and `sheet_last` (inclusive) at the same cell address.
    Cell3D {
        sheet_first: String,
        sheet_last: String,
        row: u32,
        col: u32,
        row_abs: bool,
        col_abs: bool,
    },
    /// 3D range reference (`Sheet1:Sheet3!A1:B2`).
    Range3D {
        sheet_first: String,
        sheet_last: String,
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
        start_row_abs: bool,
        start_col_abs: bool,
        end_row_abs: bool,
        end_col_abs: bool,
    },
    External(ExternalReference),
    Table(TableReference),
    NamedRange(String),
}

impl Display for TableSpecifier {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            TableSpecifier::All => write!(f, "#All"),
            TableSpecifier::Data => write!(f, "#Data"),
            TableSpecifier::Headers => write!(f, "#Headers"),
            TableSpecifier::Totals => write!(f, "#Totals"),
            TableSpecifier::Row(row) => write!(f, "{row}"),
            TableSpecifier::Column(column) => write!(f, "{column}"),
            TableSpecifier::ColumnRange(start, end) => write!(f, "{start}:{end}"),
            TableSpecifier::SpecialItem(item) => write!(f, "{item}"),
            TableSpecifier::Combination(specs) => {
                // Emit nested bracketed parts so the surrounding Table formatter prints
                // canonical structured refs like Table[[#Headers],[Column1]:[Column2]].
                // ColumnRange children must split their bracket boundary across
                // both endpoints (`[A]:[B]`) rather than wrapping the whole
                // range in one bracket pair.
                let mut first = true;
                for spec in specs {
                    if !first {
                        write!(f, ",")?;
                    }
                    first = false;
                    match spec.as_ref() {
                        TableSpecifier::ColumnRange(start, end) => {
                            write!(f, "[{start}]:[{end}]")?;
                        }
                        other => write!(f, "[{other}]")?,
                    }
                }
                Ok(())
            }
        }
    }
}

impl Display for TableRowSpecifier {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            TableRowSpecifier::Current => write!(f, "@"),
            TableRowSpecifier::All => write!(f, "#All"),
            TableRowSpecifier::Data => write!(f, "#Data"),
            TableRowSpecifier::Headers => write!(f, "#Headers"),
            TableRowSpecifier::Totals => write!(f, "#Totals"),
            TableRowSpecifier::Index(idx) => write!(f, "{idx}"),
        }
    }
}

impl Display for SpecialItem {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            SpecialItem::Headers => write!(f, "#Headers"),
            SpecialItem::Data => write!(f, "#Data"),
            SpecialItem::Totals => write!(f, "#Totals"),
            SpecialItem::All => write!(f, "#All"),
            SpecialItem::ThisRow => write!(f, "@"),
        }
    }
}

fn sheet_name_needs_quoting(name: &str) -> bool {
    formualizer_common::a1_sheet_name_needs_quoting(name)
}

#[derive(Debug, Clone)]
struct OpenFormulaRefPart {
    sheet: Option<String>,
    coord: String,
}

type AxisPartWithAbs = Option<(u32, bool)>;
type RangePartWithAbs = (AxisPartWithAbs, AxisPartWithAbs);

/// Result of extracting the sheet portion of a reference string.
#[derive(Debug, Clone)]
enum SheetSpec {
    /// No sheet segment was present (e.g. plain `A1`).
    None,
    /// Standard single-sheet reference (`Sheet1!A1`, `'Sheet 1'!A1`).
    Single(String),
    /// Excel 3D sheet range (`Sheet1:Sheet3!A1`, `'Sheet 1':'Sheet 3'!A1`).
    Range { first: String, last: String },
}

impl ReferenceType {
    /// Build a cell reference with relative anchors.
    pub fn cell(sheet: Option<String>, row: u32, col: u32) -> Self {
        Self::Cell {
            sheet,
            row,
            col,
            row_abs: false,
            col_abs: false,
        }
    }

    /// Build a cell reference with explicit anchors.
    pub fn cell_with_abs(
        sheet: Option<String>,
        row: u32,
        col: u32,
        row_abs: bool,
        col_abs: bool,
    ) -> Self {
        Self::Cell {
            sheet,
            row,
            col,
            row_abs,
            col_abs,
        }
    }

    /// Build a range reference with relative anchors.
    pub fn range(
        sheet: Option<String>,
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
    ) -> Self {
        Self::Range {
            sheet,
            start_row,
            start_col,
            end_row,
            end_col,
            start_row_abs: false,
            start_col_abs: false,
            end_row_abs: false,
            end_col_abs: false,
        }
    }

    /// Build a range reference with explicit anchors.
    #[expect(
        clippy::too_many_arguments,
        reason = "constructor mirroring the enum fields; an explicit signature keeps callers readable"
    )]
    pub fn range_with_abs(
        sheet: Option<String>,
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
        start_row_abs: bool,
        start_col_abs: bool,
        end_row_abs: bool,
        end_col_abs: bool,
    ) -> Self {
        Self::Range {
            sheet,
            start_row,
            start_col,
            end_row,
            end_col,
            start_row_abs,
            start_col_abs,
            end_row_abs,
            end_col_abs,
        }
    }

    /// Create a reference from a string such as `A1`, `A:A`, `A1:B2`, or `Table1[Column]`.
    pub fn from_string(reference: &str) -> Result<Self, ParsingError> {
        Self::parse_excel_reference(reference)
    }

    /// Create a reference from a string using the specified formula dialect.
    pub fn from_string_with_dialect(
        reference: &str,
        dialect: FormulaDialect,
    ) -> Result<Self, ParsingError> {
        match dialect {
            FormulaDialect::Excel => Self::parse_excel_reference(reference),
            FormulaDialect::OpenFormula => Self::parse_openformula_reference(reference)
                .or_else(|_| Self::parse_excel_reference(reference)),
        }
    }

    /// Parse a grid reference into a shared SheetRef, preserving $ anchors.
    ///
    /// Only cell and range references are supported. Table and named ranges return an error.
    pub fn parse_sheet_ref(reference: &str) -> Result<SheetRef<'static>, ParsingError> {
        Self::parse_sheet_ref_with_dialect(reference, FormulaDialect::Excel)
    }

    /// Parse a grid reference into a shared SheetRef using the specified dialect.
    pub fn parse_sheet_ref_with_dialect(
        reference: &str,
        dialect: FormulaDialect,
    ) -> Result<SheetRef<'static>, ParsingError> {
        match dialect {
            FormulaDialect::Excel => Self::parse_excel_sheet_ref(reference),
            FormulaDialect::OpenFormula => Self::parse_openformula_sheet_ref(reference)
                .or_else(|_| Self::parse_excel_sheet_ref(reference)),
        }
    }

    /// Lossy conversion from parsed ReferenceType into SheetRef.
    /// External, table, and named ranges are discarded; anchors are preserved.
    pub fn to_sheet_ref_lossy(&self) -> Option<SheetRef<'_>> {
        match self {
            ReferenceType::Cell {
                sheet,
                row,
                col,
                row_abs,
                col_abs,
            } => {
                let row0 = row.checked_sub(1)?;
                let col0 = col.checked_sub(1)?;
                let sheet_loc = match sheet.as_deref() {
                    Some(name) => SheetLocator::from_name(name),
                    None => SheetLocator::Current,
                };
                let coord = RelativeCoord::new(row0, col0, *row_abs, *col_abs);
                Some(SheetRef::Cell(SheetCellRef::new(sheet_loc, coord)))
            }
            ReferenceType::Range {
                sheet,
                start_row,
                start_col,
                end_row,
                end_col,
                start_row_abs,
                start_col_abs,
                end_row_abs,
                end_col_abs,
            } => {
                let sheet_loc = match sheet.as_deref() {
                    Some(name) => SheetLocator::from_name(name),
                    None => SheetLocator::Current,
                };
                let sr = start_row
                    .and_then(|v| v.checked_sub(1).map(|i| AxisBound::new(i, *start_row_abs)));
                if start_row.is_some() && sr.is_none() {
                    return None;
                }
                let sc = start_col
                    .and_then(|v| v.checked_sub(1).map(|i| AxisBound::new(i, *start_col_abs)));
                if start_col.is_some() && sc.is_none() {
                    return None;
                }
                let er =
                    end_row.and_then(|v| v.checked_sub(1).map(|i| AxisBound::new(i, *end_row_abs)));
                if end_row.is_some() && er.is_none() {
                    return None;
                }
                let ec =
                    end_col.and_then(|v| v.checked_sub(1).map(|i| AxisBound::new(i, *end_col_abs)));
                if end_col.is_some() && ec.is_none() {
                    return None;
                }
                let range = SheetRangeRef::from_parts(sheet_loc, sr, sc, er, ec).ok()?;
                Some(SheetRef::Range(range))
            }
            _ => None,
        }
    }

    fn parse_excel_sheet_ref(reference: &str) -> Result<SheetRef<'static>, ParsingError> {
        let (spec, ref_part) = Self::extract_sheet_spec(reference);
        let sheet = match spec {
            SheetSpec::None => None,
            SheetSpec::Single(name) => Some(name),
            SheetSpec::Range { .. } => {
                return Err(ParsingError::InvalidReference(
                    "3D references are not supported for SheetRef".to_string(),
                ));
            }
        };

        if ref_part.contains('[') {
            return Err(ParsingError::InvalidReference(
                "Table references are not supported for SheetRef".to_string(),
            ));
        }

        let sheet_loc: SheetLocator<'static> = match sheet {
            Some(name) => SheetLocator::from_name(name),
            None => SheetLocator::Current,
        };

        if let Some((start, end)) = ref_part.split_once(':') {
            let (start_col, start_row) = Self::parse_range_part_with_abs(start)?;
            let (end_col, end_row) = Self::parse_range_part_with_abs(end)?;

            let start_col = Self::axis_bound_from_1based(start_col)?;
            let start_row = Self::axis_bound_from_1based(start_row)?;
            let end_col = Self::axis_bound_from_1based(end_col)?;
            let end_row = Self::axis_bound_from_1based(end_row)?;

            let range =
                SheetRangeRef::from_parts(sheet_loc, start_row, start_col, end_row, end_col)
                    .map_err(|err| ParsingError::InvalidReference(err.to_string()))?;
            Ok(SheetRef::Range(range))
        } else {
            let (row, col, row_abs, col_abs) = parse_a1_1based(&ref_part)
                .map_err(|err| ParsingError::InvalidReference(err.to_string()))?;
            #[expect(
                clippy::arithmetic_side_effects,
                reason = "parse_a1_1based returns row >= 1 and col >= 1"
            )]
            let coord = RelativeCoord::new(row - 1, col - 1, row_abs, col_abs);
            Ok(SheetRef::Cell(SheetCellRef::new(sheet_loc, coord)))
        }
    }

    fn parse_openformula_sheet_ref(reference: &str) -> Result<SheetRef<'static>, ParsingError> {
        Self::parse_excel_sheet_ref(reference)
    }

    fn axis_bound_from_1based(
        bound: Option<(u32, bool)>,
    ) -> Result<Option<AxisBound>, ParsingError> {
        match bound {
            Some((index, abs)) => AxisBound::from_excel_1based(index, abs)
                .map(Some)
                .map_err(|err| ParsingError::InvalidReference(err.to_string())),
            None => Ok(None),
        }
    }

    #[expect(
        clippy::arithmetic_side_effects,
        clippy::string_slice,
        reason = "cursor bounded by slice length; the column and row runs are sliced at ASCII positions found by the scan"
    )]
    fn parse_range_part_with_abs(part: &str) -> Result<RangePartWithAbs, ParsingError> {
        if let Ok((row, col, row_abs, col_abs)) = parse_a1_1based(part) {
            return Ok((Some((col, col_abs)), Some((row, row_abs))));
        }

        let bytes = part.as_bytes();
        let len = bytes.len();
        let mut i = 0usize;

        let mut col_abs = false;
        let mut row_abs = false;

        if bytes.get(i) == Some(&b'$') {
            col_abs = true;
            i += 1;
        }

        let col_start = i;
        while bytes.get(i).is_some_and(u8::is_ascii_alphabetic) {
            i += 1;
        }

        if i > col_start {
            let col_str = &part[col_start..i];
            let col1 = Self::column_to_number(col_str)?;

            if i == len {
                return Ok((Some((col1, col_abs)), None));
            }

            if bytes.get(i) == Some(&b'$') {
                row_abs = true;
                i += 1;
            }

            if i >= len {
                return Err(ParsingError::InvalidReference(format!(
                    "Invalid range part: {part}"
                )));
            }

            let row_start = i;
            while bytes.get(i).is_some_and(u8::is_ascii_digit) {
                i += 1;
            }

            if row_start == i || i != len {
                return Err(ParsingError::InvalidReference(format!(
                    "Invalid range part: {part}"
                )));
            }

            let row_str = &part[row_start..i];
            let row1 = row_str
                .parse::<u32>()
                .map_err(|_| ParsingError::InvalidReference(format!("Invalid row: {row_str}")))?;
            if row1 == 0 {
                return Err(ParsingError::InvalidReference(format!(
                    "Invalid range part: {part}"
                )));
            }

            return Ok((Some((col1, col_abs)), Some((row1, row_abs))));
        }

        i = 0;
        if bytes.get(i) == Some(&b'$') {
            row_abs = true;
            i += 1;
        }

        let row_start = i;
        while bytes.get(i).is_some_and(u8::is_ascii_digit) {
            i += 1;
        }

        if row_start == i || i != len {
            return Err(ParsingError::InvalidReference(format!(
                "Invalid range part: {part}"
            )));
        }

        let row_str = &part[row_start..i];
        let row1 = row_str
            .parse::<u32>()
            .map_err(|_| ParsingError::InvalidReference(format!("Invalid row: {row_str}")))?;
        if row1 == 0 {
            return Err(ParsingError::InvalidReference(format!(
                "Invalid range part: {part}"
            )));
        }

        Ok((None, Some((row1, row_abs))))
    }

    fn parse_3d_reference(first: &str, last: &str, ref_part: &str) -> Result<Self, ParsingError> {
        if first.is_empty() || last.is_empty() {
            return Err(ParsingError::InvalidReference(format!(
                "3D reference requires two sheet names: {first}:{last}!{ref_part}"
            )));
        }
        if ref_part.is_empty() {
            return Err(ParsingError::InvalidReference(format!(
                "3D reference {first}:{last}! is missing a cell or range"
            )));
        }
        // 3D refs cannot point at structured table tokens.
        if ref_part.contains('[') {
            return Err(ParsingError::InvalidReference(format!(
                "3D reference {first}:{last}!{ref_part} cannot target a table"
            )));
        }

        if let Some((start, end)) = ref_part.split_once(':') {
            let (start_col, start_row) = Self::parse_range_part_with_abs(start)?;
            let (end_col, end_row) = Self::parse_range_part_with_abs(end)?;

            let split = |bound: Option<(u32, bool)>| match bound {
                Some((index, abs)) => (Some(index), abs),
                None => (None, false),
            };
            let (start_col, start_col_abs) = split(start_col);
            let (start_row, start_row_abs) = split(start_row);
            let (end_col, end_col_abs) = split(end_col);
            let (end_row, end_row_abs) = split(end_row);

            Ok(ReferenceType::Range3D {
                sheet_first: first.to_string(),
                sheet_last: last.to_string(),
                start_row,
                start_col,
                end_row,
                end_col,
                start_row_abs,
                start_col_abs,
                end_row_abs,
                end_col_abs,
            })
        } else {
            let (col, row, col_abs, row_abs) =
                Self::parse_cell_reference(ref_part).map_err(|_| {
                    ParsingError::InvalidReference(format!(
                        "Invalid 3D reference target: {ref_part}"
                    ))
                })?;
            Ok(ReferenceType::Cell3D {
                sheet_first: first.to_string(),
                sheet_last: last.to_string(),
                row,
                col,
                row_abs,
                col_abs,
            })
        }
    }

    /// Strip every leading workbook-index-0 qualifier.
    ///
    /// Workbook index 0 is the workbook the formula lives in (external
    /// workbooks are numbered from 1), as Excel stores it in OOXML:
    /// `[0]!Name` is the workbook-scoped `Name`, `[0]Sheet1!A1` is
    /// `Sheet1!A1` and `'[0]Sheet 1'!A1` is `'Sheet 1'!A1`. A prefix is
    /// stripped only while a `!` follows it. This is a loop rather than
    /// recursion so the number of prefixes cannot exhaust the stack, and the
    /// quoted form allocates its result once.
    #[inline]
    fn strip_workbook_zero_prefixes(reference: &str) -> Cow<'_, str> {
        // Almost no reference starts with a workbook-0 qualifier; test the
        // prefix before scanning for `!`.
        if !reference.starts_with("[0]") && !reference.starts_with("'[0]") {
            return Cow::Borrowed(reference);
        }
        Self::strip_workbook_zero_prefixes_slow(reference)
    }

    #[cold]
    #[inline(never)]
    fn strip_workbook_zero_prefixes_slow(reference: &str) -> Cow<'_, str> {
        // `tail` is always a suffix of `reference`, so it contains a `!`
        // exactly when it is longer than the text after the last `!`.
        let Some(after_last_bang) = reference.rsplit_once('!').map(|(_, after)| after.len()) else {
            return Cow::Borrowed(reference);
        };
        let has_bang = |tail: &str| tail.len() > after_last_bang;

        let mut tail = reference;
        // Whether a leading `'` was taken off `tail` (the quoted form).
        let mut quoted = false;
        loop {
            if !quoted
                && let Some(rest) = tail.strip_prefix("[0]")
                && has_bang(rest)
            {
                tail = rest.strip_prefix('!').unwrap_or(rest);
            } else if !quoted
                && let Some(rest) = tail.strip_prefix("'[0]")
                && has_bang(rest)
            {
                quoted = true;
                tail = rest;
            } else if quoted
                && let Some(rest) = tail.strip_prefix("[0]")
                && has_bang(rest)
            {
                tail = rest;
            } else {
                break;
            }
        }
        if quoted {
            Cow::Owned(format!("'{tail}"))
        } else {
            Cow::Borrowed(tail)
        }
    }

    fn parse_excel_reference(reference: &str) -> Result<Self, ParsingError> {
        let reference = Self::strip_workbook_zero_prefixes(reference);
        let reference = reference.as_ref();

        // Excel structured reference shorthands that appear as a single bracketed token.
        //
        // We use these forms to avoid ambiguity with cell refs / named ranges:
        // - `[TableName]` resolves to the table's data body (equivalent to `TableName[#Data]`).
        // - `[@Column]` / `[@[Column Name]]` is a "This Row" selector; it requires table-aware
        //   context during resolution and will be rewritten by the evaluator/graph builder.
        if reference.starts_with('[') && reference.ends_with(']') && !reference.contains('!') {
            return Self::parse_bracketed_structured_reference(reference);
        }

        // Extract sheet specification (none / single / 3D range) if present.
        let (sheet_spec, ref_part) = Self::extract_sheet_spec(reference);

        let sheet = match sheet_spec {
            SheetSpec::None => None,
            SheetSpec::Single(name) => Some(name),
            // 3D references (`Sheet1:Sheet3!A1` / `Sheet1:Sheet3!A1:B2`) take a
            // dedicated path because they cannot reuse the 2D Cell/Range carriers.
            SheetSpec::Range { first, last } => {
                return Self::parse_3d_reference(&first, &last, &ref_part);
            }
        };

        // Table references live in the ref_part (e.g., "Table1[Column]").
        // Sheet names can contain '[' for external workbook refs (e.g., "[1]Sheet1!A1").
        if ref_part.contains('[') {
            // Issue #76: R1C1-shaped operands like `R[1]C[2]`, `R1C[2]`, `RC[1]`
            // contain `[` but are not table references. Without this gate they
            // either misclassify as `Table { name: "R1C", specifier: Column("2") }`
            // or get rejected by the structured-references trailing-garbage check.
            // We don't add an R1C1 dialect; we just refuse to fabricate a table
            // and fall back to the same `NamedRange` outcome that bracket-free
            // R1C1 strings (e.g. `R1C1`, `RC`) already produce.
            if Self::is_r1c1_shape(&ref_part) {
                return Ok(ReferenceType::NamedRange(reference.to_string()));
            }
            return Self::parse_table_reference(&ref_part);
        }

        let external_sheet = sheet.as_deref().and_then(|s| {
            // Excel external workbook refs embed a "[...]" token inside the sheet segment.
            // Use the last '[' to allow paths/URIs that may contain earlier brackets, then
            // take the first ']' after it to avoid being confused by ']' in the sheet name.
            let lb = s.rfind('[')?;
            let (_, sheet_name) = s.get(lb..)?.split_once(']')?;
            // `sheet_name` is a suffix of `s`; what precedes it is the book
            // token through its `]`.
            let token = s.strip_suffix(sheet_name)?;
            if sheet_name.is_empty() {
                None
            } else {
                Some((token, sheet_name))
            }
        });

        if let Some((start, end)) = ref_part.split_once(':') {
            // Range reference
            let (start_col, start_row) = Self::parse_range_part_with_abs(start)?;
            let (end_col, end_row) = Self::parse_range_part_with_abs(end)?;

            let split = |bound: Option<(u32, bool)>| match bound {
                Some((index, abs)) => (Some(index), abs),
                None => (None, false),
            };
            let (start_col, start_col_abs) = split(start_col);
            let (start_row, start_row_abs) = split(start_row);
            let (end_col, end_col_abs) = split(end_col);
            let (end_row, end_row_abs) = split(end_row);

            if let Some((book_token, sheet_name)) = external_sheet {
                Ok(ReferenceType::External(ExternalReference {
                    raw: reference.to_string(),
                    book: ExternalBookRef::Token(book_token.to_string()),
                    sheet: sheet_name.to_string(),
                    kind: ExternalRefKind::Range {
                        start_row,
                        start_col,
                        end_row,
                        end_col,
                        start_row_abs,
                        start_col_abs,
                        end_row_abs,
                        end_col_abs,
                    },
                }))
            } else {
                Ok(ReferenceType::Range {
                    sheet,
                    start_row,
                    start_col,
                    end_row,
                    end_col,
                    start_row_abs,
                    start_col_abs,
                    end_row_abs,
                    end_col_abs,
                })
            }
        } else {
            // Try to parse as a single cell reference
            match Self::parse_cell_reference(&ref_part) {
                Ok((col, row, col_abs, row_abs)) => {
                    if let Some((book_token, sheet_name)) = external_sheet {
                        Ok(ReferenceType::External(ExternalReference {
                            raw: reference.to_string(),
                            book: ExternalBookRef::Token(book_token.to_string()),
                            sheet: sheet_name.to_string(),
                            kind: ExternalRefKind::Cell {
                                row,
                                col,
                                row_abs,
                                col_abs,
                            },
                        }))
                    } else {
                        Ok(ReferenceType::Cell {
                            sheet,
                            row,
                            col,
                            row_abs,
                            col_abs,
                        })
                    }
                }
                Err(_) => {
                    // Treat it as a named range
                    Ok(ReferenceType::NamedRange(reference.to_string()))
                }
            }
        }
    }

    /// Parse a cell reference like "A1" into (column, row) using byte-based parsing.
    fn parse_cell_reference(reference: &str) -> Result<(u32, u32, bool, bool), ParsingError> {
        parse_a1_1based(reference)
            .map(|(row, col, row_abs, col_abs)| (col, row, col_abs, row_abs))
            .map_err(|_| {
                ParsingError::InvalidReference(format!("Invalid cell reference: {reference}"))
            })
    }

    /// Convert a column letter (e.g., "A", "BC") to a column number (1-based) using byte operations.
    pub(crate) fn column_to_number(column: &str) -> Result<u32, ParsingError> {
        col_index_from_letters_1based(column)
            .map_err(|_| ParsingError::InvalidReference(format!("Invalid column: {column}")))
    }

    /// Convert a column number to a column letter using lookup table for common values.
    pub(crate) fn number_to_column(num: u32) -> String {
        if num == 0 {
            return String::new();
        }
        // Use lookup table for common columns (1-702 covers A-ZZ)
        if let Some(letters) = num
            .checked_sub(1)
            .and_then(|index| COLUMN_LOOKUP.get(index as usize))
        {
            return letters.clone();
        }

        col_letters_from_1based(num).unwrap_or_default()
    }

    fn format_col(col: u32, abs: bool) -> String {
        if abs {
            format!("${}", Self::number_to_column(col))
        } else {
            Self::number_to_column(col)
        }
    }

    fn format_row(row: u32, abs: bool) -> String {
        if abs {
            format!("${row}")
        } else {
            row.to_string()
        }
    }
}

impl Display for ReferenceType {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}",
            match self {
                ReferenceType::Cell {
                    sheet,
                    row,
                    col,
                    row_abs,
                    col_abs,
                } => {
                    let col_str = Self::format_col(*col, *col_abs);
                    let row_str = Self::format_row(*row, *row_abs);

                    if let Some(sheet_name) = sheet {
                        format!(
                            "{}!{col_str}{row_str}",
                            formualizer_common::format_a1_sheet_name(sheet_name)
                        )
                    } else {
                        format!("{col_str}{row_str}")
                    }
                }
                ReferenceType::Range {
                    sheet,
                    start_row,
                    start_col,
                    end_row,
                    end_col,
                    start_row_abs,
                    start_col_abs,
                    end_row_abs,
                    end_col_abs,
                } => {
                    // Format start reference
                    let start_ref = match (start_col, start_row) {
                        (Some(col), Some(row)) => format!(
                            "{}{}",
                            Self::format_col(*col, *start_col_abs),
                            Self::format_row(*row, *start_row_abs)
                        ),
                        (Some(col), None) => Self::format_col(*col, *start_col_abs),
                        (None, Some(row)) => Self::format_row(*row, *start_row_abs),
                        (None, None) => "".to_string(), // Should not happen in normal usage
                    };

                    // Format end reference
                    let end_ref = match (end_col, end_row) {
                        (Some(col), Some(row)) => format!(
                            "{}{}",
                            Self::format_col(*col, *end_col_abs),
                            Self::format_row(*row, *end_row_abs)
                        ),
                        (Some(col), None) => Self::format_col(*col, *end_col_abs),
                        (None, Some(row)) => Self::format_row(*row, *end_row_abs),
                        (None, None) => "".to_string(), // Should not happen in normal usage
                    };

                    let range_part = format!("{start_ref}:{end_ref}");

                    if let Some(sheet_name) = sheet {
                        format!(
                            "{}!{range_part}",
                            formualizer_common::format_a1_sheet_name(sheet_name)
                        )
                    } else {
                        range_part
                    }
                }
                ReferenceType::Cell3D {
                    sheet_first,
                    sheet_last,
                    row,
                    col,
                    row_abs,
                    col_abs,
                } => {
                    let col_str = Self::format_col(*col, *col_abs);
                    let row_str = Self::format_row(*row, *row_abs);
                    let prefix = format_3d_sheet_prefix(sheet_first, sheet_last);
                    format!("{prefix}!{col_str}{row_str}")
                }
                ReferenceType::Range3D {
                    sheet_first,
                    sheet_last,
                    start_row,
                    start_col,
                    end_row,
                    end_col,
                    start_row_abs,
                    start_col_abs,
                    end_row_abs,
                    end_col_abs,
                } => {
                    let start_ref = match (start_col, start_row) {
                        (Some(col), Some(row)) => format!(
                            "{}{}",
                            Self::format_col(*col, *start_col_abs),
                            Self::format_row(*row, *start_row_abs)
                        ),
                        (Some(col), None) => Self::format_col(*col, *start_col_abs),
                        (None, Some(row)) => Self::format_row(*row, *start_row_abs),
                        (None, None) => "".to_string(),
                    };
                    let end_ref = match (end_col, end_row) {
                        (Some(col), Some(row)) => format!(
                            "{}{}",
                            Self::format_col(*col, *end_col_abs),
                            Self::format_row(*row, *end_row_abs)
                        ),
                        (Some(col), None) => Self::format_col(*col, *end_col_abs),
                        (None, Some(row)) => Self::format_row(*row, *end_row_abs),
                        (None, None) => "".to_string(),
                    };
                    let range_part = format!("{start_ref}:{end_ref}");
                    let prefix = format_3d_sheet_prefix(sheet_first, sheet_last);
                    format!("{prefix}!{range_part}")
                }
                ReferenceType::External(ext) => ext.raw.clone(),
                ReferenceType::Table(table_ref) => {
                    if let Some(specifier) = &table_ref.specifier {
                        // For table references, we need to handle column specifiers specially
                        // to remove leading/trailing whitespace
                        match specifier {
                            TableSpecifier::Column(column) => {
                                format!("{}[{}]", table_ref.name, column.trim())
                            }
                            TableSpecifier::ColumnRange(start, end) => {
                                format!("{}[{}:{}]", table_ref.name, start.trim(), end.trim())
                            }
                            _ => {
                                // For other specifiers, use the standard formatting
                                format!("{}[{}]", table_ref.name, specifier)
                            }
                        }
                    } else {
                        table_ref.name.clone()
                    }
                }
                ReferenceType::NamedRange(name) => name.clone(),
            }
        )
    }
}

/// Render the `Sheet1:SheetN` portion of a 3D reference. When either name
/// needs quoting, Excel quotes the whole span as one segment
/// (`'Jan 24:Mar 24'!B5`), never each name on its own.
fn format_3d_sheet_prefix(first: &str, last: &str) -> String {
    if sheet_name_needs_quoting(first) || sheet_name_needs_quoting(last) {
        let escaped = format!("{first}:{last}").replace('\'', "''");
        format!("'{escaped}'")
    } else {
        format!("{first}:{last}")
    }
}

impl TryFrom<&str> for ReferenceType {
    type Error = ParsingError;

    fn try_from(value: &str) -> Result<Self, Self::Error> {
        ReferenceType::from_string(value)
    }
}

impl FromStr for ReferenceType {
    type Err = ParsingError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        ReferenceType::from_string(s)
    }
}

impl ReferenceType {
    /// Normalise the reference string (convert to canonical form)
    pub fn normalise(&self) -> String {
        format!("{self}")
    }

    /// Read one sheet-name segment starting at `start`. Returns the parsed
    /// (unescaped) name, the byte offset directly after the closing quote
    /// (when quoted) or the last alphanumeric byte (when bare), and a flag
    /// indicating whether the segment was quoted.
    #[expect(
        clippy::arithmetic_side_effects,
        clippy::string_slice,
        reason = "cursor bounded by slice length; the name is sliced between ASCII quotes or up to an ASCII delimiter"
    )]
    fn read_sheet_segment(reference: &str, start: usize) -> Option<(String, usize, bool)> {
        let bytes = reference.as_bytes();
        let first = *bytes.get(start)?;

        if first == b'\'' {
            // Quoted segment. Excel doubles a literal `'` inside the name.
            let mut i = start + 1;
            let body_start = i;
            while let Some(&b) = bytes.get(i) {
                if b == b'\'' {
                    if bytes.get(i + 1) == Some(&b'\'') {
                        i += 2;
                        continue;
                    }
                    let raw = &reference[body_start..i];
                    let name = raw.replace("''", "'");
                    return Some((name, i + 1, true));
                }
                i += 1;
            }
            None
        } else {
            // Bare segment. Sheet names cannot contain ':', '!', '\'', or any
            // ASCII-whitespace/operator characters in unquoted form.
            let mut i = start;
            while let Some(&b) = bytes.get(i) {
                match b {
                    b':' | b'!' | b'\'' | b' ' | b'\t' | b'\n' | b'\r' => break,
                    _ => i += 1,
                }
            }
            if i == start {
                None
            } else {
                Some((reference[start..i].to_string(), i, false))
            }
        }
    }

    /// Extract sheet specification (none, single sheet, or 3D sheet range)
    /// from a reference string.
    #[expect(
        clippy::arithmetic_side_effects,
        clippy::string_slice,
        reason = "byte offset from ASCII delimiter search: after_first, after_second and bang index ASCII `:` or `!` bytes inside reference"
    )]
    fn extract_sheet_spec(reference: &str) -> (SheetSpec, String) {
        let Some((first_name, after_first, first_quoted)) = Self::read_sheet_segment(reference, 0)
        else {
            // No sheet segment recognised – fall back to looking for a bare
            // `!` separator (e.g. external book tokens such as `[1]Sheet!A1`).
            return Self::extract_sheet_spec_fallback(reference);
        };
        let bytes = reference.as_bytes();

        // 3D form: Name1:Name2!...
        if bytes.get(after_first) == Some(&b':') {
            let second_start = after_first + 1;
            if let Some((second_name, after_second, _)) =
                Self::read_sheet_segment(reference, second_start)
                && bytes.get(after_second) == Some(&b'!')
            {
                let ref_part = reference[after_second + 1..].to_string();
                return (
                    SheetSpec::Range {
                        first: first_name,
                        last: second_name,
                    },
                    ref_part,
                );
            }

            // The reference looks like the start of a 3D ref but the second
            // segment is malformed (e.g. `Sheet1:!A1`). Surface the broken
            // form as a 3D range with an empty `last` so the parser layer
            // can report a precise error rather than silently treating it as
            // a sheet name containing `:`.
            if let Some(bang) = reference
                .get(second_start..)
                .and_then(|rest| rest.find('!'))
            {
                let ref_part = reference[second_start + bang + 1..].to_string();
                return (
                    SheetSpec::Range {
                        first: first_name,
                        last: String::new(),
                    },
                    ref_part,
                );
            }
        }

        // Single-sheet form: Name!...
        if bytes.get(after_first) == Some(&b'!') {
            let ref_part = reference[after_first + 1..].to_string();
            // Excel forbids ':' in sheet names, so one quoted segment holding
            // a single ':' is a 3D span written the way Excel writes it:
            // `'Jan 24:Mar 24'!B5`. A book path (`'C:\x\[Book.xlsx]S'!A1`)
            // is left alone.
            if first_quoted
                && !first_name.contains('[')
                && let Some((first, last)) = first_name.split_once(':')
                && !first.is_empty()
                && !last.is_empty()
                && !last.contains(':')
            {
                return (
                    SheetSpec::Range {
                        first: first.to_string(),
                        last: last.to_string(),
                    },
                    ref_part,
                );
            }
            return (SheetSpec::Single(first_name), ref_part);
        }

        // The leading segment did not terminate in `!`; treat the whole input
        // as if no sheet were present and fall through to the legacy logic.
        Self::extract_sheet_spec_fallback(reference)
    }

    fn extract_sheet_spec_fallback(reference: &str) -> (SheetSpec, String) {
        // Handle unquoted sheet names containing characters our segment
        // reader rejects (such as bracketed external workbook tokens, e.g.
        // `[1]Sheet1!A1`). The original implementation scanned for the first
        // `!` after byte 0; preserve that behaviour for compatibility.
        let mut chars = reference.chars();
        if chars.next().is_some()
            && let Some((_, ref_part)) = chars.as_str().split_once('!')
            && let Some(sheet) = reference
                .strip_suffix(ref_part)
                .and_then(|head| head.strip_suffix('!'))
        {
            return (SheetSpec::Single(sheet.to_string()), ref_part.to_string());
        }

        (SheetSpec::None, reference.to_string())
    }

    /// Detect R1C1-shaped operands so they aren't routed through the table-
    /// reference parser (issue #76).
    ///
    /// Matches `^R\d*(\[-?\d+\])?C\d*(\[-?\d+\])?$` and additionally requires
    /// the operand to contain at least one digit or bracket so that bare `R`,
    /// `C`, and `RC` (which already classify cleanly as `NamedRange` via the
    /// non-bracket path) are not pulled in here. Plain A1 cells like `R1`,
    /// `C5`, and `RC1` never reach this function because they don't contain
    /// `[` and are handled by the cell-reference path.
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "cursor bounded by slice length"
    )]
    fn is_r1c1_shape(s: &str) -> bool {
        let bytes = s.as_bytes();
        let len = bytes.len();
        let mut i = 0usize;
        let mut anchored = false;

        if bytes.get(i) != Some(&b'R') {
            return false;
        }
        i += 1;

        let row_digits_start = i;
        while bytes.get(i).is_some_and(u8::is_ascii_digit) {
            i += 1;
        }
        if i > row_digits_start {
            anchored = true;
        }

        if bytes.get(i) == Some(&b'[') {
            i += 1;
            if bytes.get(i) == Some(&b'-') {
                i += 1;
            }
            let n_start = i;
            while bytes.get(i).is_some_and(u8::is_ascii_digit) {
                i += 1;
            }
            if i == n_start || bytes.get(i) != Some(&b']') {
                return false;
            }
            i += 1;
            anchored = true;
        }

        if bytes.get(i) != Some(&b'C') {
            return false;
        }
        i += 1;

        let col_digits_start = i;
        while bytes.get(i).is_some_and(u8::is_ascii_digit) {
            i += 1;
        }
        if i > col_digits_start {
            anchored = true;
        }

        if bytes.get(i) == Some(&b'[') {
            i += 1;
            if bytes.get(i) == Some(&b'-') {
                i += 1;
            }
            let n_start = i;
            while bytes.get(i).is_some_and(u8::is_ascii_digit) {
                i += 1;
            }
            if i == n_start || bytes.get(i) != Some(&b']') {
                return false;
            }
            i += 1;
            anchored = true;
        }

        i == len && anchored
    }

    /// Parse a table reference like "Table1[Column1]" or more complex ones
    /// like "Table1[[#All],[Column1]:[Column2]]".
    ///
    /// The specifier syntax is parsed by a real recursive-descent parser
    /// (`structured_ref::SpecifierParser`) following MS-XLSX §18.17.6.2.
    fn parse_table_reference(reference: &str) -> Result<Self, ParsingError> {
        let (table_name, specifier_str) = reference
            .find('[')
            .and_then(|bracket_pos| reference.split_at_checked(bracket_pos))
            .ok_or_else(|| {
                ParsingError::InvalidReference(format!(
                    "Missing '[' in table reference: {reference}"
                ))
            })?;
        let table_name = table_name.trim();
        if table_name.is_empty() {
            return Err(ParsingError::InvalidReference(reference.to_string()));
        }

        let specifier = structured_ref::parse_full_specifier(specifier_str)?;

        Ok(ReferenceType::Table(TableReference {
            name: table_name.to_string(),
            specifier,
        }))
    }

    /// Handle the `[...]` shorthand that appears without a table name. The
    /// resolver/evaluator binds the implicit table from cell context.
    ///
    /// `[TableName]` is the data-body shorthand and is materialised as
    /// `Table { name = "TableName", specifier = #Data }`; everything else
    /// produces an unnamed `Table` carrying the parsed specifier verbatim.
    fn parse_bracketed_structured_reference(reference: &str) -> Result<Self, ParsingError> {
        debug_assert!(reference.starts_with('[') && reference.ends_with(']'));
        let specifier = structured_ref::parse_full_specifier(reference)?;

        match specifier {
            Some(TableSpecifier::Column(name)) => Ok(ReferenceType::Table(TableReference {
                name,
                specifier: Some(TableSpecifier::SpecialItem(SpecialItem::Data)),
            })),
            other => Ok(ReferenceType::Table(TableReference {
                name: String::new(),
                specifier: other,
            })),
        }
    }

    fn parse_openformula_reference(reference: &str) -> Result<Self, ParsingError> {
        if let Some(inner) = reference
            .strip_prefix('[')
            .and_then(|rest| rest.strip_suffix(']'))
        {
            if inner.is_empty() {
                return Err(ParsingError::InvalidReference(
                    "Empty OpenFormula reference".to_string(),
                ));
            }

            let (start_part_str, end_part_str) = match inner.split_once(':') {
                Some((start, end)) => (start, Some(end)),
                None => (inner, None),
            };

            let start_part = Self::parse_openformula_part(start_part_str)?;
            let end_part = if let Some(part) = end_part_str {
                Some(Self::parse_openformula_part(part)?)
            } else {
                None
            };

            let sheet = match (&start_part.sheet, &end_part) {
                (Some(sheet), Some(end)) => {
                    if let Some(end_sheet) = &end.sheet
                        && end_sheet != sheet
                    {
                        return Err(ParsingError::InvalidReference(format!(
                            "Mismatched sheets in reference: {sheet} vs {end_sheet}"
                        )));
                    }
                    Some(sheet.clone())
                }
                (Some(sheet), None) => Some(sheet.clone()),
                (None, Some(end)) => end.sheet.clone(),
                (None, None) => None,
            };

            let mut excel_like = String::new();
            if let Some(sheet_name) = sheet {
                if sheet_name_needs_quoting(&sheet_name) {
                    let escaped = sheet_name.replace('\'', "''");
                    excel_like.push('\'');
                    excel_like.push_str(&escaped);
                    excel_like.push('\'');
                } else {
                    excel_like.push_str(&sheet_name);
                }
                excel_like.push('!');
            }

            excel_like.push_str(&start_part.coord);
            if let Some(end) = end_part {
                excel_like.push(':');
                excel_like.push_str(&end.coord);
            }

            return Self::parse_excel_reference(&excel_like);
        }

        Err(ParsingError::InvalidReference(format!(
            "Unsupported OpenFormula reference: {reference}"
        )))
    }

    fn parse_openformula_part(part: &str) -> Result<OpenFormulaRefPart, ParsingError> {
        let trimmed = part.trim();
        if trimmed.is_empty() {
            return Err(ParsingError::InvalidReference(
                "Empty component in OpenFormula reference".to_string(),
            ));
        }

        if trimmed == "." {
            return Err(ParsingError::InvalidReference(
                "Incomplete OpenFormula reference component".to_string(),
            ));
        }

        if trimmed.starts_with('[') {
            // Nested brackets are not expected here
            return Err(ParsingError::InvalidReference(format!(
                "Unexpected '[' in OpenFormula reference component: {trimmed}"
            )));
        }

        let (sheet, coord_slice) = if let Some(stripped) = trimmed.strip_prefix('.') {
            (None, stripped.trim())
        } else if let Some(dot_idx) = Self::find_openformula_sheet_separator(trimmed) {
            #[expect(
                clippy::string_slice,
                clippy::arithmetic_side_effects,
                reason = "byte offset from ASCII delimiter search: dot_idx is the index of a `.`"
            )]
            let (sheet_part, coord_part) = (&trimmed[..dot_idx], &trimmed[dot_idx + 1..]);
            let (sheet_part, coord_part) = (sheet_part.trim(), coord_part.trim());
            if coord_part.is_empty() {
                return Err(ParsingError::InvalidReference(format!(
                    "Missing coordinate in OpenFormula reference component: {trimmed}"
                )));
            }
            let sheet_name = Self::normalise_openformula_sheet(sheet_part)?;
            (Some(sheet_name), coord_part)
        } else {
            (None, trimmed)
        };

        let coord = coord_slice.trim_start_matches('.').trim().to_string();

        if coord.is_empty() {
            return Err(ParsingError::InvalidReference(format!(
                "Missing coordinate in OpenFormula reference component: {trimmed}"
            )));
        }

        Ok(OpenFormulaRefPart { sheet, coord })
    }

    fn normalise_openformula_sheet(sheet: &str) -> Result<String, ParsingError> {
        let without_abs = sheet.trim().trim_start_matches('$');

        if let Some(quoted) = without_abs.strip_prefix('\'') {
            let Some(inner) = quoted.strip_suffix('\'') else {
                return Err(ParsingError::InvalidReference(format!(
                    "Unterminated sheet name in OpenFormula reference: {sheet}"
                )));
            };
            Ok(inner.replace("''", "'"))
        } else {
            Ok(without_abs.to_string())
        }
    }

    #[expect(
        clippy::arithmetic_side_effects,
        reason = "cursor bounded by slice length"
    )]
    fn find_openformula_sheet_separator(part: &str) -> Option<usize> {
        let bytes = part.as_bytes();
        let mut i = 0;
        let mut in_quotes = false;

        while let Some(&b) = bytes.get(i) {
            match b {
                b'\'' => {
                    if bytes.get(i + 1) == Some(&b'\'') {
                        i += 2;
                        continue;
                    }
                    in_quotes = !in_quotes;
                    i += 1;
                }
                b'.' if !in_quotes => return Some(i),
                _ => i += 1,
            }
        }

        None
    }

    // The structured-reference grammar lives in the `structured_ref`
    // submodule below; legacy `parse_special_item` /
    // `parse_complex_table_specifier` helpers were removed when the real
    // recursive-descent parser landed for issue #73.

    /// Get the Excel-style string representation of this reference
    pub fn to_excel_string(&self) -> String {
        match self {
            ReferenceType::Cell {
                sheet,
                row,
                col,
                row_abs,
                col_abs,
            } => {
                let col_str = Self::format_col(*col, *col_abs);
                let row_str = Self::format_row(*row, *row_abs);
                if let Some(s) = sheet {
                    if sheet_name_needs_quoting(s) {
                        let escaped_name = s.replace('\'', "''");
                        format!("'{}'!{}{}", escaped_name, col_str, row_str)
                    } else {
                        format!("{}!{}{}", s, col_str, row_str)
                    }
                } else {
                    format!("{}{}", col_str, row_str)
                }
            }
            ReferenceType::Range {
                sheet,
                start_row,
                start_col,
                end_row,
                end_col,
                start_row_abs,
                start_col_abs,
                end_row_abs,
                end_col_abs,
            } => {
                // Format start reference
                let start_ref = match (start_col, start_row) {
                    (Some(col), Some(row)) => format!(
                        "{}{}",
                        Self::format_col(*col, *start_col_abs),
                        Self::format_row(*row, *start_row_abs)
                    ),
                    (Some(col), None) => Self::format_col(*col, *start_col_abs),
                    (None, Some(row)) => Self::format_row(*row, *start_row_abs),
                    (None, None) => "".to_string(), // Should not happen in normal usage
                };

                // Format end reference
                let end_ref = match (end_col, end_row) {
                    (Some(col), Some(row)) => format!(
                        "{}{}",
                        Self::format_col(*col, *end_col_abs),
                        Self::format_row(*row, *end_row_abs)
                    ),
                    (Some(col), None) => Self::format_col(*col, *end_col_abs),
                    (None, Some(row)) => Self::format_row(*row, *end_row_abs),
                    (None, None) => "".to_string(), // Should not happen in normal usage
                };

                let range_part = format!("{start_ref}:{end_ref}");

                if let Some(s) = sheet {
                    if sheet_name_needs_quoting(s) {
                        let escaped_name = s.replace('\'', "''");
                        format!("'{escaped_name}'!{range_part}")
                    } else {
                        format!("{s}!{range_part}")
                    }
                } else {
                    range_part
                }
            }
            ReferenceType::Cell3D { .. } | ReferenceType::Range3D { .. } => format!("{self}"),
            ReferenceType::External(ext) => ext.raw.clone(),
            ReferenceType::Table(table_ref) => {
                if let Some(specifier) = &table_ref.specifier {
                    format!("{}[{}]", table_ref.name, specifier)
                } else {
                    table_ref.name.clone()
                }
            }
            ReferenceType::NamedRange(name) => name.clone(),
        }
    }
}

/// A supported unary formula operator.
///
/// `Debug` prints the quoted spelling to preserve the former string-based
/// AST's debug output, also embedded in AST display text.
#[non_exhaustive]
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum UnaryOperator {
    Plus,
    Minus,
    Percent,
    Spill,
    ImplicitIntersection,
}
// Serialize as a string even in non-human-readable serde formats. A
// renamed unit enum would still use a variant index in binary serializers.
#[cfg(feature = "serde")]
impl Serialize for UnaryOperator {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        serializer.serialize_str(self.as_str())
    }
}
#[cfg(feature = "serde")]
impl<'de> Deserialize<'de> for UnaryOperator {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        let value = String::deserialize(deserializer)?;
        Self::try_from(value.as_str()).map_err(serde::de::Error::custom)
    }
}
impl UnaryOperator {
    /// The operator spelling used in formulas and serialized ASTs.
    pub const fn as_str(self) -> &'static str {
        match self {
            Self::Plus => "+",
            Self::Minus => "-",
            Self::Percent => "%",
            Self::Spill => "#",
            Self::ImplicitIntersection => "@",
        }
    }
}
// ASTNodeType's Display embeds Debug for function arguments and arrays.
// Preserve the former String representation there as well.
impl fmt::Debug for UnaryOperator {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(self.as_str(), f)
    }
}
impl Display for UnaryOperator {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.as_str())
    }
}
impl TryFrom<&str> for UnaryOperator {
    type Error = &'static str;
    fn try_from(value: &str) -> Result<Self, Self::Error> {
        match value {
            "+" => Ok(Self::Plus),
            "-" => Ok(Self::Minus),
            "%" => Ok(Self::Percent),
            "#" => Ok(Self::Spill),
            "@" => Ok(Self::ImplicitIntersection),
            _ => Err("unsupported formula operator"),
        }
    }
}
impl std::hash::Hash for UnaryOperator {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.as_str().hash(state);
    }
}

/// A supported binary formula operator.
///
/// `Debug` prints the quoted spelling to preserve the former string-based
/// AST's debug output, also embedded in AST display text.
#[non_exhaustive]
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum BinaryOperator {
    Add,
    Subtract,
    Multiply,
    Divide,
    Power,
    Concat,
    Equal,
    NotEqual,
    Less,
    Greater,
    LessEqual,
    GreaterEqual,
    Range,
    Union,
    Intersection,
}
// Serialize as a string even in non-human-readable serde formats. A
// renamed unit enum would still use a variant index in binary serializers.
#[cfg(feature = "serde")]
impl Serialize for BinaryOperator {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        serializer.serialize_str(self.as_str())
    }
}
#[cfg(feature = "serde")]
impl<'de> Deserialize<'de> for BinaryOperator {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        let value = String::deserialize(deserializer)?;
        Self::try_from(value.as_str()).map_err(serde::de::Error::custom)
    }
}
impl BinaryOperator {
    /// The operator spelling used in formulas and serialized ASTs.
    pub const fn as_str(self) -> &'static str {
        match self {
            Self::Add => "+",
            Self::Subtract => "-",
            Self::Multiply => "*",
            Self::Divide => "/",
            Self::Power => "^",
            Self::Concat => "&",
            Self::Equal => "=",
            Self::NotEqual => "<>",
            Self::Less => "<",
            Self::Greater => ">",
            Self::LessEqual => "<=",
            Self::GreaterEqual => ">=",
            Self::Range => ":",
            Self::Union => ",",
            Self::Intersection => " ",
        }
    }
}
// ASTNodeType's Display embeds Debug for function arguments and arrays.
// Preserve the former String representation there as well.
impl fmt::Debug for BinaryOperator {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(self.as_str(), f)
    }
}
impl Display for BinaryOperator {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.as_str())
    }
}
/// Whether a node is a number, text or logical constant: never a reference,
/// so never an operand of the union operator (`=1,000` is not a union).
/// Error literals are not counted: Excel writes `#REF!` where a reference
/// in a union was deleted.
fn is_constant_literal(node: &ASTNode) -> bool {
    matches!(
        &node.node_type,
        ASTNodeType::Literal(value) if !matches!(value, LiteralValue::Error(_))
    )
}

impl TryFrom<&str> for BinaryOperator {
    type Error = &'static str;
    fn try_from(value: &str) -> Result<Self, Self::Error> {
        match value {
            "+" => Ok(Self::Add),
            "-" => Ok(Self::Subtract),
            "*" => Ok(Self::Multiply),
            "/" => Ok(Self::Divide),
            "^" => Ok(Self::Power),
            "&" => Ok(Self::Concat),
            "=" => Ok(Self::Equal),
            "<>" => Ok(Self::NotEqual),
            "<" => Ok(Self::Less),
            ">" => Ok(Self::Greater),
            "<=" => Ok(Self::LessEqual),
            ">=" => Ok(Self::GreaterEqual),
            ":" => Ok(Self::Range),
            "," => Ok(Self::Union),
            " " => Ok(Self::Intersection),
            _ => Err("unsupported formula operator"),
        }
    }
}
impl std::hash::Hash for BinaryOperator {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.as_str().hash(state);
    }
}

/// The different types of AST nodes.
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq, Hash)]
pub enum ASTNodeType {
    Literal(LiteralValue),
    /// An explicitly omitted function argument slot.
    ///
    /// This node is only valid as a direct argument of a [`Function`](Self::Function)
    /// or [`Call`](Self::Call) node.
    Omitted,
    Reference {
        original: String, // Original reference string (preserved for display/debugging)
        reference: ReferenceType, // Parsed reference
    },
    UnaryOp {
        op: UnaryOperator,
        expr: Box<ASTNode>,
    },
    BinaryOp {
        op: BinaryOperator,
        left: Box<ASTNode>,
        right: Box<ASTNode>,
    },
    Function {
        name: String,
        args: Vec<ASTNode>, // Most functions have <= 4 args
    },
    /// Generic call where the callee is itself an expression that produces
    /// a callable value (e.g. LAMBDA immediate-invocation `LAMBDA(x, x+1)(5)`).
    Call {
        callee: Box<ASTNode>,
        args: Vec<ASTNode>,
    },
    Array(Vec<Vec<ASTNode>>), // Most arrays are small
}

impl Display for ASTNodeType {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            ASTNodeType::Literal(value) => write!(f, "Literal({value})"),
            ASTNodeType::Omitted => write!(f, "Omitted"),
            ASTNodeType::Reference { reference, .. } => write!(f, "Reference({reference:?})"),
            ASTNodeType::UnaryOp { op, expr } => write!(f, "UnaryOp({op}, {expr})"),
            ASTNodeType::BinaryOp { op, left, right } => {
                write!(f, "BinaryOp({op}, {left}, {right})")
            }
            ASTNodeType::Function { name, args } => write!(f, "Function({name}, {args:?})"),
            ASTNodeType::Call { callee, args } => write!(f, "Call({callee}, {args:?})"),
            ASTNodeType::Array(rows) => write!(f, "Array({rows:?})"),
        }
    }
}

/// An AST node represents a parsed formula element
///
/// # Depth
///
/// Hashing ([`Self::fingerprint`], [`Self::calculate_hash`], `Hash`),
/// pretty-printing, `Display` and the derived `Clone`, `PartialEq`, `Debug`,
/// serde and drop glue recurse once per tree level. Trees within the default
/// [`ParserLimits::ast_height`](crate::ParserLimits::ast_height) limit (256)
/// are supported, which includes every tree the parser returns under default
/// limits. A taller tree, hand-built or parsed under a raised limit, needs the
/// caller to provide the stack (see
/// [`ParserLimits::with_ast_height`](crate::ParserLimits::with_ast_height)).
/// Reference walks ([`Self::visit_refs`], [`Self::refs`],
/// [`Self::get_dependencies`], [`Self::collect_references`],
/// [`Self::update_sheet_references`]) use an explicit stack and have no
/// depth limit.
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug, Clone, PartialEq)]
pub struct ASTNode {
    pub node_type: ASTNodeType,
    pub source_token: Option<Token>,
    /// True if this AST contains any volatile function calls.
    ///
    /// This is set by the parser when a volatility classifier is provided.
    /// For ASTs constructed manually (e.g., in tests), this defaults to false.
    pub contains_volatile: bool,
}

impl ASTNode {
    pub fn new(node_type: ASTNodeType, source_token: Option<Token>) -> Self {
        ASTNode {
            node_type,
            source_token,
            contains_volatile: false,
        }
    }

    /// Create an ASTNode while explicitly setting contains_volatile.
    pub fn new_with_volatile(
        node_type: ASTNodeType,
        source_token: Option<Token>,
        contains_volatile: bool,
    ) -> Self {
        ASTNode {
            node_type,
            source_token,
            contains_volatile,
        }
    }

    /// Whether this AST contains any volatile functions.
    pub fn contains_volatile(&self) -> bool {
        self.contains_volatile
    }

    /// Structural fingerprint of this tree; the same value as
    /// [`Self::calculate_hash`].
    ///
    /// # Depth
    ///
    /// Recursive in the tree height. Trees within the default
    /// [`ParserLimits::ast_height`](crate::ParserLimits::ast_height) limit (256)
    /// are supported, which includes every tree the parser returns under default
    /// limits. A taller tree, hand-built or parsed under a raised limit, needs the
    /// caller to provide the stack (see
    /// [`ParserLimits::with_ast_height`](crate::ParserLimits::with_ast_height)).
    pub fn fingerprint(&self) -> u64 {
        self.calculate_hash()
    }

    /// Calculate a hash for this ASTNode
    ///
    /// # Depth
    ///
    /// Recursive in the tree height. Trees within the default
    /// [`ParserLimits::ast_height`](crate::ParserLimits::ast_height) limit (256)
    /// are supported, which includes every tree the parser returns under default
    /// limits. A taller tree, hand-built or parsed under a raised limit, needs the
    /// caller to provide the stack (see
    /// [`ParserLimits::with_ast_height`](crate::ParserLimits::with_ast_height)).
    pub fn calculate_hash(&self) -> u64 {
        let mut hasher = FormulaHasher::new();
        self.hash_node(&mut hasher);
        hasher.finish()
    }

    fn hash_node(&self, hasher: &mut FormulaHasher) {
        match &self.node_type {
            ASTNodeType::Literal(value) => {
                hasher.write(&[1]); // Discriminant for Literal
                value.hash(hasher);
            }
            ASTNodeType::Omitted => hasher.write(&[8]),
            ASTNodeType::Reference { reference, .. } => {
                hasher.write(&[2]); // Discriminant for Reference
                reference.hash(hasher);
            }
            ASTNodeType::UnaryOp { op, expr } => {
                hasher.write(&[3]); // Discriminant for UnaryOp
                hasher.write(op.as_str().as_bytes());
                expr.hash_node(hasher);
            }
            ASTNodeType::BinaryOp { op, left, right } => {
                hasher.write(&[4]); // Discriminant for BinaryOp
                hasher.write(op.as_str().as_bytes());
                left.hash_node(hasher);
                right.hash_node(hasher);
            }
            ASTNodeType::Function { name, args } => {
                hasher.write(&[5]); // Discriminant for Function
                // Use lowercase function name to be case-insensitive
                let name_lower = name.to_lowercase();
                hasher.write(name_lower.as_bytes());
                hasher.write_usize(args.len());
                for arg in args {
                    arg.hash_node(hasher);
                }
            }
            ASTNodeType::Call { callee, args } => {
                hasher.write(&[7]); // Discriminant for Call
                callee.hash_node(hasher);
                hasher.write_usize(args.len());
                for arg in args {
                    arg.hash_node(hasher);
                }
            }
            ASTNodeType::Array(rows) => {
                hasher.write(&[6]); // Discriminant for Array
                hasher.write_usize(rows.len());
                for row in rows {
                    hasher.write_usize(row.len());
                    for item in row {
                        item.hash_node(hasher);
                    }
                }
            }
        }
    }

    pub fn get_dependencies(&self) -> Vec<&ReferenceType> {
        let mut dependencies = Vec::new();
        self.collect_dependencies(&mut dependencies);
        dependencies
    }

    pub fn get_dependency_strings(&self) -> Vec<String> {
        self.get_dependencies()
            .into_iter()
            .map(|dep| format!("{dep}"))
            .collect()
    }

    /// Pre-order walk with an explicit stack, so a deep hand-built tree
    /// cannot exhaust the call stack. Children are pushed in reverse so they
    /// are visited in source order.
    fn collect_dependencies<'a>(&'a self, dependencies: &mut Vec<&'a ReferenceType>) {
        let mut stack: Vec<&'a ASTNode> = vec![self];
        while let Some(node) = stack.pop() {
            match &node.node_type {
                ASTNodeType::Reference { reference, .. } => dependencies.push(reference),
                ASTNodeType::UnaryOp { expr, .. } => stack.push(expr),
                ASTNodeType::BinaryOp { left, right, .. } => {
                    stack.push(right);
                    stack.push(left);
                }
                ASTNodeType::Function { args, .. } => stack.extend(args.iter().rev()),
                ASTNodeType::Call { callee, args } => {
                    stack.extend(args.iter().rev());
                    stack.push(callee);
                }
                ASTNodeType::Array(rows) => {
                    for row in rows.iter().rev() {
                        stack.extend(row.iter().rev());
                    }
                }
                ASTNodeType::Literal(_) | ASTNodeType::Omitted => {}
            }
        }
    }

    /// Lightweight borrowed view of a reference encountered during AST traversal.
    /// This mirrors ReferenceType variants but borrows sheet/name strings to avoid allocation.
    pub fn refs(&self) -> RefIter<'_> {
        RefIter {
            stack: smallvec::smallvec![self],
        }
    }

    /// Visit all references in this AST without allocating intermediates.
    pub fn visit_refs<V: FnMut(RefView<'_>)>(&self, mut visitor: V) {
        let mut stack: Vec<&ASTNode> = Vec::with_capacity(8);
        stack.push(self);
        while let Some(node) = stack.pop() {
            match &node.node_type {
                ASTNodeType::Reference { reference, .. } => visitor(RefView::from(reference)),
                ASTNodeType::UnaryOp { expr, .. } => stack.push(expr),
                ASTNodeType::BinaryOp { left, right, .. } => {
                    // Push right first so left is visited first (stable-ish order)
                    stack.push(right);
                    stack.push(left);
                }
                ASTNodeType::Function { args, .. } => {
                    for a in args.iter().rev() {
                        stack.push(a);
                    }
                }
                ASTNodeType::Call { callee, args } => {
                    for a in args.iter().rev() {
                        stack.push(a);
                    }
                    stack.push(callee);
                }
                ASTNodeType::Array(rows) => {
                    for r in rows.iter().rev() {
                        for item in r.iter().rev() {
                            stack.push(item);
                        }
                    }
                }
                ASTNodeType::Literal(_) | ASTNodeType::Omitted => {}
            }
        }
    }

    /// Convenience: collect references into a small, inline vector based on a policy.
    pub fn collect_references(&self, policy: &CollectPolicy) -> SmallVec<[ReferenceType; 4]> {
        let mut out: SmallVec<[ReferenceType; 4]> = SmallVec::new();
        self.visit_refs(|rv| match rv {
            RefView::Cell {
                sheet,
                row,
                col,
                row_abs,
                col_abs,
            } => out.push(ReferenceType::Cell {
                sheet: sheet.map(|s| s.to_string()),
                row,
                col,
                row_abs,
                col_abs,
            }),
            RefView::Range {
                sheet,
                start_row,
                start_col,
                end_row,
                end_col,
                start_row_abs,
                start_col_abs,
                end_row_abs,
                end_col_abs,
            } => {
                // Optionally expand very small finite ranges into individual cells
                if policy.expand_small_ranges
                    && let (Some(sr), Some(sc), Some(er), Some(ec)) =
                        (start_row, start_col, end_row, end_col)
                {
                    // Widened to u64: a full-height or full-width u32
                    // span plus one does not fit in u32.
                    let rows = u64::from(er.saturating_sub(sr)) + 1;
                    let cols = u64::from(ec.saturating_sub(sc)) + 1;
                    let area = rows.saturating_mul(cols);
                    let limit = u64::try_from(policy.range_expansion_limit).unwrap_or(u64::MAX);
                    if area <= limit {
                        let row_abs = start_row_abs && end_row_abs;
                        let col_abs = start_col_abs && end_col_abs;
                        for r in sr..=er {
                            for c in sc..=ec {
                                out.push(ReferenceType::Cell {
                                    sheet: sheet.map(|s| s.to_string()),
                                    row: r,
                                    col: c,
                                    row_abs,
                                    col_abs,
                                });
                            }
                        }
                        return; // handled
                    }
                }
                out.push(ReferenceType::Range {
                    sheet: sheet.map(|s| s.to_string()),
                    start_row,
                    start_col,
                    end_row,
                    end_col,
                    start_row_abs,
                    start_col_abs,
                    end_row_abs,
                    end_col_abs,
                });
            }
            RefView::Cell3D {
                sheet_first,
                sheet_last,
                row,
                col,
                row_abs,
                col_abs,
            } => out.push(ReferenceType::Cell3D {
                sheet_first: sheet_first.to_string(),
                sheet_last: sheet_last.to_string(),
                row,
                col,
                row_abs,
                col_abs,
            }),
            RefView::Range3D {
                sheet_first,
                sheet_last,
                start_row,
                start_col,
                end_row,
                end_col,
                start_row_abs,
                start_col_abs,
                end_row_abs,
                end_col_abs,
            } => out.push(ReferenceType::Range3D {
                sheet_first: sheet_first.to_string(),
                sheet_last: sheet_last.to_string(),
                start_row,
                start_col,
                end_row,
                end_col,
                start_row_abs,
                start_col_abs,
                end_row_abs,
                end_col_abs,
            }),
            RefView::External {
                raw,
                book,
                sheet,
                kind,
            } => out.push(ReferenceType::External(ExternalReference {
                raw: raw.to_string(),
                book: ExternalBookRef::Token(book.to_string()),
                sheet: sheet.to_string(),
                kind,
            })),
            RefView::Table { name, specifier } => out.push(ReferenceType::Table(TableReference {
                name: name.to_string(),
                specifier: specifier.cloned(),
            })),
            RefView::NamedRange { name } => {
                if policy.include_names {
                    out.push(ReferenceType::NamedRange(name.to_string()));
                }
            }
        });
        out
    }
    /// Updates sheet references within the AST.
    ///
    /// If `target_name` is provided, only references matching that sheet name are updated.
    /// This is used for "healing" specific broken references (Tombstone rescue).
    /// If `target_name` is None, it acts as a global rename (standard sheet rename).
    ///
    /// The walk uses an explicit stack, so tree depth is not limited by the
    /// call stack.
    pub fn update_sheet_references(&mut self, target_name: Option<&str>, new_name: &str) {
        let mut stack: Vec<&mut ASTNode> = vec![self];
        while let Some(node) = stack.pop() {
            match &mut node.node_type {
                ASTNodeType::Reference {
                    reference:
                        ReferenceType::Cell { sheet, .. } | ReferenceType::Range { sheet, .. },
                    ..
                } => {
                    if let Some(current_sheet) = sheet
                        && (target_name.is_none() || target_name == Some(current_sheet.as_str()))
                    {
                        *sheet = Some(new_name.to_string());
                    }
                }
                ASTNodeType::Reference {
                    reference:
                        ReferenceType::Cell3D {
                            sheet_first,
                            sheet_last,
                            ..
                        }
                        | ReferenceType::Range3D {
                            sheet_first,
                            sheet_last,
                            ..
                        },
                    ..
                } => {
                    if target_name.is_none() || target_name == Some(sheet_first.as_str()) {
                        *sheet_first = new_name.to_string();
                    }
                    if target_name.is_none() || target_name == Some(sheet_last.as_str()) {
                        *sheet_last = new_name.to_string();
                    }
                }
                ASTNodeType::UnaryOp { expr, .. } => stack.push(expr),
                ASTNodeType::BinaryOp { left, right, .. } => {
                    stack.push(right);
                    stack.push(left);
                }
                ASTNodeType::Function { args, .. } => stack.extend(args.iter_mut().rev()),
                ASTNodeType::Call { callee, args } => {
                    stack.extend(args.iter_mut().rev());
                    stack.push(callee);
                }
                ASTNodeType::Array(rows) => {
                    for row in rows.iter_mut().rev() {
                        stack.extend(row.iter_mut().rev());
                    }
                }
                ASTNodeType::Reference { .. } | ASTNodeType::Literal(_) | ASTNodeType::Omitted => {}
            }
        }
    }
}

/// A borrowing view over a ReferenceType. Avoids cloning sheet/names while walking.
#[derive(Clone, Copy, Debug)]
pub enum RefView<'a> {
    Cell {
        sheet: Option<&'a str>,
        row: u32,
        col: u32,
        row_abs: bool,
        col_abs: bool,
    },
    Range {
        sheet: Option<&'a str>,
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
        start_row_abs: bool,
        start_col_abs: bool,
        end_row_abs: bool,
        end_col_abs: bool,
    },
    /// 3D cell view (`Sheet1:Sheet3!A1`).
    Cell3D {
        sheet_first: &'a str,
        sheet_last: &'a str,
        row: u32,
        col: u32,
        row_abs: bool,
        col_abs: bool,
    },
    /// 3D range view (`Sheet1:Sheet3!A1:B2`).
    Range3D {
        sheet_first: &'a str,
        sheet_last: &'a str,
        start_row: Option<u32>,
        start_col: Option<u32>,
        end_row: Option<u32>,
        end_col: Option<u32>,
        start_row_abs: bool,
        start_col_abs: bool,
        end_row_abs: bool,
        end_col_abs: bool,
    },
    External {
        raw: &'a str,
        book: &'a str,
        sheet: &'a str,
        kind: ExternalRefKind,
    },
    Table {
        name: &'a str,
        specifier: Option<&'a TableSpecifier>,
    },
    NamedRange {
        name: &'a str,
    },
}

impl<'a> From<&'a ReferenceType> for RefView<'a> {
    fn from(r: &'a ReferenceType) -> Self {
        match r {
            ReferenceType::Cell {
                sheet,
                row,
                col,
                row_abs,
                col_abs,
            } => RefView::Cell {
                sheet: sheet.as_deref(),
                row: *row,
                col: *col,
                row_abs: *row_abs,
                col_abs: *col_abs,
            },
            ReferenceType::Range {
                sheet,
                start_row,
                start_col,
                end_row,
                end_col,
                start_row_abs,
                start_col_abs,
                end_row_abs,
                end_col_abs,
            } => RefView::Range {
                sheet: sheet.as_deref(),
                start_row: *start_row,
                start_col: *start_col,
                end_row: *end_row,
                end_col: *end_col,
                start_row_abs: *start_row_abs,
                start_col_abs: *start_col_abs,
                end_row_abs: *end_row_abs,
                end_col_abs: *end_col_abs,
            },
            ReferenceType::Cell3D {
                sheet_first,
                sheet_last,
                row,
                col,
                row_abs,
                col_abs,
            } => RefView::Cell3D {
                sheet_first: sheet_first.as_str(),
                sheet_last: sheet_last.as_str(),
                row: *row,
                col: *col,
                row_abs: *row_abs,
                col_abs: *col_abs,
            },
            ReferenceType::Range3D {
                sheet_first,
                sheet_last,
                start_row,
                start_col,
                end_row,
                end_col,
                start_row_abs,
                start_col_abs,
                end_row_abs,
                end_col_abs,
            } => RefView::Range3D {
                sheet_first: sheet_first.as_str(),
                sheet_last: sheet_last.as_str(),
                start_row: *start_row,
                start_col: *start_col,
                end_row: *end_row,
                end_col: *end_col,
                start_row_abs: *start_row_abs,
                start_col_abs: *start_col_abs,
                end_row_abs: *end_row_abs,
                end_col_abs: *end_col_abs,
            },
            ReferenceType::External(ext) => RefView::External {
                raw: ext.raw.as_str(),
                book: ext.book.token(),
                sheet: ext.sheet.as_str(),
                kind: ext.kind,
            },
            ReferenceType::Table(tr) => RefView::Table {
                name: tr.name.as_str(),
                specifier: tr.specifier.as_ref(),
            },
            ReferenceType::NamedRange(name) => RefView::NamedRange { name },
        }
    }
}

/// Iterator over RefView for an AST, implemented via an explicit stack to avoid recursion allocation.
pub struct RefIter<'a> {
    stack: smallvec::SmallVec<[&'a ASTNode; 8]>,
}

impl<'a> Iterator for RefIter<'a> {
    type Item = RefView<'a>;
    fn next(&mut self) -> Option<Self::Item> {
        while let Some(node) = self.stack.pop() {
            match &node.node_type {
                ASTNodeType::Reference { reference, .. } => return Some(RefView::from(reference)),
                ASTNodeType::UnaryOp { expr, .. } => self.stack.push(expr),
                ASTNodeType::BinaryOp { left, right, .. } => {
                    self.stack.push(right);
                    self.stack.push(left);
                }
                ASTNodeType::Function { args, .. } => {
                    for a in args.iter().rev() {
                        self.stack.push(a);
                    }
                }
                ASTNodeType::Call { callee, args } => {
                    for a in args.iter().rev() {
                        self.stack.push(a);
                    }
                    self.stack.push(callee);
                }
                ASTNodeType::Array(rows) => {
                    for r in rows.iter().rev() {
                        for item in r.iter().rev() {
                            self.stack.push(item);
                        }
                    }
                }
                ASTNodeType::Literal(_) | ASTNodeType::Omitted => {}
            }
        }
        None
    }
}

/// Policy controlling how references are collected.
#[derive(Debug, Clone)]
pub struct CollectPolicy {
    pub expand_small_ranges: bool,
    pub range_expansion_limit: usize,
    pub include_names: bool,
}

impl Default for CollectPolicy {
    fn default() -> Self {
        Self {
            expand_small_ranges: false,
            range_expansion_limit: 0,
            include_names: true,
        }
    }
}

impl Display for ASTNode {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.node_type)
    }
}

impl std::hash::Hash for ASTNode {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        let hash = self.calculate_hash();
        state.write_u64(hash);
    }
}

impl From<TokenizerError> for ParserError {
    fn from(err: TokenizerError) -> Self {
        ParserError {
            message: err.message,
            position: Some(err.pos),
        }
    }
}

/// Source-span-backed parser for converting formulas into an AST.
///
/// This is the canonical parser implementation. It owns the formula source and
/// span tokens, avoiding per-token string allocation while preserving source
/// locations for AST nodes.
pub struct Parser {
    source: Arc<str>,
    tokens: Arc<[TokenSpan]>,
    position: usize,
    volatility_classifier: Option<VolatilityClassifierBox>,
    dialect: FormulaDialect,
    /// When > 0, treat a top-level `OpInfix(",")` as a terminator (call-arg
    /// separator) instead of the union/list operator. Used by `parse_call_arguments`.
    in_call_args_depth: usize,
    /// Current recursion depth of `parse_bp`. Bounded by the configured Pratt-frame limit so a
    /// deeply nested formula (e.g. `=((((...))))`) returns an error instead of
    /// overflowing the stack.
    depth: usize,
    limits: ParserLimits,
    nodes: usize,
    pending_error: Option<ParserError>,
}

/// Ephemeral construction metadata; public AST nodes retain no height field.
/// Parent admission uses child heights directly, without traversing subtrees.
struct BuiltNode {
    node: ASTNode,
    height: usize,
}
#[derive(Default)]
struct BuiltArgs {
    nodes: Vec<ASTNode>,
    height: usize,
    volatile: bool,
}
impl BuiltArgs {
    fn push(&mut self, child: BuiltNode) {
        self.height = self.height.max(child.height);
        self.volatile |= child.node.contains_volatile;
        self.nodes.push(child.node);
    }
}
impl std::ops::Deref for BuiltNode {
    type Target = ASTNode;
    fn deref(&self) -> &ASTNode {
        &self.node
    }
}

impl Parser {
    /// Tokenize a formula using the default Excel dialect and prepare it for parsing.
    pub fn new<T: AsRef<str>>(formula: T) -> Result<Self, TokenizerError> {
        Self::new_with_dialect(formula, FormulaDialect::Excel)
    }

    /// Compatibility alias for `Parser::new`.
    pub fn try_from_formula(formula: &str) -> Result<Self, TokenizerError> {
        Self::new(formula)
    }

    /// Tokenize a formula with an explicit dialect and prepare it for parsing.
    pub fn new_with_dialect<T: AsRef<str>>(
        formula: T,
        dialect: FormulaDialect,
    ) -> Result<Self, TokenizerError> {
        Self::new_with_limits(formula.as_ref(), dialect, ParserLimits::default())
    }

    fn new_with_limits(
        formula: &str,
        dialect: FormulaDialect,
        limits: ParserLimits,
    ) -> Result<Self, TokenizerError> {
        limits.check_source(formula)?;
        let spans = crate::tokenizer::tokenize_spans_with_limits(formula, dialect, limits)?;
        let mut parser = Self::from_source_and_tokens(
            Arc::from(formula),
            Arc::from(spans.into_boxed_slice()),
            dialect,
        );
        parser.limits = limits;
        Ok(parser)
    }

    /// External streams are mutable: validate admission and all spans before copying.
    pub fn from_token_stream(stream: &TokenStream) -> Self {
        let limits = ParserLimits::default();
        let error = stream.admission_error(limits).map(ParserError::from);
        if let Some(error) = error {
            let mut parser =
                Self::from_source_and_tokens(Arc::from(""), Arc::from([]), stream.dialect());
            parser.pending_error = Some(error);
            return parser;
        }
        Self::from_source_and_tokens(
            Arc::from(stream.source()),
            Arc::from(stream.spans.clone().into_boxed_slice()),
            stream.dialect(),
        )
    }

    fn from_source_and_tokens(
        source: Arc<str>,
        tokens: Arc<[TokenSpan]>,
        dialect: FormulaDialect,
    ) -> Self {
        Parser {
            source,
            tokens,
            position: 0,
            volatility_classifier: None,
            dialect,
            in_call_args_depth: 0,
            depth: 0,
            limits: ParserLimits::default(),
            nodes: 0,
            pending_error: None,
        }
    }

    /// Provide a function-volatility classifier for this parser.
    /// If set, the parser will annotate ASTs with a contains_volatile bit.
    pub fn with_volatility_classifier<F>(mut self, f: F) -> Self
    where
        F: Fn(&str) -> bool + Send + Sync + 'static,
    {
        self.volatility_classifier = Some(Box::new(f));
        self
    }

    // Keep rich AST temporaries out of every active Pratt frame in debug builds.
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "child heights are at most the AST height limit and the number of admitted nodes, so 1 + height cannot overflow"
    )]
    fn unary(&mut self, expr: BuiltNode, span: TokenSpan) -> Result<BuiltNode, ParserError> {
        let height = 1 + expr.height;
        self.admit(height)?;
        let token = self.span_to_token(&span);
        let volatile = expr.contains_volatile;
        Ok(BuiltNode {
            height,
            node: ASTNode::new_with_volatile(
                ASTNodeType::UnaryOp {
                    op: UnaryOperator::try_from(token.value.as_str()).map_err(|message| {
                        ParserError {
                            message: message.to_string(),
                            position: Some(span.start),
                        }
                    })?,
                    expr: Box::new(expr.node),
                },
                Some(token),
                volatile,
            ),
        })
    }
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "child heights are at most the AST height limit and the number of admitted nodes, so 1 + height cannot overflow"
    )]
    fn binary(
        &mut self,
        left: BuiltNode,
        right: BuiltNode,
        span: TokenSpan,
    ) -> Result<BuiltNode, ParserError> {
        let height = 1 + left.height.max(right.height);
        self.admit(height)?;
        let token = self.span_to_token(&span);
        let op = BinaryOperator::try_from(token.value.as_str()).map_err(|message| ParserError {
            message: if token.value == ";" {
                "';' is an argument separator, not an operator in this position; OpenFormula union uses '~'".to_string()
            } else {
                message.to_string()
            },
            position: Some(span.start),
        })?;
        if op == BinaryOperator::Union
            && (is_constant_literal(&left.node) || is_constant_literal(&right.node))
        {
            return Err(ParserError {
                message: "the union operator joins references; a number, text or logical constant is not a reference".to_string(),
                position: Some(span.start),
            });
        }
        let volatile = left.contains_volatile || right.contains_volatile;
        Ok(BuiltNode {
            height,
            node: ASTNode::new_with_volatile(
                ASTNodeType::BinaryOp {
                    op,
                    left: Box::new(left.node),
                    right: Box::new(right.node),
                },
                Some(token),
                volatile,
            ),
        })
    }
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "child heights are at most the AST height limit and the number of admitted nodes, so 1 + height cannot overflow"
    )]
    fn call(&mut self, left: BuiltNode, args: BuiltArgs) -> Result<BuiltNode, ParserError> {
        let height = 1 + left.height.max(args.height);
        self.admit(height)?;
        let volatile = left.contains_volatile || args.volatile;
        Ok(BuiltNode {
            height,
            node: ASTNode::new_with_volatile(
                ASTNodeType::Call {
                    callee: Box::new(left.node),
                    args: args.nodes,
                },
                None,
                volatile,
            ),
        })
    }
    /// The byte offset in the source of the token at `index`, or the source
    /// length when `index` is past the last token. `ParserError::position`
    /// is a byte offset, like the tokenizer's error position.
    fn byte_offset(&self, index: usize) -> usize {
        self.tokens
            .get(index)
            .map_or(self.source.len(), |token| token.start)
    }

    /// The token at the cursor, if any.
    #[inline]
    fn peek(&self) -> Option<TokenSpan> {
        self.tokens.get(self.position).copied()
    }

    /// Whether the token at the cursor has this type and subtype.
    #[inline]
    fn peek_is(&self, token_type: TokenType, subtype: TokenSubType) -> bool {
        self.peek()
            .is_some_and(|t| t.token_type == token_type && t.subtype == subtype)
    }

    /// Move past the token at the cursor.
    #[inline]
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "callers advance only past a token they read with peek, so position < tokens.len()"
    )]
    fn advance(&mut self) {
        self.position += 1;
    }

    fn skip_whitespace(&mut self) {
        while self
            .peek()
            .is_some_and(|t| t.token_type == TokenType::Whitespace)
        {
            self.advance();
        }
    }

    #[expect(
        clippy::string_slice,
        reason = "spans come from the span tokenizer on this source (char-boundary invariant), or from an external TokenStream whose spans admission_error checked with source.get"
    )]
    fn span_value(&self, span: &TokenSpan) -> &str {
        &self.source[span.start..span.end]
    }

    fn semantic_span_value(&self, span: &TokenSpan) -> &str {
        let value = self.span_value(span);
        if span.token_type == TokenType::OpInfix
            && value.as_bytes().contains(&b' ')
            && value
                .as_bytes()
                .iter()
                .all(|byte| matches!(byte, b' ' | b'\t' | b'\r' | b'\n'))
        {
            " "
        } else {
            value
        }
    }

    fn span_to_token(&self, span: &TokenSpan) -> Token {
        Token::new_with_span(
            self.semantic_span_value(span).to_string(),
            span.token_type,
            span.subtype,
            span.start,
            span.end,
        )
    }

    fn span_precedence(&self, span: &TokenSpan) -> Option<(u8, Associativity)> {
        if !matches!(
            span.token_type,
            TokenType::OpPrefix | TokenType::OpInfix | TokenType::OpPostfix
        ) {
            return None;
        }

        let op = if span.token_type == TokenType::OpPrefix {
            "u"
        } else {
            self.semantic_span_value(span)
        };

        match op {
            "#" => Some((11, Associativity::Left)),
            ":" => Some((10, Associativity::Left)),
            " " => Some((9, Associativity::Left)),
            "," => Some((8, Associativity::Left)),
            "%" => Some((7, Associativity::Left)),
            "u" => Some((6, Associativity::Right)),
            "^" => Some((5, Associativity::Left)),
            "*" | "/" => Some((4, Associativity::Left)),
            "+" | "-" => Some((3, Associativity::Left)),
            "&" => Some((2, Associativity::Left)),
            "=" | "<" | ">" | "<=" | ">=" | "<>" => Some((1, Associativity::Left)),
            _ => None,
        }
    }

    #[cold]
    fn limit_error(&self, budget: &str, limit: usize) -> ParserError {
        ParserError {
            message: format!("Formula {budget} (max {limit})"),
            position: Some(self.byte_offset(self.position)),
        }
    }
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "nodes < ast_nodes is checked before the increment"
    )]
    fn admit(&mut self, height: usize) -> Result<(), ParserError> {
        if self.nodes >= self.limits.ast_nodes {
            return Err(self.limit_error("AST node limit exceeded", self.limits.ast_nodes));
        }
        if height > self.limits.ast_height {
            return Err(self.limit_error("AST height limit exceeded", self.limits.ast_height));
        }
        self.nodes += 1;
        Ok(())
    }
    fn omitted(&mut self) -> Result<BuiltNode, ParserError> {
        self.admit(1)?;
        Ok(BuiltNode {
            node: ASTNode::new(ASTNodeType::Omitted, None),
            height: 1,
        })
    }
    pub fn parse(&mut self) -> Result<ASTNode, ParserError> {
        if let Some(error) = &self.pending_error {
            return Err(ParserError {
                message: error.message.clone(),
                position: error.position,
            });
        }
        self.nodes = 0;
        if self.tokens.is_empty() {
            return Err(ParserError {
                message: "No tokens to parse".to_string(),
                position: None,
            });
        }

        self.skip_whitespace();
        let Some(first) = self.peek() else {
            return Err(ParserError {
                message: "No tokens to parse".to_string(),
                position: None,
            });
        };

        if first.token_type == TokenType::Literal {
            let span = first;
            self.advance();
            self.skip_whitespace();
            if let Some(extra) = self.peek() {
                return Err(ParserError {
                    message: format!("Unexpected token at position {}: {extra:?}", extra.start),
                    position: Some(extra.start),
                });
            }

            let token = self.span_to_token(&span);
            self.admit(1)?;
            return Ok(ASTNode::new(
                ASTNodeType::Literal(LiteralValue::Text(token.value.clone())),
                Some(token),
            ));
        }

        let ast = self.parse_expression()?;
        self.skip_whitespace();
        if let Some(extra) = self.peek() {
            return Err(ParserError {
                message: format!("Unexpected token at position {}: {extra:?}", extra.start),
                position: Some(extra.start),
            });
        }
        Ok(ast.node)
    }

    fn parse_expression(&mut self) -> Result<BuiltNode, ParserError> {
        self.parse_bp(0)
    }

    #[expect(
        clippy::arithmetic_side_effects,
        reason = "depth counts active parse_bp frames: it is incremented once per frame and decremented on every exit, so it is bounded by the call stack"
    )]
    fn parse_bp(&mut self, min_precedence: u8) -> Result<BuiltNode, ParserError> {
        // Bound recursion so deeply nested input (e.g. `=((((...))))`) returns
        // an error instead of overflowing the stack.
        self.depth += 1;
        if self.depth > self.limits.pratt_frames {
            self.depth -= 1;
            return Err(self.limit_error("nesting too deep", self.limits.pratt_frames));
        }
        let result = self.parse_bp_inner(min_precedence);
        self.depth -= 1;
        result
    }

    #[expect(
        clippy::arithmetic_side_effects,
        reason = "precedence comes from the span_precedence table (at most 11), so precedence + 1 fits in u8"
    )]
    fn parse_bp_inner(&mut self, min_precedence: u8) -> Result<BuiltNode, ParserError> {
        let mut left = self.parse_prefix()?;

        loop {
            self.skip_whitespace();
            let Some(token) = self.peek() else {
                break;
            };

            // Postfix call: a `(` directly following a closed expression denotes
            // immediate invocation of a callable result (e.g. LAMBDA IIFE).
            if token.token_type == TokenType::Paren && token.subtype == TokenSubType::Open {
                self.advance();
                let args = self.parse_call_arguments()?;
                left = self.call(left, args)?;
                continue;
            }

            if token.token_type == TokenType::OpPostfix {
                let (precedence, _) = self
                    .span_precedence(&token)
                    .unwrap_or((0, Associativity::Left));
                if precedence < min_precedence {
                    break;
                }

                self.advance();
                left = self.unary(left, token)?;
                continue;
            }

            if token.token_type != TokenType::OpInfix {
                break;
            }

            // Inside a postfix call's argument list, treat top-level `,` as
            // an argument separator, not as the union operator.
            if self.in_call_args_depth > 0 && self.span_value(&token) == "," {
                break;
            }

            let (precedence, associativity) = self
                .span_precedence(&token)
                .unwrap_or((0, Associativity::Left));
            if precedence < min_precedence {
                break;
            }

            let op_span = token;
            self.advance();

            let next_min_precedence = if associativity == Associativity::Left {
                precedence + 1
            } else {
                precedence
            };

            let right = self.parse_bp(next_min_precedence)?;
            left = self.binary(left, right, op_span)?;
        }

        Ok(left)
    }

    fn parse_prefix(&mut self) -> Result<BuiltNode, ParserError> {
        self.skip_whitespace();
        if let Some(op_span) = self.peek()
            && op_span.token_type == TokenType::OpPrefix
        {
            self.advance();

            let (precedence, _) = self
                .span_precedence(&op_span)
                .unwrap_or((0, Associativity::Right));

            let expr = self.parse_bp(precedence)?;
            return self.unary(expr, op_span);
        }

        self.parse_primary()
    }

    fn parse_primary(&mut self) -> Result<BuiltNode, ParserError> {
        self.skip_whitespace();
        let Some(token) = self.peek() else {
            return Err(ParserError {
                message: "Unexpected end of tokens".to_string(),
                position: Some(self.byte_offset(self.position)),
            });
        };

        match token.token_type {
            TokenType::Operand => {
                self.advance();
                self.parse_operand(token)
            }
            TokenType::Func => {
                self.advance();
                self.parse_function(token)
            }
            TokenType::Paren if token.subtype == TokenSubType::Open => {
                self.advance();
                let expr = self.parse_expression()?;
                self.skip_whitespace();
                if !self.peek_is(TokenType::Paren, TokenSubType::Close) {
                    return Err(ParserError {
                        message: "Expected closing parenthesis".to_string(),
                        position: Some(self.byte_offset(self.position)),
                    });
                }
                self.advance();
                Ok(expr)
            }
            TokenType::Array if token.subtype == TokenSubType::Open => {
                self.advance();
                self.parse_array()
            }
            _ => Err(ParserError {
                message: format!("Unexpected token: {token:?}"),
                position: Some(self.byte_offset(self.position)),
            }),
        }
    }

    fn parse_operand(&mut self, span: TokenSpan) -> Result<BuiltNode, ParserError> {
        self.admit(1)?;
        let value = self.span_value(&span);
        let token = self.span_to_token(&span);

        match span.subtype {
            TokenSubType::Number => {
                let value = value.parse::<f64>().map_err(|_| ParserError {
                    message: format!("Invalid number: {value}"),
                    position: Some(self.byte_offset(self.position)),
                })?;
                Ok(BuiltNode {
                    height: 1,
                    node: ASTNode::new(
                        ASTNodeType::Literal(LiteralValue::Number(value)),
                        Some(token),
                    ),
                })
            }
            TokenSubType::Text => {
                let text = match value.strip_prefix('"').and_then(|v| v.strip_suffix('"')) {
                    Some(inner) => inner.replace("\"\"", "\""),
                    None => value.to_string(),
                };
                Ok(BuiltNode {
                    height: 1,
                    node: ASTNode::new(ASTNodeType::Literal(LiteralValue::Text(text)), Some(token)),
                })
            }
            TokenSubType::Logical => {
                let v = value.eq_ignore_ascii_case("TRUE");
                Ok(BuiltNode {
                    height: 1,
                    node: ASTNode::new(ASTNodeType::Literal(LiteralValue::Boolean(v)), Some(token)),
                })
            }
            TokenSubType::Error => {
                let error = ExcelError::from_error_string(value);
                Ok(BuiltNode {
                    height: 1,
                    node: ASTNode::new(
                        ASTNodeType::Literal(LiteralValue::Error(error)),
                        Some(token),
                    ),
                })
            }
            TokenSubType::Range => {
                let reference = ReferenceType::from_string_with_dialect(value, self.dialect)
                    .map_err(|e| ParserError {
                        message: format!("Invalid reference '{value}': {e}"),
                        position: Some(self.byte_offset(self.position)),
                    })?;
                Ok(BuiltNode {
                    height: 1,
                    node: ASTNode::new(
                        ASTNodeType::Reference {
                            original: value.to_string(),
                            reference,
                        },
                        Some(token),
                    ),
                })
            }
            _ => Err(ParserError {
                message: format!("Unexpected operand subtype: {:?}", span.subtype),
                position: Some(self.byte_offset(self.position)),
            }),
        }
    }

    #[expect(
        clippy::arithmetic_side_effects,
        reason = "child heights are at most the AST height limit and the number of admitted nodes, so 1 + height cannot overflow"
    )]
    fn parse_function(&mut self, func_span: TokenSpan) -> Result<BuiltNode, ParserError> {
        let Some(name) = self.span_value(&func_span).strip_suffix('(') else {
            return Err(ParserError {
                message: "Invalid function token".to_string(),
                position: Some(self.byte_offset(self.position)),
            });
        };
        let name = name.to_string();
        let args = self.parse_function_arguments()?;

        let this_is_volatile = self
            .volatility_classifier
            .as_ref()
            .map(|f| f(name.as_str()))
            .unwrap_or(false);
        let args_volatile = args.volatile;

        let height = 1 + args.height;
        self.admit(height)?;
        let func_token = self.span_to_token(&func_span);
        Ok(BuiltNode {
            height,
            node: ASTNode::new_with_volatile(
                ASTNodeType::Function {
                    name,
                    args: args.nodes,
                },
                Some(func_token),
                this_is_volatile || args_volatile,
            ),
        })
    }

    /// Parse arguments for a postfix call (immediate invocation), where the
    /// opening `(` is a `Paren:Open` and the matching `)` is a `Paren:Close`.
    /// Caller has already consumed the opening paren. See the classic parser
    /// version for details on how top-level `,` is handled.
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "in_call_args_depth is incremented and decremented once per call, so it counts active calls and is bounded by the Pratt-frame limit"
    )]
    fn parse_call_arguments(&mut self) -> Result<BuiltArgs, ParserError> {
        let mut args = BuiltArgs::default();

        self.skip_whitespace();
        if self.peek_is(TokenType::Paren, TokenSubType::Close) {
            self.advance();
            return Ok(args);
        }

        self.in_call_args_depth += 1;
        let result = (|| -> Result<BuiltArgs, ParserError> {
            let mut expecting_argument = true;
            let mut saw_argument = false;
            loop {
                self.skip_whitespace();
                let Some(token) = self.peek() else {
                    return Err(ParserError {
                        message: "Unterminated call argument list".to_string(),
                        position: Some(self.byte_offset(self.position)),
                    });
                };

                let is_separator = (token.token_type == TokenType::Sep
                    && token.subtype == TokenSubType::Arg)
                    || (token.token_type == TokenType::OpInfix && self.span_value(&token) == ",");
                let is_close =
                    token.token_type == TokenType::Paren && token.subtype == TokenSubType::Close;

                if expecting_argument {
                    if is_close {
                        if saw_argument {
                            args.push(self.omitted()?);
                        }
                        self.advance();
                        return Ok(std::mem::take(&mut args));
                    }
                    if is_separator {
                        args.push(self.omitted()?);
                        saw_argument = true;
                        self.advance();
                    } else {
                        args.push(self.parse_expression()?);
                        saw_argument = true;
                        expecting_argument = false;
                    }
                } else if is_separator {
                    self.advance();
                    expecting_argument = true;
                } else if is_close {
                    self.advance();
                    return Ok(std::mem::take(&mut args));
                } else {
                    return Err(ParserError {
                        message: format!("Expected ',' or ')' in call arguments, got {token:?}"),
                        position: Some(self.byte_offset(self.position)),
                    });
                }
            }
        })();
        self.in_call_args_depth -= 1;
        result
    }

    fn parse_function_arguments(&mut self) -> Result<BuiltArgs, ParserError> {
        let mut args = BuiltArgs::default();

        self.skip_whitespace();
        if self.peek_is(TokenType::Func, TokenSubType::Close) {
            self.advance();
            return Ok(args);
        }

        let mut expecting_argument = true;
        let mut saw_argument = false;
        loop {
            self.skip_whitespace();
            let Some(token) = self.peek() else {
                return Err(ParserError {
                    message: "Unterminated function argument list".to_string(),
                    position: Some(self.byte_offset(self.position)),
                });
            };

            let is_separator =
                token.token_type == TokenType::Sep && token.subtype == TokenSubType::Arg;
            let is_close =
                token.token_type == TokenType::Func && token.subtype == TokenSubType::Close;

            if expecting_argument {
                if is_close {
                    if saw_argument {
                        args.push(self.omitted()?);
                    }
                    self.advance();
                    return Ok(args);
                }
                if is_separator {
                    args.push(self.omitted()?);
                    saw_argument = true;
                    self.advance();
                } else {
                    args.push(self.parse_expression()?);
                    saw_argument = true;
                    expecting_argument = false;
                }
            } else if is_separator {
                self.advance();
                expecting_argument = true;
            } else if is_close {
                self.advance();
                return Ok(args);
            } else {
                return Err(ParserError {
                    message: format!("Expected ',' or ')' in function arguments, got {token:?}"),
                    position: Some(self.byte_offset(self.position)),
                });
            }
        }
    }

    #[expect(
        clippy::arithmetic_side_effects,
        reason = "child heights are at most the AST height limit and the number of admitted nodes, so 1 + height cannot overflow"
    )]
    fn append_array_item(
        &mut self,
        row: &mut Vec<ASTNode>,
        height: &mut usize,
        volatile: &mut bool,
    ) -> Result<(), ParserError> {
        let child = self.parse_expression()?;
        *height = (*height).max(1 + child.height);
        *volatile |= child.contains_volatile;
        row.push(child.node);
        Ok(())
    }
    fn finish_array(
        &mut self,
        rows: Vec<Vec<ASTNode>>,
        height: usize,
        volatile: bool,
    ) -> Result<BuiltNode, ParserError> {
        self.admit(height)?;
        Ok(BuiltNode {
            height,
            node: ASTNode::new_with_volatile(ASTNodeType::Array(rows), None, volatile),
        })
    }
    fn parse_array(&mut self) -> Result<BuiltNode, ParserError> {
        let mut rows = Vec::new();
        let mut current_row = Vec::new();
        let mut height = 1;
        let mut contains_volatile = false;

        self.skip_whitespace();
        if self.peek_is(TokenType::Array, TokenSubType::Close) {
            self.advance();
            return self.finish_array(rows, 1, false);
        }

        self.append_array_item(&mut current_row, &mut height, &mut contains_volatile)?;

        while self.position < self.tokens.len() {
            self.skip_whitespace();
            let Some(token) = self.peek() else {
                break;
            };

            // Every arm advances `position` or leaves the loop. A separator
            // with another subtype (possible in an external TokenStream) is an
            // unexpected token, not a no-op that would loop forever.
            match (token.token_type, token.subtype) {
                (TokenType::Sep, TokenSubType::Arg) => {
                    self.advance();
                    self.append_array_item(&mut current_row, &mut height, &mut contains_volatile)?;
                }
                (TokenType::Sep, TokenSubType::Row) => {
                    self.advance();
                    rows.push(current_row);
                    current_row = Vec::new();
                    self.append_array_item(&mut current_row, &mut height, &mut contains_volatile)?;
                }
                (TokenType::Array, TokenSubType::Close) => {
                    self.advance();
                    rows.push(current_row);
                    break;
                }
                _ => {
                    return Err(ParserError {
                        message: format!("Unexpected token in array: {token:?}"),
                        position: Some(self.byte_offset(self.position)),
                    });
                }
            }
        }

        // Array evaluation requires a rectangular shape. Reject malformed
        // literals before returning an AST to assignment or ingestion; never
        // silently pad missing elements.
        if let Some(first) = rows.first()
            && rows.iter().any(|row| row.len() != first.len())
        {
            return Err(ParserError {
                message: "Array rows must have equal length".to_string(),
                position: Some(self.byte_offset(self.position.saturating_sub(1))),
            });
        }

        self.finish_array(rows, height, contains_volatile)
    }
}

impl TryFrom<&str> for Parser {
    type Error = TokenizerError;

    fn try_from(formula: &str) -> Result<Self, Self::Error> {
        Self::new(formula)
    }
}

impl TryFrom<String> for Parser {
    type Error = TokenizerError;

    fn try_from(formula: String) -> Result<Self, Self::Error> {
        Self::new(formula)
    }
}

impl From<&TokenStream> for Parser {
    fn from(stream: &TokenStream) -> Self {
        Self::from_token_stream(stream)
    }
}

impl FromStr for ASTNode {
    type Err = ParserError;

    fn from_str(formula: &str) -> Result<Self, Self::Err> {
        parse(formula)
    }
}

impl TryFrom<&str> for ASTNode {
    type Error = ParserError;

    fn try_from(formula: &str) -> Result<Self, Self::Error> {
        parse(formula)
    }
}

impl TryFrom<String> for ASTNode {
    type Error = ParserError;

    fn try_from(formula: String) -> Result<Self, Self::Error> {
        parse(formula)
    }
}

impl Parser {
    pub fn builder() -> ParserBuilder {
        ParserBuilder::default()
    }
}

#[derive(Default)]
pub struct ParserBuilder {
    dialect: FormulaDialect,
    volatility_classifier: Option<VolatilityClassifierArc>,
    limits: ParserLimits,
}

impl ParserBuilder {
    pub fn limits(mut self, limits: ParserLimits) -> Self {
        self.limits = limits;
        self
    }
    pub fn dialect(mut self, dialect: FormulaDialect) -> Self {
        self.dialect = dialect;
        self
    }

    pub fn with_volatility_classifier<F>(mut self, f: F) -> Self
    where
        F: Fn(&str) -> bool + Send + Sync + 'static,
    {
        self.volatility_classifier = Some(Arc::new(f));
        self
    }

    pub fn build<T: AsRef<str>>(self, formula: T) -> Result<Parser, TokenizerError> {
        let mut parser = Parser::new_with_limits(formula.as_ref(), self.dialect, self.limits)?;
        if let Some(classifier) = self.volatility_classifier {
            parser = parser.with_volatility_classifier(move |name| classifier(name));
        }
        Ok(parser)
    }

    pub fn parse<T: AsRef<str>>(self, formula: T) -> Result<ASTNode, ParserError> {
        let mut parser = self.build(formula)?;
        parser.parse()
    }
}

/// Normalise a reference string to its canonical form
pub fn normalise_reference(reference: &str) -> Result<String, ParsingError> {
    let ref_type = ReferenceType::from_string(reference)?;
    Ok(ref_type.to_string())
}

pub fn parse<T: AsRef<str>>(formula: T) -> Result<ASTNode, ParserError> {
    parse_with_dialect(formula, FormulaDialect::Excel)
}

pub fn parse_with_dialect<T: AsRef<str>>(
    formula: T,
    dialect: FormulaDialect,
) -> Result<ASTNode, ParserError> {
    let mut parser = Parser::new_with_dialect(formula, dialect)?;
    parser.parse()
}

/// Parse a single formula and annotate volatility using the provided classifier.
/// This is a convenience wrapper around `Parser::with_volatility_classifier`.
pub fn parse_with_volatility_classifier<T, F>(
    formula: T,
    classifier: F,
) -> Result<ASTNode, ParserError>
where
    T: AsRef<str>,
    F: Fn(&str) -> bool + Send + Sync + 'static,
{
    parse_with_dialect_and_volatility_classifier(formula, FormulaDialect::Excel, classifier)
}

pub fn parse_with_dialect_and_volatility_classifier<T, F>(
    formula: T,
    dialect: FormulaDialect,
    classifier: F,
) -> Result<ASTNode, ParserError>
where
    T: AsRef<str>,
    F: Fn(&str) -> bool + Send + Sync + 'static,
{
    let mut parser =
        Parser::new_with_dialect(formula, dialect)?.with_volatility_classifier(classifier);
    parser.parse()
}

/// Efficient batch parser with an internal token cache and optional volatility classifier.
///
/// The cache is keyed by the original formula string; repeated formulas across a batch
/// (very common in spreadsheets) will avoid re-tokenization and whitespace filtering.
pub struct BatchParser {
    include_whitespace: bool,
    volatility_classifier: Option<VolatilityClassifierArc>,
    token_cache: crate::token_cache::TokenCache,
    limits: ParserLimits,
    dialect: FormulaDialect,
}

impl BatchParser {
    pub fn builder() -> BatchParserBuilder {
        BatchParserBuilder::default()
    }

    /// Parse a formula using the internal cache and configured classifier.
    pub fn parse(&mut self, formula: &str) -> Result<ASTNode, ParserError> {
        self.limits.check_source(formula)?;
        let (source, spans) = if let Some(pair) = self.token_cache.get(formula) {
            pair
        } else {
            let mut spans =
                crate::tokenizer::tokenize_spans_with_limits(formula, self.dialect, self.limits)?;
            let source: Arc<str> = Arc::from(formula);
            if !self.include_whitespace {
                spans.retain(|t| t.token_type != TokenType::Whitespace);
            }

            let spans: Arc<[TokenSpan]> = Arc::from(spans.into_boxed_slice());
            self.token_cache
                .insert(Arc::clone(&source), Arc::clone(&spans));
            (source, spans)
        };

        let mut parser = Parser::from_source_and_tokens(source, spans, self.dialect);
        parser.limits = self.limits;
        if let Some(classifier) = self.volatility_classifier.clone() {
            parser = parser.with_volatility_classifier(move |name| classifier(name));
        }
        parser.parse()
    }
}

pub struct BatchParserBuilder {
    limits: ParserLimits,
    cache_entries: usize,
    cache_bytes: usize,
    include_whitespace: bool,
    volatility_classifier: Option<VolatilityClassifierArc>,
    dialect: FormulaDialect,
}

impl Default for BatchParserBuilder {
    fn default() -> Self {
        Self {
            include_whitespace: false,
            volatility_classifier: None,
            dialect: FormulaDialect::default(),
            limits: ParserLimits::default(),
            cache_entries: 16_384,
            cache_bytes: 8 * 1024 * 1024,
        }
    }
}
impl BatchParserBuilder {
    pub fn limits(mut self, limits: ParserLimits) -> Self {
        self.limits = limits;
        self
    }
    /// Set FIFO cache payload bounds. Zero entries disables retention.
    pub fn cache_capacity(mut self, entries: usize, bytes: usize) -> Self {
        self.cache_entries = entries;
        self.cache_bytes = bytes;
        self
    }
    pub fn include_whitespace(mut self, include: bool) -> Self {
        self.include_whitespace = include;
        self
    }

    pub fn with_volatility_classifier<F>(mut self, f: F) -> Self
    where
        F: Fn(&str) -> bool + Send + Sync + 'static,
    {
        self.volatility_classifier = Some(Arc::new(f));
        self
    }

    pub fn dialect(mut self, dialect: FormulaDialect) -> Self {
        self.dialect = dialect;
        self
    }

    pub fn build(self) -> BatchParser {
        BatchParser {
            include_whitespace: self.include_whitespace,
            volatility_classifier: self.volatility_classifier,
            token_cache: crate::token_cache::TokenCache::new(self.cache_entries, self.cache_bytes),
            limits: self.limits,
            dialect: self.dialect,
        }
    }
}