use std::collections::{HashMap, HashSet}; use std::rc::Rc; use super::{Area, BinOp, Ev, Expr, Reference, SheetSel, UnOp, Value, Workbook, may_be_cut}; use gridcraft_core::{CellRef, MAX_COLS, MAX_ROWS, RangeRef}; /// SUMIF and AVERAGEIF with a sum range: Excel sizes the sum range like the criteria range. pub(super) fn resizes_sum_range(name: &str, args: usize) -> bool { args == 3 && matches!(name, "SUMIF" | "AVERAGEIF") } /// Height and width of a single-area reference or an array argument. pub(super) fn ev_shape(ev: &Ev) -> Option<(u32, u32)> { match ev { Ev::R(areas) => match areas.as_slice() { [a] => Some((a.range.height(), a.range.width())), _ => None, }, Ev::V(Value::Array(a)) => Some((u32::try_from(a.rows).unwrap_or(u32::MAX), u32::try_from(a.cols).unwrap_or(u32::MAX))), Ev::V(_) => Some((1, 1)), Ev::L(_) => None, } } /// The range SUMIF/AVERAGEIF add up: from the sum range's top-left cell, as many rows and columns /// as the criteria range (`height` × `width`), cut off at the sheet's edge. pub fn resized_sum_range(sum: RangeRef, height: u32, width: u32) -> RangeRef { let row = sum.start.row.saturating_add(height.saturating_sub(1)).min(MAX_ROWS - 1); let col = sum.start.col.saturating_add(width.saturating_sub(1)).min(MAX_COLS - 1); RangeRef::new(sum.start, CellRef::new(row, col)) } /// Collects the static references of an expression with their sheets resolved; `dynamic` is /// set when the formula uses INDIRECT/OFFSET/tables (or a name that can't be resolved now) whose /// targets can change between recalcs. /// /// Defined names are resolved here, not treated as dynamic: a name holding a range contributes /// that range, a name holding a LAMBDA contributes the references inside its body (its /// parameters, and LET variables, are bound names, not lookups), names referring to names follow /// the chain to a bounded depth. A column of cells calling one LAMBDA name is then an ordinary /// static dependency, re-evaluated when its inputs change and only then. Changing a name's /// definition is a structural edit (full rebuild), and the engine re-resolves the readers of the /// hidden names its commands rewrite without one, in manual mode too (their values then wait for /// the next calculation, their precedents don't), so the graph follows the definitions. Names with /// relative references (evaluated relative to the using cell), unknown names, unparsable names, /// sheet-scoped names used from another sheet, cycles between names and chains deeper than the /// bound stay dynamic. A LAMBDA name calling itself is not a cycle here: the call reads what its /// body reads. The evaluator reads a definition with the caller's LET variables and LAMBDA /// parameters in scope, so a name whose definition leaves free a name the caller binds is dynamic. /// /// The cases that stay dynamic, in one list (docs/target-app-parity.md points here): /// - INDIRECT, OFFSET and the volatile functions (`call_reads`), in a formula or a name; /// - tables (structured references, and a name that is not defined, as a table name is); /// - names with relative references, and unparsable names; /// - a sheet prefix naming no sheet, and a sheet-scoped name used from another sheet; /// - cycles between names, and chains deeper than [`NAME_DEPTH`]; /// - a name given to SUMIF or AVERAGEIF as a range (the sum range is sized from the criteria /// range, known statically only for plain references); /// - a spill reference (`A1#`) in an operand of the range operator, directly or through a name; /// - a LET variable, LAMBDA parameter or recursive self-call in an operand of the range operator; /// - a name whose definition leaves free a name the caller binds; /// - a formula mentioning a name whose own array covers cells it reads, while it does (decided /// when the array is laid out, not here: `Calc::mark_spill_reader` in `recalc.rs`); /// - a database function, in a formula or in a name's definition (its computed criteria read /// cells shifted from the criteria cells' references, see `computed_criterion`); /// - GETPIVOTDATA given anything but a plain reference into a report, and in a name's definition /// (`call_reads`); /// - a formula that holds a name, a LET variable, a LAMBDA parameter or a call to a function not /// built in, and whose areas (its references, the boxes of its range operands, the areas of the /// names it reads) include one the evaluator may cut to the sheet's used range ([`may_be_cut`]: /// whole columns or rows, or a block over 16,384 cells running to the sheet's edge, or over /// 1,048,576 cells): what the cut array holds (its shape, its blanks) depends on cells outside the /// area, which the graph has no edge for. A formula holding such an area and no name is static /// (`=ROWS(A:A+0)` misses the used range growing). This follows `read_range` and `trim_lines`; /// TRIMRANGE cuts every reference by its own rule, but its result depends only on the cells /// inside the area; /// - a formula that holds a name, a LET variable, a LAMBDA parameter or a call to a function not /// built in, and calls SUBTOTAL or AGGREGATE, itself or in a definition it reads: these two /// charge the sizes left after cutting each reference argument to the used range against a budget /// of `MAX_CELLS` cells per call, so past it their result depends on cells no reference names. /// Arguments can repeat (a name, a LET variable, a recursive LAMBDA's union), so the walk does not /// try to bound them. With plain references only, such a call is static, as before; /// - past the graph build's bounds: [`MAX_PRECEDENT_NODES`], [`MAX_NAME_AREAS`], /// [`MAX_BUILD_NAME_AREAS`], [`MAX_BUILD_FREE_NAMES`], [`MAX_BUILD_FOLDED_FREE_NAMES`] and /// [`MAX_BUILD_NAME_TEXT`]. /// /// Resolves names through a fresh [`NameCache`]; a graph build resolving many formulas shares one /// through [`precedents_with`]. pub fn precedents(wb: &Workbook, sheet: usize, e: &Expr) -> (Vec, bool) { precedents_with(wb, sheet, e, &mut NameCache::default()) } /// [`precedents`] with the defined names resolved through `names`, shared across the formulas of /// one graph build. pub fn precedents_with(wb: &Workbook, sheet: usize, e: &Expr, names: &mut NameCache) -> (Vec, bool) { // Room for the formula's list and a few nested ones (a range's operands, a name's // definition), without growing. let mut taken = Vec::with_capacity(4); taken.push(Taken::default()); let mut walk = Walk { wb, names, nodes: 0, from_names: 0, overflowed: false, taken, database: false, frames: Vec::new(), spill: false, names_met: false, budgeted: false, }; let (mut out, mut dynamic) = walk.collect(sheet, e, 0); // A database function's computed criteria read cells no reference names (see // `computed_criterion`): a formula calling one is dynamic. dynamic |= walk.database; // SUBTOTAL and AGGREGATE cut every reference argument to the used range and charge what is left // against a budget of `MAX_CELLS` cells per call: past it, their result depends on cells no // reference names. A name, LET variable or LAMBDA parameter can hand a call the same areas any // number of times, so with one the formula is dynamic, as it was before names were resolved // statically; with plain references only it stays static, as it always was. dynamic |= walk.names_met && walk.budgeted; // Each area once: a formula mentioning a name or a range k times depends on it once. remove_repeats(&mut out); // An area the evaluator may cut, in a formula that holds a name: the formulas that were dynamic // before names were resolved statically. The formula's list holds its references, the boxes of // its range operands (each covering the references and names' areas inside it, and cut where one // of them is: a box only grows) and the areas of the names it reads, those of the names their // definitions read included. A name whose areas the walk drops (past a bound) is dynamic, and so // is the formula reading it. This is the one place the rule is applied. if walk.names_met && !dynamic { dynamic = out.iter().any(|a| may_be_cut(&a.range)); } (out, dynamic) } /// Lists of up to this many areas, or boxes, are searched by comparison rather than through a set /// or an index: most formulas hold a handful of areas, and a set costs an allocation and a hash per /// area. pub(crate) const SCANNED_UP_TO: usize = 16; /// Removes the repeats from `list`, keeping the first of each area in order. fn remove_repeats(list: &mut Vec) { if list.len() <= SCANNED_UP_TO { // Each area is compared with those kept before it, which move to the front. let mut kept = 0; for i in 0..list.len() { let Some(&area) = list.get(i) else { break }; if !list.get(..kept).is_some_and(|before| before.contains(&area)) { if let Some(slot) = list.get_mut(kept) { *slot = area; } kept += 1; } } list.truncate(kept); return; } let mut distinct: HashSet> = HashSet::with_capacity_and_hasher(list.len(), Default::default()); list.retain(|a| distinct.insert(*a)); } /// Names referring to names are followed this many levels before the formula is called dynamic. const NAME_DEPTH: usize = 8; /// Most expression nodes one precedent walk visits, before giving up and marking the formula /// dynamic. Every node of the formula counts one, and so does every node of the name definitions the /// walk parses (a name the cache already holds costs nothing), except an inner link of a chain of one /// shape, which counts with the chain's outermost node: a parenthesis directly inside a parenthesis, /// a `%` directly on a `%`, an operator other than a range as the left operand of another, a range as /// the left operand of a range, and an invoked result invoked again. The walk's explicit stack holds /// at most the children of the nodes visited, plus two steps for each, so the bound limits its /// memory too. The same flag (`link` on [`Step::Visit`]) decides that a chain of ranges shares one /// box list, so a change to this counting rule must not change that. const MAX_PRECEDENT_NODES: usize = 1_000_000; /// Most areas one defined name contributes, and most a formula takes from the names it mentions, /// before the name or the formula is called dynamic. A name's areas are stored in the graph for /// every formula reading it, so a name of many single cells, or one summing many such names, would /// otherwise make each short formula reading it as large as all of them; dynamic is always a correct /// answer. A formula's own references don't count. In a definition, a span of sheets /// (`First:Last!A1`) counts one area per sheet at each mention, and a range operand the boxes it /// closes into, one per sheet at each mention, against the list they join (the definition's, or an /// enclosing range operand's): the list as it stands, and where that passes this bound, the list /// without its repeats (see `fit`). const MAX_NAME_AREAS: usize = 1024; /// Most areas the formulas of one graph build may take from names, all together, each area counted /// once whatever its size. A name of [`MAX_NAME_AREAS`] areas read from a whole column of cells /// would store them once per cell (a million readers: a thousand million areas); past this budget /// (a million areas of 24 bytes, about 25 MB) the further readers are dynamic. The graph indexes a /// range of up to 64 columns once per column, as it does for a formula's own references, so the /// memory of that index is not what this budget bounds. A workbook of tens of thousands of LAMBDA /// calls over a named range stores a few areas per reader, far below it. The names a build /// resolves keep their own areas too, as many again at most: a definition that is only another /// name (`copy_k = wide_name`) costs three bytes of text but copies all the areas of the name it /// repeats, so past this budget the further names are dynamic, and a workbook of many such names /// costs no more than this. const MAX_BUILD_NAME_AREAS: usize = 1 << 20; /// Most free names (left unbound by a definition) the names one graph build resolves keep, all /// together; past it the further names are dynamic. A summary keeps each as a number standing for /// its spelling, which the build holds once ([`NameCache`]'s `spellings`), so a long name kept by /// many names costs its length once. const MAX_BUILD_FREE_NAMES: usize = 1 << 20; /// Most free names one graph build copies from the summary of a name into the definition using it, /// all together, counted before each copy (a copy skipped because the definition can't keep its /// free names, see `Frame::past_free_budget`, counts as made); past it the definition that would /// copy is dynamic. A name leaves free those of the names it uses too, so names sharing their free /// names copy the shared ones once per use: two hundred names each summing the same three hundred /// names, used by each of a thousand names, copy 60 million. The other budgets don't bound this: /// [`MAX_BUILD_FREE_NAMES`] counts the free names a definition keeps, not the copies that made /// them, and a name using another of free names it already holds keeps no more for each copy. /// This budget, about 268 million copies, is large enough that the copies of the three-tier shapes /// measured, up to three hundred leaves, two hundred children and twelve hundred parents (72 /// million copies), fit within it, and small enough that the copying a hostile file can force takes /// seconds, not minutes. Whether the formulas reading such a shape stay static depends on the other /// bounds too: the largest of those shapes holds about 5 MiB of definitions, past /// [`MAX_BUILD_NAME_TEXT`], so some of its readers are dynamic. const MAX_BUILD_FOLDED_FREE_NAMES: usize = 1 << 28; #[cfg(test)] thread_local! { /// [`MAX_BUILD_FOLDED_FREE_NAMES`] on this thread, which a test lowers to build at the budget. pub(crate) static FOLD_BUDGET: std::cell::Cell = const { std::cell::Cell::new(MAX_BUILD_FOLDED_FREE_NAMES) }; } #[cfg(not(test))] fn fold_budget() -> usize { MAX_BUILD_FOLDED_FREE_NAMES } #[cfg(test)] fn fold_budget() -> usize { FOLD_BUDGET.with(std::cell::Cell::get) } /// Most definition text one graph build parses to resolve names, in bytes. A workbook-wide name is /// resolved for each sheet that uses it (its unqualified references point at that sheet), so a /// thousand long names used from two hundred sheets would parse 1.6 GB of definitions; past this /// budget the further names are dynamic. A workbook of LAMBDA names used from a few sheets parses a /// few kilobytes. const MAX_BUILD_NAME_TEXT: usize = 4 << 20; /// A name as the walk resolves it: lower-cased, its scope, and the sheet its unqualified /// references resolve against. type NameKey = (String, Option, usize); /// The defined names of a workbook by lower-cased name and scope, built once for a graph build or a /// recalculation pass: [`Workbook::name`] scans every name at every lookup, so a build of many /// formulas over many names cost formulas × names. pub struct NameIndex { by_name: HashMap<(String, Option), usize>, } impl NameIndex { pub fn new(wb: &Workbook) -> Self { #[cfg(test)] NAME_INDEXES_BUILT.with(|n| n.set(n.get().saturating_add(1))); let mut by_name = HashMap::new(); for (i, n) in wb.names.iter().enumerate() { by_name.entry((n.name.to_ascii_lowercase(), n.scope)).or_insert(i); } NameIndex { by_name } } /// Where in `wb.names` the name `name` seen from `sheet` is, as [`Workbook::name`] finds it: one /// scoped to that sheet first, then a workbook-wide one. Its unindexed twin is /// [`Workbook::name_position`], which must find the same name. pub fn find(&self, name: &str, sheet: usize) -> Option { let lower = name.to_ascii_lowercase(); self.by_name.get(&(lower.clone(), Some(sheet))).or_else(|| self.by_name.get(&(lower, None))).copied() } } /// Name lookups of one graph build or one recalculation pass answered by a scan of the workbook's /// names ([`Workbook::name_position`]) before [`NameLookup`] builds a [`NameIndex`] at the next one. /// A speed switch, not a limit: the scan and the index find the same name, so no result depends on /// it. Measured 2026-11-18 (release build, four-core 2011 iMac), ten one-cell edits of a formula /// reading one name: with the index built at the first lookup they took 0.4 ms with 50 names, /// 10.7 ms with 2,000 and 1.6 to 2.8 s with 200,000 (a scan at every lookup: 0.09, 0.18 and 28 ms); /// with the first 16 lookups scanned, 0.15 ms, 0.33 ms and about 60 ms, while a full recalculation /// of 20,000 formulas over 50 names stayed within noise. pub(crate) const NAME_LOOKUPS_SCANNED: usize = 16; #[cfg(test)] thread_local! { /// [`NameIndex`]es built on this thread, which a test reads. pub(crate) static NAME_INDEXES_BUILT: std::cell::Cell = const { std::cell::Cell::new(0) }; } /// Finds defined names for one graph build or one recalculation pass: by a scan of the workbook's /// names for the first [`NAME_LOOKUPS_SCANNED`] lookups, then through a [`NameIndex`] built at the /// next one. An edit that looks up a few names in a workbook of many doesn't pay for an index of /// all of them, and a build or pass that looks up many doesn't scan the list at each. #[derive(Default)] pub struct NameLookup { index: Option, scans: usize, } impl NameLookup { /// Where in `wb.names` the name `name` seen from `sheet` is (see [`NameIndex::find`]). pub fn find(&mut self, wb: &Workbook, name: &str, sheet: usize) -> Option { if let Some(index) = &self.index { return index.find(name, sheet); } if self.scans < NAME_LOOKUPS_SCANNED { self.scans += 1; return wb.name_position(name, sheet); } self.index.insert(NameIndex::new(wb)).find(name, sheet) } } /// What each defined name contributes to the formulas using it, resolved once per graph build. /// /// The workbook's names don't change while a graph is built, so a name read from thousands of /// cells, or mentioned many times inside another name's definition, is resolved the first time /// and looked up after that, once per sheet it is used from (unqualified references point at that /// sheet). The work of a build is then linear in the size of the definitions times the sheets using /// them, however often they are referenced, and bounded by [`MAX_BUILD_NAME_TEXT`]; followed afresh /// at every mention, a chain of names each mentioning the previous one k times would cost k^depth /// per use. A name met again from its own definition (a recursive LAMBDA) adds nothing; met again /// from deeper down the chain it is a cycle, and the names on it are dynamic. A chain cut by /// [`NAME_DEPTH`] is dynamic from the cut up to the formula, and the cache keeps that answer for /// those names even where a shorter chain reaches them later: dynamic is always a correct answer, /// only a slower one. #[derive(Default)] pub struct NameCache { /// Keyed by the name, its scope and the sheet its unqualified references resolve against. entries: HashMap, /// Finds the workbook's names (see [`NameLookup`]). lookup: NameLookup, /// Areas handed to the formulas of the build from the names they mention, counted against /// [`MAX_BUILD_NAME_AREAS`]. stored: usize, /// Characters of definitions parsed in the build, counted against [`MAX_BUILD_NAME_TEXT`]. parsed: usize, /// Areas kept in `entries` for the names resolved in the build, counted against /// [`MAX_BUILD_NAME_AREAS`]. cached: usize, /// Free names kept in `entries`, counted against [`MAX_BUILD_FREE_NAMES`]. free_kept: usize, /// The spelling (case-folded) of each free name the build met in a definition, and of each LET /// variable and LAMBDA parameter it bound, numbered: the summaries, the definitions being /// resolved and the bound names in scope hold the numbers. It grows with the text of the /// formulas and definitions the build reads, each spelling once. spellings: HashMap, /// Free names copied from the summaries of names into the definitions using them, counted /// against [`MAX_BUILD_FOLDED_FREE_NAMES`]. folded: usize, } impl NameCache { /// The number standing for the spelling `name`, numbered the first time it is met. fn spelling(&mut self, name: String) -> usize { let next = self.spellings.len(); *self.spellings.entry(name).or_insert(next) } /// Free names copied into definitions so far (see [`MAX_BUILD_FOLDED_FREE_NAMES`]). #[cfg(test)] pub(crate) fn folded(&self) -> usize { self.folded } /// Bytes the free names kept in the build hold: their numbers in the summaries, and each /// spelling once (those of bound names included). #[cfg(test)] pub(crate) fn free_name_bytes(&self) -> usize { let spelled: usize = self.spellings.keys().map(String::len).sum(); spelled.saturating_add(self.free_kept.saturating_mul(std::mem::size_of::())) } /// A cache whose budget on areas taken from names counts on from `stored`. pub fn with_stored(stored: usize) -> Self { NameCache { stored, ..Default::default() } } /// Areas handed to formulas from names so far, the count [`NameCache::with_stored`] takes. pub fn stored(&self) -> usize { self.stored } /// Gives back what a formula was charged, before it is resolved again or removed. pub fn give_back(&mut self, areas: usize) { self.stored = self.stored.saturating_sub(areas); } } enum NameEntry { /// Being resolved further up the current chain, entered at `depth`: met again from its own /// definition it is a direct self-call, from deeper down a cycle. Resolving { depth: usize, }, Resolved(Summary), } /// What a defined name brings to the formulas using it, whichever use resolved it: each use /// applies its own context ([`Walk::apply`]). struct Summary { /// Shared with the range operands holding the name as its boxes (see [`Deferred`]). areas: Rc<[Area]>, /// One box per sheet around `areas` ([`bounding_boxes`]), made at the name's first use in a /// range's operand: all a range operand takes from the name for its own box. At most as many /// as `areas`. boxes: Option>, dynamic: bool, /// The names the definition leaves free, those of the names it uses included (folded), as the /// numbers of their spellings, sorted. A dynamic name keeps none: every formula using it is /// dynamic whatever its caller binds. free: Vec, /// Whether the definition holds a spill reference, those of the names it uses included. spill: bool, /// Whether the definition calls SUBTOTAL or AGGREGATE, those of the names it uses included. budgeted: bool, } /// Adds `range` to `out` on the sheet(s) `r` names, or on `sheet` for an unqualified reference; a /// sheet that doesn't exist contributes nothing (evaluation reports #REF!). A span of sheets adds /// one area per sheet, at each mention: where they don't [`fit`] in `out` within `most` it adds /// none and returns false, so repeating a span in a definition never takes `out` past `most` areas. /// The boxes a range operand closes into are counted the same way against the list they join /// (`Walk::collect`). `distinct` is what `out`'s [`Taken`] knows of its repeats. fn push_area( wb: &Workbook, sheet: usize, out: &mut Vec, mut distinct: Option<&mut Distinct>, r: &Reference, range: RangeRef, most: usize, ) -> bool { match &r.sheet { SheetSel::Current => out.push(Area { sheet, range }), SheetSel::Named(n) => { if let Some(i) = wb.sheet_index(n) { out.push(Area { sheet: i, range }); } } SheetSel::Span(a, b) => { if let (Some(i), Some(j)) = (wb.sheet_index(a), wb.sheet_index(b)) { let sheets = i.abs_diff(j).saturating_add(1); if !fit(out, distinct.as_deref_mut(), sheets, most) { return false; } // A span whose areas the list already holds without repeats would add only repeats, // which the next removal drops: they are counted, not added. let span = (i.min(j), i.max(j), range); if let Some(d) = distinct { if d.spans.contains(&span) { d.repeats = d.repeats.saturating_add(sheets); return true; } d.spans_added.push(span); } for s in i.min(j)..=i.max(j) { out.push(Area { sheet: s, range }); } } } } true } /// Whether `extra` more areas fit in `list` within `most`, the `extra` counted in full whether or /// not `list` holds them. Where they would not, the repeats are removed from `list` (its first of /// each kept, in order) and it is counted again: repeats are removed from a definition's areas /// after collecting anyway, so a reference written many times before a span of sheets counts as it /// does after the span, and a span of up to half `most` sheets, repeated alone in a definition, /// fits however often it is written. Only the areas added since the last removal are looked at /// (`distinct` holds the ones before, which have no repeats; without it the whole list is): a /// definition repeating a span of 512 sheets 700 times would otherwise pass over a full list of /// 1,024 areas at each mention. `distinct` holds no more areas than the list held at a removal, /// at most `most` after a count that fits plus the areas added since. Past a count that fails /// even so, the name is dynamic and stores no areas, and the walk adds no more references or boxes /// to it (`Walk::collect`). A range operand's list may hold names as their boxes (see `Walk::apply`): /// it is counted with their areas, which are put back in their place before repeats are removed. fn fit(list: &mut Vec, distinct: Option<&mut Distinct>, extra: usize, most: usize) -> bool { let mut spare = Distinct::default(); let distinct = match distinct { Some(d) => d, None => &mut spare, }; if list.len().saturating_add(distinct.repeats).saturating_add(distinct.hidden).saturating_add(extra) <= most { return true; } distinct.expand(list); let added = list.split_off(distinct.clean.min(list.len())); #[cfg(test)] AREAS_SIFTED.with(|n| n.set(n.get().saturating_add(added.len()))); list.extend(added.into_iter().filter(|a| distinct.seen.insert(*a))); distinct.clean = list.len(); distinct.repeats = 0; let Distinct { spans, spans_added, .. } = distinct; spans.extend(spans_added.drain(..)); list.len().saturating_add(extra) <= most } #[cfg(test)] thread_local! { /// Areas [`fit`] looked at on this thread to remove repeats, which a test reads. pub(crate) static AREAS_SIFTED: std::cell::Cell = const { std::cell::Cell::new(0) }; } /// The first `clean` areas of a list being collected, which hold no repeats, and the set of them: /// [`fit`] removes repeats from the areas after them only. `spans` are the spans of sheets (first /// sheet, last sheet, range) whose areas are all among those, and `spans_added` those added since /// the last removal; a span of `spans` mentioned again only counts its areas in `repeats`, the /// repeats the list would hold had they been added, which every count includes and the next /// removal clears. The spans kept are at most those written in the definition. `deferred` are the /// names a range operand's list holds as their boxes, in the order they joined it, all after /// `clean`, and `hidden` the areas they would add beyond their boxes, which every count includes /// until [`Distinct::expand`] puts their areas back. #[derive(Default)] struct Distinct { seen: HashSet>, clean: usize, repeats: usize, spans: HashSet<(usize, usize, RangeRef), std::hash::BuildHasherDefault>, spans_added: Vec<(usize, usize, RangeRef)>, deferred: Vec, hidden: usize, } /// A name in a range operand's list as its boxes: the `boxes` areas from `at` stand for `areas`. struct Deferred { at: usize, boxes: usize, areas: Rc<[Area]>, } impl Distinct { /// Puts the areas of the names `list` holds as their boxes back in place of the boxes: the list /// is then what it would be had the names added their areas. fn expand(&mut self, list: &mut Vec) { let Some(first) = self.deferred.first() else { return }; let mut at = first.at.min(list.len()); let mut tail = list.split_off(at).into_iter(); for d in self.deferred.drain(..) { list.extend(tail.by_ref().take(d.at.saturating_sub(at))); let _boxes = tail.by_ref().take(d.boxes).count(); list.extend_from_slice(&d.areas); at = d.at.saturating_add(d.boxes); } list.extend(tail); self.hidden = 0; } } /// What a list being collected already holds (see `Walk::taken`). #[derive(Default)] struct Taken { /// The names whose areas it holds: a name mentioned again adds nothing. names: HashSet, /// Its areas without repeats, as far as [`fit`] has removed them. areas: Distinct, } /// Most areas a list being collected may hold after a span of sheets, or the boxes of a range /// operand, are added to it (see `fit`): in a name's definition (`depth` > 0) [`MAX_NAME_AREAS`], /// past which the name is dynamic anyway; a formula's own references don't count. fn most_areas(depth: usize) -> usize { if depth > 0 { MAX_NAME_AREAS } else { usize::MAX } } /// What a function call reads beyond its arguments' own references: SUMIF and AVERAGEIF the /// cells of the sum range they really read (see `resized_sum_range`), dynamic when the criteria /// range's size isn't known statically; GETPIVOTDATA the report its reference points into; /// INDIRECT, OFFSET and the volatile functions, read at evaluation (dynamic). `in_definition`: the /// call sits in a name's definition, not in the formula itself. // The list's repeats (`distinct`) travel beside the list itself, which makes one argument more. #[allow(clippy::too_many_arguments)] fn call_reads( wb: &Workbook, sheet: usize, n: &str, args: &[Expr], in_definition: bool, out: &mut Vec, distinct: Option<&mut Distinct>, dynamic: &mut bool, ) { // GETPIVOTDATA reads the report cells, so it depends on the whole report its reference points // into (pivot commands recalculate everything). Any other reference is dynamic, and so is a // call in a name's definition: the report would be looked up on the sheet that resolved the // name, and a name's summary doesn't depend on the use that resolved it. if n == "GETPIVOTDATA" { let report = match args.get(1) { Some(Expr::Ref(r)) if !in_definition => { let si = match &r.sheet { SheetSel::Current => Some(sheet), SheetSel::Named(name) => wb.sheet_index(name), SheetSel::Span(..) => None, }; si.and_then(|i| wb.sheet(i)) .and_then(|sh| sh.pivots.iter().find_map(|p| p.last_range.filter(|lr| lr.intersects(&r.range())))) .map(|lr| (r, lr)) } _ => None, }; match report { Some((r, lr)) => *dynamic |= !push_area(wb, sheet, out, None, r, lr, usize::MAX), None => *dynamic = true, } } if resizes_sum_range(n, args.len()) { match (args.first(), args.get(2)) { (Some(Expr::Ref(c)), Some(Expr::Ref(s))) => { let (crit, sum) = (c.range(), s.range()); let most = if in_definition { MAX_NAME_AREAS } else { usize::MAX }; *dynamic |= !push_area(wb, sheet, out, distinct, s, resized_sum_range(sum, crit.height(), crit.width()), most); } (_, Some(Expr::Number(_) | Expr::Text(_) | Expr::Bool(_) | Expr::Error(_) | Expr::Array(_) | Expr::Missing)) => {} _ => *dynamic = true, } } if matches!(n, "INDIRECT" | "OFFSET" | "NOW" | "TODAY" | "RAND" | "RANDBETWEEN" | "RANDARRAY" | "CELL" | "INFO") { *dynamic = true; } } #[cfg(test)] thread_local! { /// Looks [`bounding_boxes`] took on this thread to place the areas it was given, which a test /// reads: one per box compared while the boxes are scanned, one per probe of the index after. pub(crate) static BOXES_LOOKED_AT: std::cell::Cell = const { std::cell::Cell::new(0) }; } /// Counts one look of [`bounding_boxes`] (see [`BOXES_LOOKED_AT`]). fn looked() { #[cfg(test)] BOXES_LOOKED_AT.with(|n| n.set(n.get().saturating_add(1))); } /// One box per sheet around `areas`, in the order the sheets first appear: what a range with a /// computed end covers. Past a few boxes, each area finds its sheet's box through an index: a span /// of sheets in an operand (`(First:Last!A1):A2`) brings one area per sheet, and a scan of the /// boxes made so far would cost the square of the number of sheets. Fewer than /// [`SCANNED_UP_TO`] boxes are scanned, which costs less than building the index. fn bounding_boxes(areas: &[Area]) -> Vec { let mut boxes: Vec = Vec::new(); // Holds every box once there are `SCANNED_UP_TO` of them. let mut by_sheet: HashMap> = HashMap::default(); for &area in areas { let at = if boxes.len() < SCANNED_UP_TO { boxes.iter().position(|b| { looked(); b.sheet == area.sheet }) } else { looked(); by_sheet.get(&area.sheet).copied() }; match at.and_then(|i| boxes.get_mut(i)) { Some(x) => x.range = x.range.union(&area.range), None => { boxes.push(area); if boxes.len() == SCANNED_UP_TO { by_sheet.extend(boxes.iter().enumerate().map(|(i, b)| (b.sheet, i))); } else if boxes.len() > SCANNED_UP_TO { by_sheet.insert(area.sheet, boxes.len().saturating_sub(1)); } } } } boxes } /// The precedent walk over one formula and the definitions of the names it resolves. Two rules /// hold throughout: /// /// 1. Anything the walk can't resolve, or meets past one of its bounds, makes the formula dynamic. /// That is always a correct answer, only a slower one: the formula recalculates every time. /// 2. A name's [`Summary`] doesn't depend on the use that resolved it: the caller's bound names /// and whether the use sits in a range's operand are applied at each use, from the summary. /// Where the order of resolution matters (a chain cut at [`NAME_DEPTH`], a cycle), the summary /// errs towards dynamic, by rule 1. struct Walk<'w, 'n> { wb: &'w Workbook, names: &'n mut NameCache, /// Nodes visited so far, counted against [`MAX_PRECEDENT_NODES`]. nodes: usize, /// Areas the formula has taken from the names it mentions itself, counted against /// [`MAX_NAME_AREAS`]. from_names: usize, /// Whether the name being resolved went past [`MAX_NAME_AREAS`]: it then stores none. overflowed: bool, /// What each list being collected already holds (the formula's, a definition's, a computed /// range's; innermost last): the names whose areas it holds, and its areas without repeats. taken: Vec, /// Whether the walk met a database function, whose computed criteria it can't follow: the /// formula is then dynamic (see [`precedents_with`]). database: bool, /// The definitions being resolved, innermost last. frames: Vec, /// Whether the definition being resolved (or the formula) met a spill reference so far, those /// of the names it uses included: a name holding one, met in a range's operand, is dynamic. spill: bool, /// Whether the walk met a name: a defined name, a LET variable or LAMBDA parameter (bound or /// used), or a call to a function not built in. names_met: bool, /// Whether the formula calls SUBTOTAL or AGGREGATE, itself or in a definition it reads (the /// summaries hand it on), and for a definition being resolved, whether it does. budgeted: bool, } /// A definition being resolved: what it leaves to its callers so far. #[derive(Default)] struct Frame { /// The names the definition leaves free, those of the names it uses included (folded), as the /// numbers of their spellings, hashed by the cheap hasher the graph uses for cell keys: copying /// them is most of a build's work on names that share many free names. free: HashSet>, /// The names bound where the definition calls itself, each once, as the numbers of their /// spellings: a definition can call itself a thousand times under two thousand parameters. bound_at_self_calls: HashSet>, /// The [`Bound::generation`] of the definition's bound names at its last self-call, whose /// names `bound_at_self_calls` holds already. self_call_generation: Option, /// Whether `free` would already take the build past [`MAX_BUILD_FREE_NAMES`] were it kept: the /// definition will keep none, unless it is dynamic for another reason (then it keeps none /// either), so no more are copied into it. past_free_budget: bool, } #[cfg(test)] thread_local! { /// Free names copied into the definitions being resolved on this thread, which a test reads. pub(crate) static FREE_NAMES_COPIED: std::cell::Cell = const { std::cell::Cell::new(0) }; } #[cfg(test)] thread_local! { /// Bound names compared on this thread with a name looked up or with a name's free names, which /// a test reads: one per hash lookup or per name taken from the smaller side. pub(crate) static BOUND_NAMES_COMPARED: std::cell::Cell = const { std::cell::Cell::new(0) }; } /// Counts `n` bound names compared (see [`BOUND_NAMES_COMPARED`]). fn compared(n: usize) { #[cfg(test)] BOUND_NAMES_COMPARED.with(|c| c.set(c.get().saturating_add(n))); #[cfg(not(test))] let _ = n; } /// The LAMBDA parameters and LET variables in scope, as the numbers of their spellings /// ([`NameCache`]'s `spellings`): a stack of them, innermost last, which the scopes push and pop, /// and how often each spelling stands on it, so that a name bound in two nested scopes stays bound /// when the inner one ends. Whether a name is bound costs one hash, not one comparison per bound /// name: a LAMBDA can have over two hundred parameters and a body mentioning a name hundreds of /// times. #[derive(Default)] struct Bound { stack: Vec, counts: HashMap>, /// Moves on at every name bound or unbound: while it stays the same, so do the names bound. generation: u64, } impl Bound { fn push(&mut self, spelling: usize) { self.stack.push(spelling); let count = self.counts.entry(spelling).or_insert(0); *count = count.saturating_add(1); self.generation = self.generation.wrapping_add(1); } /// Ends the scope of the last `count` names bound. fn pop(&mut self, count: usize) { for _ in 0..count { let Some(spelling) = self.stack.pop() else { return }; self.generation = self.generation.wrapping_add(1); if let Some(left) = self.counts.get_mut(&spelling) { *left = left.saturating_sub(1); if *left == 0 { self.counts.remove(&spelling); } } } } fn contains(&self, spelling: usize) -> bool { compared(1); self.counts.contains_key(&spelling) } /// The spellings bound, each once. fn spellings(&self) -> impl Iterator + '_ { self.counts.keys().copied() } /// How many spellings are bound, each counted once. fn distinct(&self) -> usize { self.counts.len() } } /// Where a name is used: `depth` counts the defined names entered on the way there (bounded by /// [`NAME_DEPTH`]). `in_range` says the use sits inside an operand of a range operator, whose box /// would have to cover what a LET variable or LAMBDA parameter there reads: the formula is dynamic /// instead. #[derive(Clone, Copy)] struct Site { depth: usize, in_range: bool, } /// A LET/LAMBDA parameter, case-folded as the evaluator compares names (`same_name`, in any /// script). (An optional parameter written `[x]` parses as a structured reference, not a name, so /// it never reaches the walk as one.) fn bound_name(n: &str) -> String { gridcraft_formula::fold_name(n) } impl Walk<'_, '_> { /// Adds the precedents a defined name contributes when used from `sheet` to `out`, resolving it /// through `names` the first time and looking it up after that. The evaluator reads a definition /// with the caller's LET variables and LAMBDA parameters (`bound`) in scope, so a name the /// definition leaves free is the caller's variable where the caller binds one so named: the /// formula is then dynamic. The engine's `name_readers` must match every name this resolves. fn name(&mut self, sheet: usize, name: &str, bound: &Bound, out: &mut Vec, dynamic: &mut bool, site: Site) { let wb = self.wb; // Split as the evaluator splits it: the parser stores the sheet unquoted, so it is used // as is and split at the last `!`. let (scope_sheet, bare) = match name.rsplit_once('!') { Some((sheet_name, bare)) => match wb.sheet_index(sheet_name) { Some(i) => (i, bare), None => { *dynamic = true; return; } }, None => (sheet, name), }; let Some(definition) = self.names.lookup.find(wb, bare, scope_sheet).and_then(|i| wb.names.get(i)) else { // Not a defined name: a table name (data body known only at evaluation) or a typo // (#NAME?). Either way, evaluate every time. *dynamic = true; return; }; // A sheet-scoped name used from another sheet (`Sheet1!F`): a LAMBDA it yields runs its body // against the calling cell's sheet, not the scope sheet its references are resolved against // here, so the cells it reads aren't known statically. if definition.scope.is_some_and(|s| s != sheet) { *dynamic = true; return; } let name_sheet = definition.scope.unwrap_or(sheet); let key = (definition.name.to_ascii_lowercase(), definition.scope, name_sheet); // Looked up before the depth bound: a hit doesn't recurse. match self.names.entries.get(&key) { // A direct self-call (a recursive LAMBDA): it reads what the body being collected reads, // nothing more. In a range's operand, its result's cells are not known: dynamic. The // names bound here are checked against the definition's free names once they are all // known. A self-call under the same bound names as the last one adds none: the // definition's self-calls all sit in its own walk, under one `Bound`. Some(NameEntry::Resolving { depth }) if depth.saturating_add(1) == site.depth => { *dynamic |= site.in_range; if let Some(frame) = self.frames.last_mut() && frame.self_call_generation != Some(bound.generation) { compared(bound.distinct()); frame.bound_at_self_calls.extend(bound.spellings()); frame.self_call_generation = Some(bound.generation); } return; } Some(NameEntry::Resolving { .. }) => { // A longer cycle (A→B→A): B's entry lacks A's areas, so the names on it are dynamic. *dynamic = true; return; } Some(NameEntry::Resolved(_)) => return self.apply(&key, bound, out, dynamic, site), None => {} } let parsed = self.names.parsed.saturating_add(definition.formula.len()); if site.depth >= NAME_DEPTH || parsed > MAX_BUILD_NAME_TEXT || self.names.cached >= MAX_BUILD_NAME_AREAS { *dynamic = true; return; } self.names.parsed = parsed; let summary = self.resolve(&key, &definition.formula, name_sheet, site.depth); self.names.entries.insert(key.clone(), NameEntry::Resolved(summary)); self.apply(&key, bound, out, dynamic, site); } /// Resolves the definition `formula` of the name `key`, entered at `depth`, against /// `name_sheet`, within the build's budgets. fn resolve(&mut self, key: &NameKey, formula: &str, name_sheet: usize, depth: usize) -> Summary { let mut summary = Summary { areas: Rc::default(), boxes: None, dynamic: true, free: Vec::new(), spill: false, budgeted: false }; let mut areas = Vec::new(); let mut past_free_budget = false; let outer_spill = std::mem::replace(&mut self.spill, false); let outer_budgeted = std::mem::replace(&mut self.budgeted, false); match gridcraft_formula::parse_name(formula) { Ok(expr) if !gridcraft_formula::adjust::has_relative_refs(&expr) => { self.names.entries.insert(key.clone(), NameEntry::Resolving { depth }); let outer_overflowed = std::mem::replace(&mut self.overflowed, false); self.taken.push(Taken::default()); self.frames.push(Frame::default()); (areas, summary.dynamic) = self.collect(name_sheet, &expr, depth + 1); self.taken.pop(); let frame = self.frames.pop().unwrap_or_default(); // Where it calls itself with one of its free names bound, the call reads that. summary.dynamic |= frame.bound_at_self_calls.iter().any(|n| frame.free.contains(n)); // Counted before they are collected and sorted: past the budget they are dropped. past_free_budget = !summary.dynamic && (frame.past_free_budget || self.names.free_kept.saturating_add(frame.free.len()) > MAX_BUILD_FREE_NAMES); if !summary.dynamic && !past_free_budget { summary.free = frame.free.into_iter().collect(); summary.free.sort_unstable(); } if std::mem::replace(&mut self.overflowed, outer_overflowed) { areas.clear(); } // Stored once each: a definition mentioning a range k times contributes it once. let mut distinct = HashSet::new(); areas.retain(|a| distinct.insert(*a)); } _ => {} } if areas.len() > MAX_NAME_AREAS { areas = Vec::new(); summary.free = Vec::new(); summary.dynamic = true; } let cached = self.names.cached.saturating_add(areas.len()); let free_kept = self.names.free_kept.saturating_add(summary.free.len()); if cached > MAX_BUILD_NAME_AREAS || free_kept > MAX_BUILD_FREE_NAMES || past_free_budget { areas = Vec::new(); summary.free = Vec::new(); summary.dynamic = true; } else { self.names.cached = cached; self.names.free_kept = free_kept; } summary.areas = areas.into(); summary.spill = std::mem::replace(&mut self.spill, outer_spill); summary.budgeted = std::mem::replace(&mut self.budgeted, outer_budgeted); summary } /// Applies the summary of the resolved name `key` at one use: the use is dynamic where the name /// is, where the caller binds a name the definition leaves free, or where a name holding a spill /// reference sits in a range's operand; the definition being resolved around the use (if any) /// takes on the name's free names and spill reference; and the name's areas join `out` (in a /// range's operand, its boxes standing for them), within the budgets of [`Walk::may_add`], unless /// `out` holds them already. fn apply(&mut self, key: &NameKey, bound: &Bound, out: &mut Vec, dynamic: &mut bool, site: Site) { let Some(NameEntry::Resolved(summary)) = self.names.entries.get(key) else { return; }; // A name leaving nothing free (a plain range) can't be shadowed. Otherwise the smaller side // is looked up in the other, at every use, before a repeated use returns below: a LET can // bind over a hundred names around hundreds of uses of a name leaving one free. let shadowed = !summary.free.is_empty() && bound.distinct() > 0 && if bound.distinct() <= summary.free.len() { compared(bound.distinct()); bound.spellings().any(|n| summary.free.binary_search(&n).is_ok()) } else { summary.free.iter().any(|&n| bound.contains(n)) }; *dynamic |= summary.dynamic || shadowed || (summary.spill && site.in_range); self.spill |= summary.spill; self.budgeted |= summary.budgeted; let count = summary.areas.len(); // Mentioned again where its areas were already added: they would only be removed again as // repeats, so nothing is added or counted. Nor are its free names passed on again: at that // first use, in the same definition, they were passed on, or the definition was dynamic // already (or became so past the copy budget) and keeps none. if self.taken.last().is_some_and(|t| t.names.contains(key)) { return; } // A definition already dynamic keeps no free names (see [`Summary`]), so none are copied // into it; the copy is charged before it is made. Nor are any copied into a definition whose // free names would already take the build past what it keeps (it ends with at least as many // as either side holds now, and the build keeps no fewer later): those copies are charged // as if made, so the copy budget runs out where it would have. if !*dynamic && let Some(frame) = self.frames.last_mut() { let folded = self.names.folded.saturating_add(summary.free.len()); if folded > fold_budget() { *dynamic = true; } else { self.names.folded = folded; let least = frame.free.len().max(summary.free.len()); frame.past_free_budget |= self.names.free_kept.saturating_add(least) > MAX_BUILD_FREE_NAMES; if !frame.past_free_budget { #[cfg(test)] FREE_NAMES_COPIED.with(|n| n.set(n.get().saturating_add(summary.free.len()))); frame.free.extend(summary.free.iter().copied()); } } } // The repeats a span left uncounted in `out`, and the areas of the names it holds as their // boxes (see `Distinct`), count as held. let held = out.len().saturating_add(self.taken.last().map_or(0, |t| t.areas.repeats.saturating_add(t.areas.hidden))); if !self.may_add(held, count, site) { *dynamic = true; return; } if let Some(NameEntry::Resolved(summary)) = self.names.entries.get_mut(key) { let Summary { areas, boxes, .. } = summary; // In a range's operand (`out` is the operand's own list, which closes into one box per // sheet) the name's boxes stand for its areas, which give the same boxes: a name used in // many range operands is not copied, nor passed over, at each. Its areas are counted as // held all the same, and put back where a count would fail (`fit`). let boxes = if site.in_range { Some(&*boxes.get_or_insert_with(|| bounding_boxes(areas))) } else { None }; match (boxes, self.taken.last_mut()) { (Some(boxes), Some(t)) if boxes.len() < areas.len() => { t.areas.deferred.push(Deferred { at: out.len(), boxes: boxes.len(), areas: Rc::clone(areas) }); t.areas.hidden = t.areas.hidden.saturating_add(areas.len().saturating_sub(boxes.len())); out.extend_from_slice(boxes); } _ => out.extend_from_slice(areas), } } if let Some(t) = self.taken.last_mut() { t.names.insert(key.clone()); } } /// Whether `n` more areas from a name may join the `held` areas collected so far: inside another /// name's definition, while that name stays within [`MAX_NAME_AREAS`] (past it, it is dynamic /// anyway, so collecting stops there rather than after the definition), and for a name the /// formula mentions itself, as [`Walk::may_take`] counts them. fn may_add(&mut self, held: usize, n: usize, site: Site) -> bool { if site.depth > 0 { let fits = held.saturating_add(n) <= MAX_NAME_AREAS; self.overflowed |= !fits; fits } else { self.may_take(n) } } /// Whether the formula may take `n` more areas from a name it mentions itself, counting them /// when it may: at most [`MAX_NAME_AREAS`] for the formula, and [`MAX_BUILD_NAME_AREAS`] for all /// the formulas of the graph build, since a name's areas are stored again for every reader. fn may_take(&mut self, n: usize) -> bool { self.from_names = self.from_names.saturating_add(n); let stored = self.names.stored.saturating_add(n); if self.from_names > MAX_NAME_AREAS || stored > MAX_BUILD_NAME_AREAS { return false; } self.names.stored = stored; true } /// Walks `root`, a formula or (`depth` > 0) the definition of the name entered last, and returns /// its static references and whether it is dynamic: whether anything in it can't be resolved /// now. The walk keeps its own stack of [`Step`]s, so its native stack use doesn't grow with /// the expression's nesting; it recurses only into a name's definition, through /// [`Walk::name`], which [`NAME_DEPTH`] bounds. fn collect<'e>(&mut self, sheet: usize, root: &'e Expr, depth: usize) -> (Vec, bool) { let wb = self.wb; // The areas of `root`, and one list for each range operator whose operands are being // visited (innermost last), which closes into the enclosing list as bounding boxes. let mut out = Vec::new(); let mut ranges: Vec> = Vec::new(); let mut state = Collecting { pending: vec![Step::Visit { expr: root, in_range: false, link: false }], bound: Bound::default(), dynamic: false }; while let Some(step) = state.pending.pop() { let (e, in_range, link) = match step { Step::Visit { expr, in_range, link } => (expr, in_range, link), Step::Close => { self.taken.pop(); if let Some(inner) = ranges.pop() { // The boxes count against the list they join as a span of sheets does // (`push_area`): the operand's list counted its own spans only, so a range // operand repeated in a definition would otherwise collect without bound // before repeats are removed. let boxes = bounding_boxes(&inner); let list = ranges.last_mut().unwrap_or(&mut out); if self.overflowed || !fit(list, self.taken.last_mut().map(|t| &mut t.areas), boxes.len(), most_areas(depth)) { state.dynamic = true; self.overflowed = true; } else { list.extend(boxes); } } continue; } Step::Bind(variable) => { self.names_met = true; state.bound.push(self.names.spelling(bound_name(variable))); continue; } Step::Unbind(count) => { state.bound.pop(count); continue; } Step::Lookup { name, in_range } => { self.names_met = true; // Folded once, for the bound names and the definition's free names. Every bound // name has a number, so a spelling without one isn't bound; with nothing bound, // none is looked up. let folded = (state.bound.distinct() > 0 || !self.frames.is_empty()).then(|| bound_name(name)); let spelling = folded.as_ref().filter(|_| state.bound.distinct() > 0).and_then(|f| self.names.spellings.get(f).copied()); if !spelling.is_some_and(|n| state.bound.contains(n)) { // In a definition, a name it doesn't bind is left free to its callers. if let Some(folded) = folded && !self.frames.is_empty() { let spelling = spelling.unwrap_or_else(|| self.names.spelling(folded)); if let Some(frame) = self.frames.last_mut() { frame.free.insert(spelling); } } let list = ranges.last_mut().unwrap_or(&mut out); self.name(sheet, name, &state.bound, list, &mut state.dynamic, Site { depth, in_range }); } else { state.dynamic |= in_range; } continue; } }; // Past the node bound the answer is conservative: the formula recalculates every time. if !link { self.nodes = self.nodes.saturating_add(1); if self.nodes > MAX_PRECEDENT_NODES { state.dynamic = true; continue; } } let visit = |expr: &'e Expr, link: bool| Step::Visit { expr, in_range, link }; match e { // Past `overflowed` the name stores no areas (and is dynamic already), so none is // added: a span failing to `fit` again would remove repeats again. Expr::Ref(_) if self.overflowed => {} Expr::Ref(r) => { let distinct = self.taken.last_mut().map(|t| &mut t.areas); if !push_area(wb, sheet, ranges.last_mut().unwrap_or(&mut out), distinct, r, r.range(), most_areas(depth)) { state.dynamic = true; self.overflowed = true; } } // Looked up next, before any other step. Expr::Name(n) => state.pending.push(Step::Lookup { name: n, in_range }), Expr::Struct(_) => state.dynamic = true, Expr::Array(rows) => state.pending.extend(rows.iter().flatten().rev().map(|x| visit(x, false))), Expr::Unary(UnOp::Percent, a) => state.pending.push(visit(a, matches!(**a, Expr::Unary(UnOp::Percent, _)))), // The spill operator (`A1#`): in a range's operand the spill's extent, not the anchor // cell, sets the box, so the formula is dynamic. Expr::Unary(UnOp::Spill, a) => { self.spill = true; state.dynamic |= in_range; state.pending.push(visit(a, false)); } Expr::Paren(a) => state.pending.push(visit(a, matches!(**a, Expr::Paren(_)))), Expr::Unary(_, a) => state.pending.push(visit(a, false)), // A range ending in a function's result (`A1:INDEX(B1:B9,n)`), or a chain of plain // references the parser can't fold into one (`A1:B2:C3`), covers the cells between the // references inside it, not only those references. A range whose left operand is a // range (`X:(B1):(C1)`) is one list: its operands, the left one's included, fill it, and // it closes once. A trim reference (`A1:.B9`) is the range operator with a modifier. Expr::Binary(BinOp::Range, a, b) => { if !link { // The range's own list: a name already added to the enclosing list still counts // towards its box. ranges.push(Vec::new()); self.taken.push(Taken::default()); state.pending.push(Step::Close); } state.pending.push(Step::Visit { expr: b, in_range: true, link: false }); state.pending.push(Step::Visit { expr: a, in_range: true, link: matches!(**a, Expr::Binary(BinOp::Range, ..)) }); } Expr::Binary(_, a, b) => { state.pending.push(visit(b, false)); state.pending.push(visit(a, matches!(&**a, Expr::Binary(op, ..) if *op != BinOp::Range))); } Expr::Invoke(callee, args) => { state.pending.extend(args.iter().rev().map(|x| visit(x, false))); state.pending.push(visit(callee, matches!(**callee, Expr::Invoke(..)))); } Expr::Call(n, args) => self.visit_call(sheet, Site { depth, in_range }, n, args, ranges.last_mut().unwrap_or(&mut out), &mut state), Expr::Number(_) | Expr::Text(_) | Expr::Bool(_) | Expr::Error(_) | Expr::Missing => {} } } (out, state.dynamic) } /// Queues a call's steps: a LAMBDA body, its parameters bound until an `Unbind`; LET values, /// each then a `Bind`, the result and an `Unbind`; else the arguments and, last, a `Lookup` of a /// callee not built in, so its areas count against [`MAX_NAME_AREAS`] after theirs. fn visit_call<'e>(&mut self, sheet: usize, site: Site, n: &'e str, args: &'e [Expr], list: &mut Vec, state: &mut Collecting<'e>) { let visit = |expr: &'e Expr, link: bool| Step::Visit { expr, in_range: site.in_range, link }; call_reads(self.wb, sheet, n, args, site.depth > 0, list, self.taken.last_mut().map(|t| &mut t.areas), &mut state.dynamic); // A database function makes the formula dynamic (see `precedents_with`), and inside a // name's definition the name too, for every formula reading it. Their names all start // with D (the parser upper-cases calls), so other calls aren't looked up. if n.starts_with('D') && gridcraft_functions::lookup(n).is_some_and(|f| f.category == gridcraft_functions::Category::Database) { self.database = true; state.dynamic |= site.depth > 0; } // Their budget on cut sizes (see `precedents_with`); the parser upper-cases calls, as the // evaluator's dispatch reads them. self.budgeted |= matches!(n, "SUBTOTAL" | "AGGREGATE"); match (n, args.split_last()) { // Parameters are bound inside the body only; the body is the last argument. ("LAMBDA", Some((body, parameters))) => { let mut added = 0; for p in parameters { if let Expr::Name(pn) = p { state.bound.push(self.names.spelling(bound_name(pn))); added += 1; } } self.names_met |= added > 0; state.pending.push(Step::Unbind(added)); state.pending.push(visit(body, false)); } // Each LET variable is bound for the values after it and for the result. ("LET", Some((result, pairs))) if args.len() >= 3 => { let added = pairs.chunks(2).filter(|pair| matches!(pair, [Expr::Name(_), _])).count(); state.pending.push(Step::Unbind(added)); state.pending.push(visit(result, false)); for pair in pairs.chunks(2).rev() { match pair { [Expr::Name(variable), value] => { state.pending.push(Step::Bind(variable)); state.pending.push(visit(value, false)); } [other] => state.pending.push(visit(other, false)), _ => {} } } } _ => { // Not a built-in: a defined name holding a LAMBDA (its body's references are // this cell's precedents too), or unknown (#NAME?, evaluated every time), // looked up after the arguments. if gridcraft_functions::lookup(n).is_none() && !is_special(n) { state.pending.push(Step::Lookup { name: n, in_range: site.in_range }); } state.pending.extend(args.iter().rev().map(|x| visit(x, false))); } } } } /// The state of one [`Walk::collect`] loop, which a visited call also changes. struct Collecting<'e> { /// The steps still to run. pending: Vec>, /// The LAMBDA parameters and LET variables in scope, which are not name lookups. bound: Bound, /// Whether anything met so far can't be resolved now. dynamic: bool, } /// One entry of [`Walk::collect`]'s explicit stack. Steps run last in, first out: a node queues its /// children in reverse, so they run left to right, and a step queued before them runs after all of /// them. enum Step<'e> { /// Visit an expression and queue what it holds. Visit { expr: &'e Expr, /// Inside an operand of a range operator (see [`Site`]). in_range: bool, /// An inner link of a chain of one shape. It means two things: the node is not counted /// against [`MAX_PRECEDENT_NODES`] (it counts with the chain's outermost node), and, for a /// range that is the left operand of a range, no list of its own is opened and closed: its /// operands fill the parent range's list. link: bool, }, /// The operands of a range operator have been visited: the list they filled closes into the /// enclosing one, one box per sheet. Close, /// A LET variable's value has been visited: the variable is bound for what comes after it. Bind(&'e str), /// The scope of the last `count` LET variables or LAMBDA parameters ends. Unbind(usize), /// Look up a name met in the expression, or the callee of a call to a function that isn't built /// in once its arguments have been visited: a LET variable or LAMBDA parameter in scope, or a /// defined name ([`Walk::name`]). Lookup { name: &'e str, in_range: bool }, } fn is_special(n: &str) -> bool { matches!( n, "IF" | "IFS" | "IFERROR" | "IFNA" | "CHOOSE" | "SWITCH" | "ROW" | "COLUMN" | "ROWS" | "COLUMNS" | "AREAS" | "ISREF" | "ISFORMULA" | "FORMULATEXT" | "SHEET" | "SHEETS" | "OFFSET" | "INDIRECT" | "INDEX" | "CELL" | "TRIMRANGE" | "GETPIVOTDATA" | "SUBTOTAL" | "AGGREGATE" | "TEXT" | "LET" | "LAMBDA" | "ISOMITTED" | "MAP" | "REDUCE" | "SCAN" | "BYROW" | "BYCOL" | "MAKEARRAY" ) } /// Names of functions the evaluator implements itself (merged into the function list for UI). pub const SPECIAL_FUNCTIONS: &[&str] = &[ "IF", "IFS", "IFERROR", "IFNA", "CHOOSE", "SWITCH", "ROW", "COLUMN", "ROWS", "COLUMNS", "AREAS", "ISREF", "ISFORMULA", "FORMULATEXT", "SHEET", "SHEETS", "OFFSET", "INDIRECT", "INDEX", "CELL", "TRIMRANGE", "GETPIVOTDATA", "SUBTOTAL", "AGGREGATE", "TEXT", "LET", "LAMBDA", "ISOMITTED", "MAP", "REDUCE", "SCAN", "BYROW", "BYCOL", "MAKEARRAY", ]; pub fn is_known_function(n: &str) -> bool { is_special(&n.to_ascii_uppercase()) || gridcraft_functions::lookup(n).is_some() }