use crate::coordinate::{CellRef, Col, Range, Row};
use crate::error::CellError;
use crate::formula::custom::CustomFunctions;
use crate::formula::functions;
use crate::formula::parser::{BinaryOp, Expr, Structured, TablePart, UnaryOp, parse};
use crate::formula::value::{Value, compare};
use crate::model::{CellValue, Spreadsheet};
use crate::progress::{Options, Stage};
use std::collections::{HashMap, HashSet};
use std::sync::Arc;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Origin {
pub sheet: usize,
pub at: CellRef,
}
impl Origin {
#[must_use]
pub const fn new(sheet: usize, at: CellRef) -> Self {
Self { sheet, at }
}
}
pub(crate) const MAX_RANGE_CELLS: usize = 4_000_000;
const MAX_CHAIN_DEPTH: usize = 100;
pub struct Engine<'a> {
book: &'a Spreadsheet,
cache: HashMap<(usize, CellRef), Value>,
running: HashSet<(usize, CellRef)>,
resolving: HashSet<String>,
custom: Option<&'a CustomFunctions>,
scope: Vec<(String, Value)>,
dims: Vec<Option<Range>>,
ranges: HashMap<(usize, Range), Value>,
cycle_hits: u64,
deferred: Option<(usize, CellRef)>,
waiting: HashSet<(usize, CellRef)>,
name_index: Option<HashMap<String, Vec<usize>>>,
parsed: HashMap<String, Option<Arc<Expr>>>,
implicit: bool,
array_starts: Option<HashSet<(usize, CellRef)>>,
shared: Option<&'a Shared>,
stale: Option<&'a HashSet<(usize, CellRef)>>,
}
pub(crate) struct Shared {
slots: HashMap<(usize, CellRef), usize>,
values: Vec<std::sync::OnceLock<Value>>,
claimed: Vec<std::sync::atomic::AtomicBool>,
ranges: std::sync::RwLock<HashMap<(usize, Range), Value>>,
}
impl Shared {
fn slot(&self, sheet: usize, at: CellRef) -> Option<usize> {
self.slots.get(&(sheet, at)).copied()
}
fn range(&self, sheet: usize, range: Range) -> Option<Value> {
self.ranges.read().ok()?.get(&(sheet, range)).cloned()
}
fn keep_range(&self, sheet: usize, range: Range, value: &Value) {
if let Ok(mut ranges) = self.ranges.write() {
ranges
.entry((sheet, range))
.or_insert_with(|| value.clone());
}
}
fn get(&self, sheet: usize, at: CellRef) -> Option<&Value> {
self.slots
.get(&(sheet, at))
.and_then(|&slot| self.values[slot].get())
}
fn claim(&self, slot: usize) -> Option<&Value> {
use std::sync::atomic::Ordering;
if !self.claimed[slot].swap(true, Ordering::AcqRel) {
return None;
}
for _ in 0..WAIT_SPINS {
if let Some(value) = self.values[slot].get() {
return Some(value);
}
std::thread::yield_now();
}
None
}
}
impl<'a> Engine<'a> {
#[must_use]
pub fn new(book: &'a Spreadsheet) -> Self {
Self {
book,
cache: HashMap::new(),
running: HashSet::new(),
resolving: HashSet::new(),
custom: None,
scope: Vec::new(),
dims: vec![None; book.sheets().len()],
ranges: HashMap::new(),
cycle_hits: 0,
deferred: None,
waiting: HashSet::new(),
name_index: None,
parsed: HashMap::new(),
implicit: false,
array_starts: None,
shared: None,
stale: None,
}
}
#[must_use]
pub fn with_functions(book: &'a Spreadsheet, custom: &'a CustomFunctions) -> Self {
Self {
custom: Some(custom),
..Self::new(book)
}
}
#[must_use]
pub const fn custom(&self) -> Option<&'a CustomFunctions> {
self.custom
}
#[must_use]
pub const fn book(&self) -> &'a Spreadsheet {
self.book
}
pub fn eval(&mut self, origin: Origin, formula: &str) -> Value {
match parse(formula) {
Ok(expr) => self.eval_tree(origin, &expr),
Err(_) => Value::Error(CellError::Name),
}
}
pub fn eval_tree(&mut self, origin: Origin, expr: &Expr) -> Value {
let single = self.holds_single_formula(origin);
let saved = std::mem::replace(&mut self.implicit, single);
let value = self.eval_value(origin, expr);
self.implicit = saved;
let value = match value {
Value::Array(rows) if rows.len() == 1 && rows[0].len() == 1 => {
rows.first().and_then(|r| r.first()).cloned()
}
other => Some(other),
};
match value {
Some(Value::Blank) | None => Value::Number(0.0),
Some(other) => other,
}
}
pub(crate) fn eval_value(&mut self, origin: Origin, expr: &Expr) -> Value {
match self.narrowed(origin, expr) {
Some(Ok(cell)) => self.eval_expr(origin, &cell),
Some(Err(e)) => Value::Error(e),
None => self.eval_expr(origin, expr),
}
}
pub(crate) fn narrowed(
&mut self,
origin: Origin,
expr: &Expr,
) -> Option<std::result::Result<Expr, CellError>> {
if !self.implicit {
return None;
}
let (sheet, area) = self.area_of(origin, expr, 0)?;
let at = origin.at;
let col = if area.width() == 1 {
area.start.col
} else if (area.start.col..=area.end.col).contains(&at.col) {
at.col
} else {
return Some(Err(CellError::Value));
};
let row = if area.height() == 1 {
area.start.row
} else if (area.start.row..=area.end.row).contains(&at.row) {
at.row
} else {
return Some(Err(CellError::Value));
};
let cell = CellRef::new(col, row);
Some(Ok(Expr::Range {
sheet,
range: Range {
start: cell,
end: cell,
},
anchors: crate::formula::parser::Anchors::default(),
}))
}
pub(crate) fn in_array<T>(&mut self, body: impl FnOnce(&mut Self) -> T) -> T {
let saved = std::mem::replace(&mut self.implicit, false);
let out = body(self);
self.implicit = saved;
out
}
fn holds_single_formula(&mut self, origin: Origin) -> bool {
let book = self.book;
let Some(sheet) = book.sheet(origin.sheet) else {
return false;
};
if !matches!(
sheet.get(origin.at).map(|c| &c.value),
Some(CellValue::Formula { .. })
) {
return false;
}
let starts = self.array_starts.get_or_insert_with(|| {
book.sheets()
.iter()
.enumerate()
.flat_map(|(i, ws)| ws.array_formulas.iter().map(move |r| (i, r.start)))
.collect()
});
!starts.contains(&(origin.sheet, origin.at))
}
fn area_of(
&mut self,
origin: Origin,
expr: &Expr,
depth: u8,
) -> Option<(Option<String>, Range)> {
let (sheet, area) = match expr {
Expr::Range { sheet, range, .. } if range.start != range.end => (sheet.clone(), *range),
Expr::Structured(reference) => {
let (sheet, range) = self.resolve_table(origin, reference).ok()?;
(Some(sheet), range)
}
Expr::Name(name)
if depth < 8 && !self.scope.iter().any(|(b, _)| b.eq_ignore_ascii_case(name)) =>
{
let (scope, bare) = self.name_scope(origin, name);
let found = self.defined_name(bare, scope)?;
let book = self.book;
let tree = self.parsed(book.defined_names[found].formula.as_str())?;
return self.area_of(origin, &tree, depth + 1);
}
Expr::Call { name, args } if name == "INDEX" => {
let (sheet, area) = self.area_of(origin, args.first()?, depth)?;
let (mut row, mut col) = (position(args.get(1))?, position(args.get(2))?);
if args.len() == 2 && area.height() == 1 {
(row, col) = (1, row);
}
let pick = |from: u32, len: u32, at: u32| match at {
0 => Some((from, from + len - 1)),
k if k <= len => Some((from + k - 1, from + k - 1)),
_ => None,
};
let (r1, r2) = pick(area.start.row.index(), area.height(), row)?;
let (c1, c2) = pick(area.start.col.index(), area.width(), col)?;
let area = Range {
start: CellRef::new(Col::new(c1)?, Row::new(r1)?),
end: CellRef::new(Col::new(c2)?, Row::new(r2)?),
};
(sheet, area)
}
_ => return None,
};
(area.start != area.end).then_some((sheet, area))
}
pub(crate) fn without_totals(&mut self, origin: Origin, expr: &Expr, value: Value) -> Value {
let found = match expr {
Expr::Range { sheet, range, .. } => Some((sheet.clone(), *range)),
_ => self.area_of(origin, expr, 0),
};
let Some((sheet, range)) = found else {
return value;
};
let book = self.book;
let Some(ws) = self
.sheet_index(origin, sheet.as_deref())
.and_then(|i| book.sheet(i))
else {
return value;
};
let mut is_total = |at: CellRef| match ws.get(at).map(|c| &c.value) {
Some(CellValue::Formula { formula, .. }) => {
self.parsed(formula).is_some_and(|e| calls_total(&e))
}
_ => false,
};
match value {
Value::Array(rows) => {
let (top, left) = (range.start.row.index(), range.start.col.index());
let rows = Arc::unwrap_or_clone(rows)
.into_iter()
.zip(top..)
.map(|(row, r)| {
row.into_iter()
.zip(left..)
.map(|(v, c)| match (Col::new(c), Row::new(r)) {
(Some(c), Some(r)) if is_total(CellRef::new(c, r)) => Value::Blank,
_ => v,
})
.collect()
})
.collect();
Value::array(rows)
}
_ if range.start == range.end && is_total(range.start) => Value::Blank,
other => other,
}
}
pub fn cell(&mut self, sheet: usize, at: CellRef) -> Value {
match self.spilled(sheet, at) {
Value::Array(rows) => rows
.first()
.and_then(|row| row.first())
.cloned()
.unwrap_or(Value::Blank),
other => other,
}
}
pub fn spilled(&mut self, sheet: usize, at: CellRef) -> Value {
if !self.running.is_empty() {
return self.spilled_once(sheet, at);
}
let mut pending = vec![(sheet, at)];
loop {
let Some(&(s, a)) = pending.last() else {
return Value::Blank;
};
let value = self.spilled_once(s, a);
if let Some(cell) = self.deferred.take() {
self.waiting.insert((s, a));
pending.push(cell);
continue;
}
pending.pop();
match pending.last() {
Some(below) => {
self.waiting.remove(below);
}
None => return value,
}
}
}
fn spilled_once(&mut self, sheet: usize, at: CellRef) -> Value {
let hits = self.cycle_hits;
if let Some(v) = self.cache.get(&(sheet, at)) {
return v.clone();
}
let Some(ws) = self.book.sheet(sheet) else {
return Value::Error(CellError::Ref);
};
let stored = ws.get(at).map(|c| c.value.clone());
let value = match stored {
None | Some(CellValue::Empty) => Value::Blank,
Some(CellValue::Number(n)) => Value::Number(n),
Some(CellValue::Text(t)) => Value::Text(t.to_string()),
Some(rich @ CellValue::RichText(_)) => {
Value::Text(rich.plain_text().unwrap_or_default())
}
Some(CellValue::Bool(b)) => Value::Bool(b),
Some(CellValue::Error(e)) => Value::Error(e),
Some(CellValue::Formula { .. })
if let Some(done) = self.shared.and_then(|sh| sh.get(sheet, at)) =>
{
done.clone()
}
Some(CellValue::Formula {
cached: Some(cached),
..
}) if self
.stale
.is_some_and(|stale| !stale.contains(&(sheet, at))) =>
{
stored_value(&cached)
}
Some(CellValue::Formula { .. })
if let Some(sh) = self.shared
&& let Some(slot) = sh.slot(sheet, at)
&& let Some(done) = sh.claim(slot) =>
{
done.clone()
}
Some(CellValue::Formula { formula, .. }) => {
if self.waiting.contains(&(sheet, at)) || !self.running.insert((sheet, at)) {
self.cycle_hits += 1;
return Value::Error(CellError::Ref);
}
if self.running.len() > MAX_CHAIN_DEPTH {
self.running.remove(&(sheet, at));
self.deferred.get_or_insert((sheet, at));
self.cycle_hits += 1;
return Value::Error(CellError::Value);
}
let value = self.eval(Origin::new(sheet, at), &formula);
self.running.remove(&(sheet, at));
value
}
};
if self.deferred.is_none() {
match self
.shared
.and_then(|sh| sh.slot(sheet, at).map(|slot| (sh, slot)))
{
Some((sh, slot)) if self.cycle_hits == hits => {
let _ = sh.values[slot].set(value.clone());
}
_ => {
self.cache.insert((sheet, at), value.clone());
}
}
}
value
}
pub(crate) fn remember(&mut self, sheet: usize, at: CellRef, value: &Value) {
if self.deferred.is_none() {
self.cache.insert((sheet, at), value.clone());
}
}
pub fn eval_expr(&mut self, origin: Origin, expr: &Expr) -> Value {
match expr {
Expr::Number(n) => Value::Number(*n),
Expr::Text(t) => Value::Text(t.clone()),
Expr::Bool(b) => Value::Bool(*b),
Expr::Error(e) => Value::Error(*e),
Expr::Missing => Value::Blank,
Expr::Range { sheet, range, .. } => self.range(origin, sheet.as_deref(), *range),
Expr::Structured(reference) => match self.resolve_table(origin, reference) {
Ok((sheet, range)) => self.range(origin, Some(&sheet), range),
Err(e) => Value::Error(e),
},
Expr::Name(name) => self.name(origin, name),
Expr::Unary(op, x) => {
let v = self.eval_value(origin, x);
unary(*op, &v)
}
Expr::Binary(op, a, b) => self.binary(origin, *op, a, b),
Expr::Call { name, args } => functions::call(self, origin, name, args),
Expr::Apply { callee, args } => self.apply_expr(origin, callee, args),
Expr::Array(rows) => Value::array(
rows.iter()
.map(|r| r.iter().map(|e| self.eval_expr(origin, e)).collect())
.collect(),
),
}
}
pub fn scoped<T>(
&mut self,
names: Vec<(String, Value)>,
body: impl FnOnce(&mut Self) -> T,
) -> T {
let depth = self.scope.len();
self.scope.extend(names);
let out = body(self);
self.scope.truncate(depth);
out
}
fn bound(&self, name: &str) -> Option<Value> {
self.scope
.iter()
.rev()
.find(|(bound, _)| bound.eq_ignore_ascii_case(name))
.map(|(_, value)| value.clone())
}
pub fn apply(&mut self, origin: Origin, callee: &Value, args: Vec<Value>) -> Value {
if let Some(e) = callee.error() {
return Value::Error(e);
}
let Value::Lambda(lambda) = callee.scalar() else {
return Value::Error(CellError::Calc);
};
if args.len() != lambda.params.len() {
return Value::Error(CellError::Value);
}
let lambda = std::sync::Arc::clone(lambda);
let mut bindings = lambda.captured.clone();
bindings.extend(lambda.params.iter().cloned().zip(args));
self.scoped(bindings, |engine| engine.eval_expr(origin, &lambda.body))
}
#[must_use]
pub fn captured(&self) -> Vec<(String, Value)> {
self.scope.clone()
}
fn apply_expr(&mut self, origin: Origin, callee: &Expr, args: &[Expr]) -> Value {
let callee = self.eval_expr(origin, callee);
let args: Vec<Value> = args.iter().map(|a| self.eval_expr(origin, a)).collect();
self.apply(origin, &callee, args)
}
fn name_scope<'n>(&self, origin: Origin, name: &'n str) -> (Option<usize>, &'n str) {
match name.rsplit_once('!') {
Some((sheet, bare)) => (self.sheet_index(origin, Some(sheet)), bare),
None => (Some(origin.sheet), name),
}
}
fn name(&mut self, origin: Origin, name: &str) -> Value {
if let Some(value) = self.bound(name) {
return value;
}
let (scope, bare) = self.name_scope(origin, name);
let Some(found) = self.defined_name(bare, scope) else {
return Value::Error(CellError::Name);
};
let key = bare.to_lowercase();
if !self.resolving.insert(key.clone()) {
return Value::Error(CellError::Ref);
}
let formula = self.book.defined_names[found].formula.as_str();
let value = match self.parsed(formula) {
Some(expr) => self.eval_expr(origin, &expr),
None => Value::Error(CellError::Name),
};
self.resolving.remove(&key);
value
}
pub(crate) fn defined_name(&mut self, name: &str, scope: Option<usize>) -> Option<usize> {
let book = self.book;
let index = self.name_index.get_or_insert_with(|| {
let mut index: HashMap<String, Vec<usize>> = HashMap::new();
for (i, defined) in book.defined_names.iter().enumerate() {
index
.entry(defined.name.to_lowercase())
.or_default()
.push(i);
}
index
});
let candidates = index.get(&name.to_lowercase())?;
let names = &book.defined_names;
candidates
.iter()
.copied()
.find(|&i| names[i].sheet.is_some() && names[i].sheet == scope)
.or_else(|| {
candidates
.iter()
.copied()
.find(|&i| names[i].sheet.is_none())
})
}
pub(crate) fn parsed(&mut self, text: &str) -> Option<Arc<Expr>> {
if let Some(expr) = self.parsed.get(text) {
return expr.clone();
}
let expr = parse(text).ok().map(Arc::new);
self.parsed.insert(text.to_owned(), expr.clone());
expr
}
fn resolve_table(
&self,
origin: Origin,
reference: &Structured,
) -> core::result::Result<(String, Range), CellError> {
let (sheet, table) = self.find_table(origin, reference)?;
let header = table.header_row_count.unwrap_or(1);
let totals = table.totals_row_count.unwrap_or(0);
let (top, bottom) = (table.range.start.row.index(), table.range.end.row.index());
let body = (top + header, bottom.saturating_sub(totals));
let (first, last) = match reference.part {
TablePart::All => (top, bottom),
TablePart::Data => body,
TablePart::Headers => (top, top + header.saturating_sub(1)),
TablePart::Totals => (bottom.saturating_sub(totals.saturating_sub(1)), bottom),
TablePart::HeadersData => (top, body.1),
TablePart::DataTotals => (body.0, bottom),
TablePart::ThisRow => {
let row = origin.at.row.index();
if row < top || row > bottom {
return Err(CellError::Value);
}
(row, row)
}
};
if first > last || (reference.part == TablePart::Totals && totals == 0) {
return Err(CellError::Ref);
}
let (left, right) = match &reference.columns {
None => (table.range.start.col.index(), table.range.end.col.index()),
Some((first_name, last_name)) => {
let offset = |name: &String| {
table
.columns
.iter()
.position(|c| c.name.eq_ignore_ascii_case(name))
.and_then(|i| u32::try_from(i).ok())
.map(|i| table.range.start.col.index() + i)
.ok_or(CellError::Name)
};
let start = offset(first_name)?;
let end = match last_name {
Some(name) => offset(name)?,
None => start,
};
(start.min(end), start.max(end))
}
};
let corner = |col: u32, row: u32| Some(CellRef::new(Col::new(col)?, Row::new(row)?));
let (start, end) = (corner(left, first), corner(right, last));
match (start, end) {
(Some(start), Some(end)) => Ok((sheet, Range { start, end })),
_ => Err(CellError::Ref),
}
}
fn find_table<'t>(
&'t self,
origin: Origin,
reference: &Structured,
) -> core::result::Result<(String, &'t crate::model::table::Table), CellError> {
let Some(name) = &reference.table else {
let sheet = self.book.sheet(origin.sheet).ok_or(CellError::Ref)?;
let table = sheet
.tables
.iter()
.find(|t| t.range.contains(origin.at))
.ok_or(CellError::Name)?;
return Ok((sheet.title().to_owned(), table));
};
self.book
.sheets()
.iter()
.find_map(|sheet| {
let table = sheet
.tables
.iter()
.find(|t| t.display_name.eq_ignore_ascii_case(name))?;
Some((sheet.title().to_owned(), table))
})
.ok_or(CellError::Name)
}
pub(crate) fn range(&mut self, origin: Origin, sheet: Option<&str>, range: Range) -> Value {
if let Some((book, name)) = sheet.and_then(external_ref) {
return self.external(book, name, range);
}
let Some(index) = self.sheet_index(origin, sheet) else {
return Value::Error(CellError::Ref);
};
let Some(range) = self.clip(index, range) else {
return Value::Blank;
};
if range.start == range.end {
return self.cell(index, range.start);
}
if (range.width() as usize).saturating_mul(range.height() as usize) > MAX_RANGE_CELLS {
return Value::Error(CellError::Value);
}
if let Some(value) = self.ranges.get(&(index, range)) {
return value.clone();
}
if let Some(value) = self.shared.and_then(|sh| sh.range(index, range)) {
return value;
}
let hits = self.cycle_hits;
let rows = (range.start.row.index()..=range.end.row.index())
.filter_map(Row::new)
.map(|row| {
(range.start.col.index()..=range.end.col.index())
.filter_map(Col::new)
.map(|col| self.cell(index, CellRef::new(col, row)))
.collect()
})
.collect();
let value = Value::array(rows);
if self.cycle_hits == hits && self.deferred.is_none() {
match self.shared {
Some(sh) => sh.keep_range(index, range, &value),
None => {
self.ranges.insert((index, range), value.clone());
}
}
}
value
}
fn clip(&mut self, sheet: usize, range: Range) -> Option<Range> {
let used = if let Some(used) = self.dims.get(sheet).copied().flatten() {
used
} else {
let used = self.book.sheet(sheet)?.dimension()?;
if let Some(slot) = self.dims.get_mut(sheet) {
*slot = Some(used);
}
used
};
if range.start.row > used.end.row || range.start.col > used.end.col {
return None;
}
Some(Range {
start: range.start,
end: CellRef::new(
range.end.col.min(used.end.col),
range.end.row.min(used.end.row),
),
})
}
fn external(&self, book: usize, sheet: &str, range: Range) -> Value {
let Some(cells) = self
.book
.external
.get(book)
.and_then(|b| b.sheet(sheet))
.map(|s| &s.cells)
else {
return Value::Error(CellError::Ref);
};
let at = |row, col| match cells.get(&(row, col)) {
None | Some(CellValue::Empty) => Value::Blank,
Some(CellValue::Number(n)) => Value::Number(*n),
Some(CellValue::Text(t)) => Value::Text(t.to_string()),
Some(CellValue::Bool(b)) => Value::Bool(*b),
Some(CellValue::Error(e)) => Value::Error(*e),
Some(other) => Value::Text(other.plain_text().unwrap_or_default()),
};
if range.start == range.end {
return at(range.start.row, range.start.col);
}
let Some(&(last_row, _)) = cells.keys().next_back() else {
return Value::Blank;
};
let end = range.end.row.min(last_row);
let rows = (range.start.row.index()..=end.index())
.filter_map(Row::new)
.map(|row| {
(range.start.col.index()..=range.end.col.index())
.filter_map(Col::new)
.map(|col| at(row, col))
.collect()
})
.collect();
Value::array(rows)
}
pub(crate) fn sheet_index(&self, origin: Origin, sheet: Option<&str>) -> Option<usize> {
match sheet {
None => Some(origin.sheet),
Some(name) => self
.book
.sheets()
.iter()
.position(|s| same_name(s.title(), name)),
}
}
fn binary(&mut self, origin: Origin, op: BinaryOp, a: &Expr, b: &Expr) -> Value {
match op {
BinaryOp::Intersect => return self.intersect(origin, a, b),
BinaryOp::Union => return self.union(origin, a, b),
BinaryOp::Span => return self.span(origin, a, b),
_ => {}
}
let (x, y) = (self.eval_value(origin, a), self.eval_value(origin, b));
binary_values(op, &x, &y)
}
fn intersect(&mut self, origin: Origin, a: &Expr, b: &Expr) -> Value {
let (
Expr::Range {
sheet, range: x, ..
},
Expr::Range { range: y, .. },
) = (a, b)
else {
return Value::Error(CellError::Value);
};
let (start, end) = (
CellRef::new(x.start.col.max(y.start.col), x.start.row.max(y.start.row)),
CellRef::new(x.end.col.min(y.end.col), x.end.row.min(y.end.row)),
);
if start.col > end.col || start.row > end.row {
return Value::Error(CellError::Null);
}
self.range(origin, sheet.as_deref(), Range { start, end })
}
fn span(&mut self, origin: Origin, a: &Expr, b: &Expr) -> Value {
let Some((sheet, range)) = spanned(&Expr::Binary(
BinaryOp::Span,
Box::new(a.clone()),
Box::new(b.clone()),
)) else {
return Value::Error(CellError::Value);
};
self.range(origin, sheet.as_deref(), range)
}
fn union(&mut self, origin: Origin, left: &Expr, right: &Expr) -> Value {
let areas = [self.eval_expr(origin, left), self.eval_expr(origin, right)];
let mut rows = Vec::new();
for v in areas {
match v {
Value::Array(r) => rows.extend(std::sync::Arc::unwrap_or_clone(r)),
other => rows.push(vec![other]),
}
}
Value::array(rows)
}
}
fn calls_total(expr: &Expr) -> bool {
match expr {
Expr::Call { name, args } => {
name == "SUBTOTAL" || name == "AGGREGATE" || args.iter().any(calls_total)
}
Expr::Apply { callee, args } => calls_total(callee) || args.iter().any(calls_total),
Expr::Unary(_, x) => calls_total(x),
Expr::Binary(_, a, b) => calls_total(a) || calls_total(b),
Expr::Array(rows) => rows.iter().flatten().any(calls_total),
_ => false,
}
}
fn position(e: Option<&Expr>) -> Option<u32> {
match e {
None | Some(Expr::Missing) => Some(0),
#[expect(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
reason = "the guard keeps it within a sheet's rows"
)]
Some(Expr::Number(n)) if (0.0..1_048_577.0).contains(n) => Some(n.trunc() as u32),
_ => None,
}
}
pub(crate) fn same_name(a: &str, b: &str) -> bool {
a == b
|| a.chars()
.flat_map(char::to_lowercase)
.eq(b.chars().flat_map(char::to_lowercase))
}
fn unary(op: UnaryOp, v: &Value) -> Value {
if op == UnaryOp::Plus {
return v.clone();
}
if let Value::Array(rows) = v {
return Value::array(
rows.iter()
.map(|r| r.iter().map(|x| unary(op, x)).collect())
.collect(),
);
}
let n = match v.number() {
Ok(n) => n,
Err(e) => return Value::Error(e),
};
Value::Number(match op {
UnaryOp::Neg => -n,
UnaryOp::Plus => n,
UnaryOp::Percent => n / 100.0,
})
}
#[must_use]
pub fn binary_values(op: BinaryOp, a: &Value, b: &Value) -> Value {
if matches!(a, Value::Array(_)) || matches!(b, Value::Array(_)) {
return broadcast(op, a, b);
}
match op {
BinaryOp::Eq | BinaryOp::Ne | BinaryOp::Lt | BinaryOp::Le | BinaryOp::Gt | BinaryOp::Ge => {
if let Some(e) = a.error().or_else(|| b.error()) {
return Value::Error(e);
}
let ord = compare(a, b);
Value::Bool(match op {
BinaryOp::Eq => ord.is_eq(),
BinaryOp::Ne => ord.is_ne(),
BinaryOp::Lt => ord.is_lt(),
BinaryOp::Le => ord.is_le(),
BinaryOp::Gt => ord.is_gt(),
_ => ord.is_ge(),
})
}
BinaryOp::Concat => match (a.text(), b.text()) {
(Ok(x), Ok(y)) => Value::Text(x + &y),
(Err(e), _) | (_, Err(e)) => Value::Error(e),
},
_ => {
let (left, right) = match (a.number(), b.number()) {
(Ok(x), Ok(y)) => (x, y),
(Err(e), _) | (_, Err(e)) => return Value::Error(e),
};
match op {
BinaryOp::Add => Value::Number(left + right),
BinaryOp::Sub => Value::Number(left - right),
BinaryOp::Mul => Value::Number(left * right),
BinaryOp::Div => {
if right == 0.0 {
Value::Error(CellError::Div0)
} else {
Value::Number(left / right)
}
}
BinaryOp::Pow => {
let r = left.powf(right);
if r.is_finite() {
Value::Number(r)
} else {
Value::Error(CellError::Num)
}
}
_ => Value::Error(CellError::Value),
}
}
}
}
fn broadcast(op: BinaryOp, a: &Value, b: &Value) -> Value {
let (ar, ac) = shape(a);
let (br, bc) = shape(b);
let (rows, cols) = (ar.max(br), ac.max(bc));
if rows.saturating_mul(cols) > MAX_RANGE_CELLS {
return Value::Error(CellError::Num);
}
let out = (0..rows)
.map(|r| {
(0..cols)
.map(|c| binary_values(op, &at(a, r, c), &at(b, r, c)))
.collect()
})
.collect();
Value::array(out)
}
pub(crate) fn shape(v: &Value) -> (usize, usize) {
match v {
Value::Array(rows) => (rows.len(), rows.iter().map(Vec::len).max().unwrap_or(0)),
_ => (1, 1),
}
}
pub(crate) fn at(v: &Value, row: usize, col: usize) -> Value {
match v {
Value::Array(rows) => {
let r = if rows.len() == 1 { 0 } else { row };
let Some(line) = rows.get(r) else {
return Value::Error(CellError::Na);
};
let c = if line.len() == 1 { 0 } else { col };
line.get(c).cloned().unwrap_or(Value::Error(CellError::Na))
}
other => other.clone(),
}
}
#[must_use]
pub fn spanned(expr: &Expr) -> Option<(Option<String>, Range)> {
match expr {
Expr::Range { sheet, range, .. } => Some((sheet.clone(), *range)),
Expr::Binary(BinaryOp::Span, a, b) => {
let (sheet, x) = spanned(a)?;
let (_, y) = spanned(b)?;
Some((
sheet,
Range {
start: CellRef::new(x.start.col.min(y.start.col), x.start.row.min(y.start.row)),
end: CellRef::new(x.end.col.max(y.end.col), x.end.row.max(y.end.row)),
},
))
}
_ => None,
}
}
pub fn recalculate(book: &mut Spreadsheet, sheet: Option<usize>, options: &Options<'_>) -> usize {
let (deps, trees) = Dependencies::of_with_trees(book);
let indexed: Vec<usize> = (0..deps.formulas.len())
.filter(|&i| sheet.is_none_or(|only| only == deps.formulas[i].sheet))
.collect();
let mut results = pass(book, &deps, &indexed, &|i| &trees[i], None, options);
let known: HashSet<(usize, CellRef)> = indexed
.iter()
.map(|&i| (deps.formulas[i].sheet, deps.formulas[i].at))
.collect();
{
let mut engine = match options.functions() {
Some(custom) => Engine::with_functions(book, custom),
None => Engine::new(book),
};
for (index, s) in book.sheets().iter().enumerate() {
if sheet.is_some_and(|only| only != index) {
continue;
}
for (at, cell) in s.iter() {
if let CellValue::Formula { formula, .. } = &cell.value
&& !known.contains(&(index, at))
{
let value = engine.eval(Origin::new(index, at), formula);
results.push((index, at, value));
}
}
}
}
store(book, results)
}
fn pass<'t>(
book: &Spreadsheet,
deps: &Dependencies,
nodes: &[usize],
tree_of: &(dyn Fn(usize) -> &'t Expr + Sync),
stale: Option<&HashSet<(usize, CellRef)>>,
options: &Options<'_>,
) -> Vec<(usize, CellRef, Value)> {
let (levels, tail) = deps.levels(nodes);
let threads = workers(nodes.len(), options);
let shared = (threads > 1).then(|| Shared {
slots: nodes
.iter()
.enumerate()
.map(|(slot, &i)| ((deps.formulas[i].sheet, deps.formulas[i].at), slot))
.collect(),
values: nodes.iter().map(|_| std::sync::OnceLock::new()).collect(),
claimed: nodes
.iter()
.map(|_| std::sync::atomic::AtomicBool::new(false))
.collect(),
ranges: std::sync::RwLock::default(),
});
let mut engine = match options.functions() {
Some(custom) => Engine::with_functions(book, custom),
None => Engine::new(book),
};
engine.stale = stale;
let mut results = Vec::with_capacity(nodes.len());
let total = nodes.len();
let mut done = 0;
let mut compute = |engine: &mut Engine<'_>, i: usize, results: &mut Vec<_>| {
options.report(Stage::Recalculating, done, Some(total), "");
done += 1;
let Node { sheet, at, .. } = deps.formulas[i];
let value = engine.eval_tree(Origin::new(sheet, at), tree_of(i));
engine.remember(sheet, at, &value);
results.push((sheet, at, value));
};
if let Some(shared) = &shared {
parallel(
book, deps, tree_of, nodes, &levels, shared, stale, threads, options,
);
engine.shared = Some(shared);
for (slot, &i) in nodes.iter().enumerate() {
if let Some(value) = shared.values[slot].get() {
results.push((deps.formulas[i].sheet, deps.formulas[i].at, value.clone()));
}
}
for &i in &tail {
compute(&mut engine, i, &mut results);
}
} else {
for i in levels.into_iter().flatten().chain(tail) {
compute(&mut engine, i, &mut results);
}
}
results
}
fn store(book: &mut Spreadsheet, results: Vec<(usize, CellRef, Value)>) -> usize {
let computed = results.len();
for (index, at, value) in results {
let Some(sheet) = book.sheet_mut(index) else {
continue;
};
if let CellValue::Formula { cached, .. } = &mut sheet.entry(at).value {
*cached = Some(Box::new(stored(&value)));
}
}
computed
}
pub fn recalculate_cell(book: &mut Spreadsheet, sheet: usize, at: CellRef) -> bool {
recalculate_cell_with(book, sheet, at, &Options::default())
}
pub fn recalculate_cell_with(
book: &mut Spreadsheet,
sheet: usize,
at: CellRef,
options: &Options<'_>,
) -> bool {
let value = {
let Some(CellValue::Formula { formula, .. }) =
book.sheet(sheet).and_then(|s| s.get(at)).map(|c| &c.value)
else {
return false;
};
let formula = formula.clone();
let mut engine = match options.functions() {
Some(custom) => Engine::with_functions(book, custom),
None => Engine::new(book),
};
engine.eval(Origin::new(sheet, at), &formula)
};
let Some(s) = book.sheet_mut(sheet) else {
return false;
};
let CellValue::Formula { cached, .. } = &mut s.entry(at).value else {
return false;
};
*cached = Some(Box::new(stored(&value)));
true
}
const WAIT_SPINS: usize = 1024;
fn workers(formulas: usize, options: &Options<'_>) -> usize {
const MIN_PARALLEL: usize = 20_000;
if cfg!(target_arch = "wasm32") || formulas < MIN_PARALLEL || options.functions().is_some() {
return 1;
}
std::thread::available_parallelism().map_or(1, |n| n.get().min(8))
}
#[expect(clippy::too_many_arguments, reason = "the parts of one pass, borrowed")]
fn parallel<'t>(
book: &Spreadsheet,
deps: &Dependencies,
tree_of: &(dyn Fn(usize) -> &'t Expr + Sync),
indexed: &[usize],
levels: &[Vec<usize>],
shared: &Shared,
stale: Option<&HashSet<(usize, CellRef)>>,
threads: usize,
options: &Options<'_>,
) {
use std::sync::Barrier;
use std::sync::atomic::{AtomicUsize, Ordering};
const MIN_WAVE: usize = 256;
let slot_of: HashMap<usize, usize> = indexed
.iter()
.enumerate()
.map(|(slot, &i)| (i, slot))
.collect();
let cursors: Vec<AtomicUsize> = levels.iter().map(|_| AtomicUsize::new(0)).collect();
let done = AtomicUsize::new(0);
let barrier = Barrier::new(threads);
let total = indexed.len();
let work = |main: bool, report: &dyn Fn(usize)| {
let mut engine = Engine::new(book);
engine.shared = Some(shared);
engine.stale = stale;
for (level, wave) in levels.iter().enumerate() {
let large = wave.len() >= MIN_WAVE;
if !large && !main {
continue;
}
if large {
barrier.wait();
}
loop {
let k = cursors[level].fetch_add(1, Ordering::Relaxed);
let Some(&i) = wave.get(k) else { break };
let Node { sheet, at, .. } = deps.formulas[i];
let value = engine.eval_tree(Origin::new(sheet, at), tree_of(i));
let _ = shared.values[slot_of[&i]].set(value);
let finished = done.fetch_add(1, Ordering::Relaxed);
report(finished);
}
if large {
barrier.wait();
}
}
};
std::thread::scope(|scope| {
for _ in 1..threads {
scope.spawn(|| work(false, &|_| {}));
}
work(true, &|finished| {
options.report(Stage::Recalculating, finished, Some(total), "");
});
});
}
pub(crate) fn stored_value(cell: &CellValue) -> Value {
match cell {
CellValue::Number(n) => Value::Number(*n),
CellValue::Text(t) => Value::Text(t.to_string()),
rich @ CellValue::RichText(_) => Value::Text(rich.plain_text().unwrap_or_default()),
CellValue::Bool(b) => Value::Bool(*b),
CellValue::Error(e) => Value::Error(*e),
CellValue::Empty | CellValue::Formula { .. } => Value::Blank,
}
}
pub(crate) fn stored(value: &Value) -> CellValue {
match value {
Value::Blank => CellValue::Empty,
Value::Number(n) => CellValue::Number(*n),
Value::Text(t) => CellValue::Text(t.as_str().into()),
Value::Bool(b) => CellValue::Bool(*b),
Value::Error(e) => CellValue::Error(*e),
Value::Lambda(_) => CellValue::Error(CellError::Calc),
Value::Array(rows) => rows
.first()
.and_then(|r| r.first())
.map_or(CellValue::Empty, stored),
}
}
#[derive(Default)]
struct Graph {
ranges: Vec<(usize, Range)>,
members: Vec<Vec<usize>>,
readers: Vec<Vec<usize>>,
reads: Vec<Vec<usize>>,
member_of: Vec<Vec<usize>>,
}
struct Node {
sheet: usize,
at: CellRef,
reads: Vec<(usize, Range)>,
always: bool,
}
const VOLATILE: [&str; 8] = [
"NOW",
"TODAY",
"RAND",
"RANDBETWEEN",
"OFFSET",
"INDIRECT",
"CELL",
"INFO",
];
pub struct Dependencies {
formulas: Vec<Node>,
}
impl Dependencies {
#[must_use]
pub fn of(book: &Spreadsheet) -> Self {
Self::of_with_trees(book).0
}
fn of_with_trees(book: &Spreadsheet) -> (Self, Vec<Expr>) {
let mut formulas = Vec::new();
let mut trees = Vec::new();
let cells: Vec<(usize, CellRef, &CellValue)> = book
.sheets()
.iter()
.enumerate()
.flat_map(|(index, sheet)| {
sheet
.iter()
.filter(|(_, cell)| matches!(cell.value, CellValue::Formula { .. }))
.map(move |(at, cell)| (index, at, &cell.value))
})
.collect();
let parse_chunk = |chunk: &[(usize, CellRef, &CellValue)]| {
let mut refs = Refs::new(book);
chunk
.iter()
.filter_map(|&(index, at, value)| node_of(&mut refs, index, at, value))
.collect::<Vec<_>>()
};
let threads = workers(cells.len(), &Options::default());
let parts: Vec<Vec<(Node, Expr)>> = if threads > 1 {
let size = cells.len().div_ceil(threads);
std::thread::scope(|scope| {
#[expect(
clippy::needless_collect,
reason = "every thread must be spawned before the first join"
)]
let handles: Vec<_> = cells
.chunks(size)
.map(|chunk| scope.spawn(move || parse_chunk(chunk)))
.collect();
handles.into_iter().filter_map(|h| h.join().ok()).collect()
})
} else {
vec![parse_chunk(&cells)]
};
for (node, tree) in parts.into_iter().flatten() {
formulas.push(node);
trees.push(tree);
}
(Self { formulas }, trees)
}
#[must_use]
pub fn len(&self) -> usize {
self.formulas.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.formulas.is_empty()
}
pub fn note(&mut self, book: &Spreadsheet, sheet: usize, at: CellRef) {
self.formulas
.retain(|node| node.sheet != sheet || node.at != at);
if let Some(value) = book.sheet(sheet).and_then(|s| s.get(at)).map(|c| &c.value)
&& let Some((node, _)) = node_of(&mut Refs::new(book), sheet, at, value)
{
self.formulas.push(node);
}
}
fn ordered(&self, nodes: &[usize]) -> Vec<usize> {
let (levels, tail) = self.levels(nodes);
levels.into_iter().flatten().chain(tail).collect()
}
fn affected(&self, changed: &[(usize, CellRef)]) -> Vec<usize> {
let all: Vec<usize> = (0..self.formulas.len()).collect();
let graph = self.graph(&all);
let mut dirty = vec![false; self.formulas.len()];
let mut queue: Vec<usize> = Vec::new();
let mut dirty_range = vec![false; graph.members.len()];
let mut ranges: Vec<usize> = Vec::new();
for (id, &(sheet, range)) in graph.ranges.iter().enumerate() {
if changed
.iter()
.any(|&(s, at)| s == sheet && range.contains(at))
{
dirty_range[id] = true;
ranges.push(id);
}
}
for (i, node) in self.formulas.iter().enumerate() {
if node.always {
dirty[i] = true;
queue.push(i);
}
}
while !queue.is_empty() || !ranges.is_empty() {
while let Some(id) = ranges.pop() {
for &r in &graph.readers[id] {
if !dirty[r] {
dirty[r] = true;
queue.push(r);
}
}
}
while let Some(i) = queue.pop() {
for &id in &graph.member_of[i] {
if !dirty_range[id] {
dirty_range[id] = true;
ranges.push(id);
}
}
}
}
all.into_iter().filter(|&i| dirty[i]).collect()
}
fn graph(&self, nodes: &[usize]) -> Graph {
let mut by_sheet: HashMap<usize, Vec<(CellRef, usize)>> = HashMap::new();
for &i in nodes {
by_sheet
.entry(self.formulas[i].sheet)
.or_default()
.push((self.formulas[i].at, i));
}
for list in by_sheet.values_mut() {
list.sort_unstable();
}
let mut ids: HashMap<(usize, Range), usize> = HashMap::new();
let mut graph = Graph {
reads: vec![Vec::new(); self.formulas.len()],
member_of: vec![Vec::new(); self.formulas.len()],
..Graph::default()
};
for &i in nodes {
for &(sheet, range) in &self.formulas[i].reads {
let id = *ids.entry((sheet, range)).or_insert_with(|| {
graph.readers.push(Vec::new());
graph.ranges.push((sheet, range));
graph.ranges.len() - 1
});
if !graph.reads[i].contains(&id) {
graph.readers[id].push(i);
graph.reads[i].push(id);
}
}
}
graph.members = map_chunks(&graph.ranges, |&(sheet, range)| {
formulas_in(&by_sheet, sheet, range)
});
for (id, members) in graph.members.iter().enumerate() {
for &j in members {
graph.member_of[j].push(id);
}
}
graph
}
fn levels(&self, nodes: &[usize]) -> (Vec<Vec<usize>>, Vec<usize>) {
let graph = self.graph(nodes);
let mut range_left: Vec<usize> = graph.members.iter().map(Vec::len).collect();
let mut waiting: HashMap<usize, usize> =
nodes.iter().map(|&i| (i, graph.reads[i].len())).collect();
let (range_readers, member_of) = (&graph.readers, &graph.member_of);
let mut wave: Vec<usize> = nodes.iter().copied().filter(|i| waiting[i] == 0).collect();
let mut ready: Vec<usize> = (0..range_left.len())
.filter(|&id| range_left[id] == 0)
.collect();
let mut release = |ready: &mut Vec<usize>, next: &mut Vec<usize>| {
while let Some(id) = ready.pop() {
for &r in &range_readers[id] {
if let Some(left) = waiting.get_mut(&r) {
*left -= 1;
if *left == 0 {
next.push(r);
}
}
}
}
};
release(&mut ready, &mut wave);
let mut levels: Vec<Vec<usize>> = Vec::new();
while !wave.is_empty() {
let mut next = Vec::new();
for &i in &wave {
for &id in &member_of[i] {
range_left[id] -= 1;
if range_left[id] == 0 {
ready.push(id);
}
}
}
release(&mut ready, &mut next);
levels.push(std::mem::replace(&mut wave, next));
}
let placed: HashSet<usize> = levels.iter().flatten().copied().collect();
let tail = nodes
.iter()
.copied()
.filter(|i| !placed.contains(i))
.collect();
(levels, tail)
}
pub fn recalculate_from(&self, book: &mut Spreadsheet, changed: &[(usize, CellRef)]) -> usize {
self.recalculate_from_with(book, changed, &Options::default())
}
pub fn recalculate_from_with(
&self,
book: &mut Spreadsheet,
changed: &[(usize, CellRef)],
options: &Options<'_>,
) -> usize {
let nodes = self.affected(changed);
let stale: HashSet<(usize, CellRef)> = nodes
.iter()
.map(|&i| (self.formulas[i].sheet, self.formulas[i].at))
.collect();
let texts: Vec<&str> = nodes
.iter()
.filter_map(|&i| {
let Node { sheet, at, .. } = self.formulas[i];
match book.sheet(sheet).and_then(|s| s.get(at)).map(|c| &c.value) {
Some(CellValue::Formula { formula, .. }) => Some(formula.as_str()),
_ => None,
}
})
.collect();
if texts.len() != nodes.len() {
return self.recompute_one_by_one(book, &nodes, options);
}
let trees = parse_all(&texts, options);
let placed: HashMap<usize, usize> =
nodes.iter().enumerate().map(|(k, &i)| (i, k)).collect();
let blank = Expr::Missing;
let results = pass(
book,
self,
&nodes,
&|i| placed.get(&i).map_or(&blank, |&k| &trees[k]),
Some(&stale),
options,
);
store(book, results)
}
fn recompute_one_by_one(
&self,
book: &mut Spreadsheet,
nodes: &[usize],
options: &Options<'_>,
) -> usize {
let order = self.ordered(nodes);
let mut results = Vec::new();
{
let mut engine = match options.functions() {
Some(custom) => Engine::with_functions(book, custom),
None => Engine::new(book),
};
let total = order.len();
for (step, &i) in order.iter().enumerate() {
options.report(Stage::Recalculating, step, Some(total), "");
let Node { sheet, at, .. } = self.formulas[i];
let Some(CellValue::Formula { formula, .. }) =
book.sheet(sheet).and_then(|s| s.get(at)).map(|c| &c.value)
else {
continue;
};
let value = engine.eval(Origin::new(sheet, at), formula);
engine.remember(sheet, at, &value);
results.push((sheet, at, value));
}
}
store(book, results)
}
}
fn formulas_in(
by_sheet: &HashMap<usize, Vec<(CellRef, usize)>>,
sheet: usize,
range: Range,
) -> Vec<usize> {
let Some(list) = by_sheet.get(&sheet) else {
return Vec::new();
};
let mut out = Vec::new();
for col in range.start.col.index()..=range.end.col.index() {
let Some(col) = Col::new(col) else { continue };
let first = CellRef::new(col, range.start.row);
let from = list.partition_point(|(at, _)| *at < first);
out.extend(
list[from..]
.iter()
.take_while(|(at, _)| at.col == col && at.row <= range.end.row)
.map(|(_, i)| *i),
);
}
out
}
fn node_of(
refs: &mut Refs<'_>,
sheet: usize,
at: CellRef,
value: &CellValue,
) -> Option<(Node, Expr)> {
let CellValue::Formula { formula, .. } = value else {
return None;
};
let expr = parse(formula).ok()?;
let (mut reads, mut always) = (Vec::new(), false);
collect_refs(&expr, sheet, refs, &mut reads, &mut always);
Some((
Node {
sheet,
at,
reads,
always,
},
expr,
))
}
fn map_chunks<T: Sync, R: Send>(items: &[T], f: impl Fn(&T) -> R + Sync) -> Vec<R> {
let threads = workers(items.len(), &Options::default());
if threads <= 1 {
return items.iter().map(&f).collect();
}
let size = items.len().div_ceil(threads);
std::thread::scope(|scope| {
let handles: Vec<_> = items
.chunks(size)
.map(|chunk| {
let f = &f;
scope.spawn(move || chunk.iter().map(f).collect::<Vec<_>>())
})
.collect();
handles
.into_iter()
.filter_map(|h| h.join().ok())
.flatten()
.collect()
})
}
fn parse_all(texts: &[&str], options: &Options<'_>) -> Vec<Expr> {
let one = |text: &&str| parse(text).unwrap_or(Expr::Error(CellError::Name));
let threads = workers(texts.len(), options);
if threads <= 1 {
return texts.iter().map(one).collect();
}
let size = texts.len().div_ceil(threads);
std::thread::scope(|scope| {
#[expect(
clippy::needless_collect,
reason = "every thread must be spawned before the first join"
)]
let handles: Vec<_> = texts
.chunks(size)
.map(|chunk| scope.spawn(move || chunk.iter().map(one).collect::<Vec<_>>()))
.collect();
handles
.into_iter()
.filter_map(|h| h.join().ok())
.flatten()
.collect()
})
}
pub fn recalculate_from(book: &mut Spreadsheet, changed: &[(usize, CellRef)]) -> usize {
Dependencies::of(book).recalculate_from(book, changed)
}
pub fn recalculate_from_with(
book: &mut Spreadsheet,
changed: &[(usize, CellRef)],
options: &Options<'_>,
) -> usize {
Dependencies::of(book).recalculate_from_with(book, changed, options)
}
fn collect_refs(
expr: &Expr,
own_sheet: usize,
refs: &mut Refs<'_>,
out: &mut Vec<(usize, Range)>,
always: &mut bool,
) {
match expr {
Expr::Range { sheet, range, .. } => {
let index = match sheet {
None => Some(own_sheet),
Some(name) => refs
.book
.sheets()
.iter()
.position(|s| same_name(s.title(), name)),
};
if let Some(index) = index {
out.push((index, *range));
}
}
Expr::Name(name) => {
let (ranges, dynamic) = refs.name(own_sheet, name);
if ranges.is_empty() || dynamic {
*always = true;
}
out.extend(ranges);
}
Expr::Structured(_) => *always = true,
Expr::Unary(_, inner) => collect_refs(inner, own_sheet, refs, out, always),
Expr::Binary(_, a, b) => {
collect_refs(a, own_sheet, refs, out, always);
collect_refs(b, own_sheet, refs, out, always);
}
Expr::Call { name, args } => {
let upper = name.to_ascii_uppercase();
if VOLATILE.contains(&upper.as_str()) {
*always = true;
}
if upper == "INDIRECT"
&& args.len() == 1
&& let Some(text) = refs.text_of(own_sheet, &args[0])
&& let Ok(target) = parse(&text)
&& matches!(target, Expr::Range { .. } | Expr::Name(_))
{
collect_refs(&target, own_sheet, refs, out, always);
}
for arg in args {
collect_refs(arg, own_sheet, refs, out, always);
}
}
Expr::Apply { callee, args } => {
collect_refs(callee, own_sheet, refs, out, always);
for arg in args {
collect_refs(arg, own_sheet, refs, out, always);
}
}
Expr::Array(rows) => {
for cell in rows.iter().flatten() {
collect_refs(cell, own_sheet, refs, out, always);
}
}
Expr::Number(_) | Expr::Text(_) | Expr::Bool(_) | Expr::Error(_) | Expr::Missing => {}
}
}
type NameReads = (Vec<(usize, Range)>, bool);
pub(crate) struct Refs<'b> {
book: &'b Spreadsheet,
names: HashMap<(usize, String), NameReads>,
depth: usize,
}
impl<'b> Refs<'b> {
fn new(book: &'b Spreadsheet) -> Self {
Self {
book,
names: HashMap::new(),
depth: 0,
}
}
fn text_of(&self, own_sheet: usize, arg: &Expr) -> Option<String> {
match arg {
Expr::Text(text) => Some(text.clone()),
Expr::Range { sheet, range, .. } if range.start == range.end => {
let index = match sheet {
None => own_sheet,
Some(name) => self
.book
.sheets()
.iter()
.position(|s| same_name(s.title(), name))?,
};
match &self.book.sheet(index)?.get(range.start)?.value {
CellValue::Text(text) => Some(text.to_string()),
CellValue::Formula { cached, .. } => match cached.as_deref()? {
CellValue::Text(text) => Some(text.to_string()),
_ => None,
},
_ => None,
}
}
_ => None,
}
}
fn name(&mut self, sheet: usize, name: &str) -> NameReads {
const MAX_NAME_DEPTH: usize = 8;
let key = (sheet, name.to_lowercase());
if let Some(found) = self.names.get(&key) {
return found.clone();
}
if self.depth >= MAX_NAME_DEPTH {
return (Vec::new(), true);
}
let defined = self
.book
.defined_names
.iter()
.filter(|n| n.name.eq_ignore_ascii_case(name) || n.name.to_lowercase() == key.1)
.min_by_key(|n| n.sheet != Some(sheet));
let mut out = Vec::new();
let mut dynamic = defined.is_none();
if let Some(expr) = defined.and_then(|n| parse(&n.formula).ok()) {
self.depth += 1;
collect_refs(&expr, sheet, self, &mut out, &mut dynamic);
self.depth -= 1;
}
self.names.insert(key, (out.clone(), dynamic));
(out, dynamic)
}
}
fn external_ref(sheet: &str) -> Option<(usize, &str)> {
let (index, name) = sheet.strip_prefix('[')?.split_once(']')?;
Some((index.parse::<usize>().ok()?.checked_sub(1)?, name))
}