spreadsheet_kit/analysis/
formula.rs

1use crate::model::{
2    FORMULA_PARSE_FAILED_PREFIX, FormulaGroup, FormulaParseDiagnosticsBuilder, FormulaParsePolicy,
3    format_formula_parse_failure,
4};
5use crate::utils::column_number_to_name;
6use anyhow::{Context, Result, anyhow};
7use formualizer_parse::{
8    ASTNode,
9    parser::{BatchParser, CollectPolicy, ReferenceType},
10    pretty::canonical_formula,
11};
12use parking_lot::{Mutex, RwLock};
13use std::collections::{HashMap, HashSet};
14use std::sync::Arc;
15use umya_spreadsheet::{CellFormulaValues, Worksheet};
16
17const RANGE_EXPANSION_LIMIT: usize = 500;
18
19#[derive(Clone)]
20pub struct FormulaAtlas {
21    parser: Arc<Mutex<BatchParser>>,
22    cache: Arc<RwLock<HashMap<String, Arc<ParsedFormula>>>>,
23    _volatility: Arc<Vec<String>>,
24}
25
26#[derive(Debug, Clone)]
27pub struct ParsedFormula {
28    pub fingerprint: String,
29    pub canonical: String,
30    pub is_volatile: bool,
31    pub dependencies: Vec<String>,
32}
33
34impl FormulaAtlas {
35    pub fn new(volatility_functions: Vec<String>) -> Self {
36        let normalized: Vec<String> = volatility_functions
37            .into_iter()
38            .map(|s| s.to_ascii_uppercase())
39            .collect();
40        let lookup = Arc::new(normalized);
41        let closure_lookup = lookup.clone();
42        let parser = BatchParser::builder()
43            .with_volatility_classifier(move |name| {
44                let upper = name.to_ascii_uppercase();
45                closure_lookup.iter().any(|entry| entry == &upper)
46            })
47            .build();
48        Self {
49            parser: Arc::new(Mutex::new(parser)),
50            cache: Arc::new(RwLock::new(HashMap::new())),
51            _volatility: lookup,
52        }
53    }
54
55    pub fn parse(&self, formula: &str) -> Result<Arc<ParsedFormula>> {
56        if let Some(existing) = self.cache.read().get(formula) {
57            return Ok(existing.clone());
58        }
59
60        let ast = {
61            let mut parser = self.parser.lock();
62            parser
63                .parse(formula)
64                .with_context(|| format!("failed to parse formula: {formula}"))?
65        };
66        let parsed = Arc::new(parsed_from_ast(&ast));
67
68        self.cache
69            .write()
70            .insert(formula.to_string(), parsed.clone());
71        Ok(parsed)
72    }
73}
74
75impl Default for FormulaAtlas {
76    fn default() -> Self {
77        Self::new(default_volatility_functions())
78    }
79}
80
81fn unescape_formula_string(s: &str) -> String {
82    s.replace("\"\"", "\"")
83}
84
85fn parsed_from_ast(ast: &ASTNode) -> ParsedFormula {
86    let fingerprint = format!("{:016x}", ast.fingerprint());
87    let canonical = unescape_formula_string(&canonical_formula(ast));
88    let dependencies = ast
89        .get_dependencies()
90        .iter()
91        .map(|reference| reference_to_string(reference))
92        .collect();
93    ParsedFormula {
94        fingerprint,
95        canonical,
96        is_volatile: ast.contains_volatile(),
97        dependencies,
98    }
99}
100
101pub struct FormulaGraph {
102    precedents: HashMap<String, Vec<String>>,
103    dependents: HashMap<String, Vec<String>>,
104    groups: HashMap<String, FormulaGroupAccumulator>,
105    range_dependents: Vec<RangeDependentEntry>,
106    sheet_name: String,
107}
108
109#[derive(Debug, Clone)]
110struct RangeDependentEntry {
111    #[allow(dead_code)]
112    range_key: String,
113    reference: ReferenceType,
114    dependents: Vec<String>,
115}
116
117impl FormulaGraph {
118    pub fn build(
119        sheet: &Worksheet,
120        atlas: &FormulaAtlas,
121        policy: FormulaParsePolicy,
122        mut diagnostics: Option<&mut FormulaParseDiagnosticsBuilder>,
123    ) -> Result<Self> {
124        let sheet_name = sheet.get_name().to_string();
125        let mut precedents_build: HashMap<String, HashSet<String>> = HashMap::new();
126        let mut dependents_build: HashMap<String, HashSet<String>> = HashMap::new();
127        let mut groups: HashMap<String, FormulaGroupAccumulator> = HashMap::new();
128        let mut range_dependents_build: HashMap<String, (ReferenceType, HashSet<String>)> =
129            HashMap::new();
130
131        let collect_policy = CollectPolicy {
132            expand_small_ranges: true,
133            range_expansion_limit: RANGE_EXPANSION_LIMIT,
134            include_names: true,
135        };
136
137        for cell in sheet.get_cell_collection() {
138            if !cell.is_formula() {
139                continue;
140            }
141            let coordinate = cell.get_coordinate();
142            let address = coordinate.get_coordinate();
143            let formula_text = cell.get_formula();
144            if formula_text.is_empty() {
145                continue;
146            }
147            let formula_with_prefix = if formula_text.starts_with('=') {
148                formula_text.to_string()
149            } else {
150                format!("={}", formula_text)
151            };
152
153            let ast = {
154                let mut parser = atlas.parser.lock();
155                match parser.parse(&formula_with_prefix) {
156                    Ok(ast) => Some(ast),
157                    Err(batch_err) => {
158                        let fallback = formualizer_parse::parse(&formula_with_prefix);
159                        match fallback {
160                            Ok(ast) => Some(ast),
161                            Err(fallback_err) => {
162                                let parse_error = format_formula_parse_failure(
163                                    &formula_with_prefix,
164                                    &fallback_err,
165                                );
166
167                                tracing::warn!(
168                                    sheet = %sheet_name,
169                                    address = %address,
170                                    formula = %formula_with_prefix,
171                                    batch_error = %batch_err,
172                                    fallback_error = %parse_error,
173                                    "skipping unparsable formula cell"
174                                );
175
176                                match policy {
177                                    FormulaParsePolicy::Off => None,
178                                    FormulaParsePolicy::Warn => {
179                                        if let Some(diag) = diagnostics.as_deref_mut() {
180                                            diag.record_error(
181                                                &sheet_name,
182                                                &address,
183                                                &formula_with_prefix,
184                                                &parse_error,
185                                            );
186                                        }
187                                        None
188                                    }
189                                    FormulaParsePolicy::Fail => {
190                                        if let Some(diag) = diagnostics.as_deref_mut() {
191                                            diag.record_error(
192                                                &sheet_name,
193                                                &address,
194                                                &formula_with_prefix,
195                                                &parse_error,
196                                            );
197                                        }
198                                        return Err(anyhow!(
199                                            "{}sheet '{}' cell {}: {}",
200                                            FORMULA_PARSE_FAILED_PREFIX,
201                                            sheet_name,
202                                            address,
203                                            parse_error
204                                        ));
205                                    }
206                                }
207                            }
208                        }
209                    }
210                }
211            };
212
213            let Some(ast) = ast else {
214                continue;
215            };
216
217            let fingerprint = format!("{:016x}", ast.fingerprint());
218            let canonical = unescape_formula_string(&canonical_formula(&ast));
219            let is_volatile = ast.contains_volatile();
220
221            let (is_array, is_shared_type) = cell
222                .get_formula_obj()
223                .map(|obj| match obj.get_formula_type() {
224                    CellFormulaValues::Array => (true, false),
225                    CellFormulaValues::Shared => (false, true),
226                    _ => (false, false),
227                })
228                .unwrap_or((false, false));
229
230            let group =
231                groups
232                    .entry(fingerprint.clone())
233                    .or_insert_with(|| FormulaGroupAccumulator {
234                        canonical: canonical.clone(),
235                        addresses: Vec::new(),
236                        is_volatile,
237                        is_array,
238                        is_shared: is_shared_type,
239                    });
240            if cell.get_formula_shared_index().is_some() {
241                group.is_shared = true;
242            }
243            group.addresses.push(address.clone());
244            group.is_volatile |= is_volatile;
245
246            let refs = ast.collect_references(&collect_policy);
247            for reference in refs {
248                match &reference {
249                    ReferenceType::Cell {
250                        sheet, row, col, ..
251                    } => {
252                        let dep_addr = format_cell_address(sheet.as_deref(), *row, *col);
253                        precedents_build
254                            .entry(address.clone())
255                            .or_default()
256                            .insert(dep_addr.clone());
257                        dependents_build
258                            .entry(dep_addr)
259                            .or_default()
260                            .insert(address.clone());
261                    }
262                    ReferenceType::Range {
263                        start_row,
264                        start_col,
265                        end_row,
266                        end_col,
267                        ..
268                    } => {
269                        let prec_str = reference.to_string();
270                        precedents_build
271                            .entry(address.clone())
272                            .or_default()
273                            .insert(prec_str.clone());
274
275                        if is_large_or_infinite_range(*start_row, *start_col, *end_row, *end_col) {
276                            range_dependents_build
277                                .entry(prec_str)
278                                .or_insert_with(|| (reference.clone(), HashSet::new()))
279                                .1
280                                .insert(address.clone());
281                        }
282                    }
283                    ReferenceType::NamedRange(name) => {
284                        precedents_build
285                            .entry(address.clone())
286                            .or_default()
287                            .insert(name.clone());
288                    }
289                    ReferenceType::Table(_) | ReferenceType::External(_) => {
290                        let table_str = reference.to_string();
291                        precedents_build
292                            .entry(address.clone())
293                            .or_default()
294                            .insert(table_str);
295                    }
296                }
297            }
298        }
299
300        let precedents = precedents_build
301            .into_iter()
302            .map(|(k, v)| (k, v.into_iter().collect()))
303            .collect();
304        let dependents = dependents_build
305            .into_iter()
306            .map(|(k, v)| (k, v.into_iter().collect()))
307            .collect();
308        let range_dependents = range_dependents_build
309            .into_iter()
310            .map(|(key, (ref_type, addrs))| RangeDependentEntry {
311                range_key: key,
312                reference: ref_type,
313                dependents: addrs.into_iter().collect(),
314            })
315            .collect();
316
317        Ok(Self {
318            precedents,
319            dependents,
320            groups,
321            range_dependents,
322            sheet_name,
323        })
324    }
325
326    pub fn groups(&self) -> Vec<FormulaGroup> {
327        self.groups
328            .iter()
329            .map(|(fingerprint, group)| FormulaGroup {
330                fingerprint: fingerprint.clone(),
331                addresses: group.addresses.clone(),
332                count: Some(group.addresses.len() as u32),
333                formula: group.canonical.clone(),
334                is_array: group.is_array,
335                is_shared: group.is_shared,
336                is_volatile: group.is_volatile,
337            })
338            .collect()
339    }
340
341    pub fn precedents(&self, address: &str) -> Vec<String> {
342        self.precedents.get(address).cloned().unwrap_or_default()
343    }
344
345    pub fn dependents(&self, address: &str) -> Vec<String> {
346        self.dependents_limited(address, None).0
347    }
348
349    /// Returns cells that depend on the given address, with optional limit.
350    ///
351    /// Returns (dependents, was_truncated). If limit is Some and exceeded,
352    /// was_truncated is true and only limit dependents are returned.
353    ///
354    /// Performance: O(n) where n = number of large range references in the sheet.
355    /// Early exits when limit reached to keep response times bounded.
356    pub fn dependents_limited(&self, address: &str, limit: Option<usize>) -> (Vec<String>, bool) {
357        let mut result = self.dependents.get(address).cloned().unwrap_or_default();
358        let limit = limit.unwrap_or(usize::MAX);
359
360        if result.len() >= limit {
361            result.truncate(limit);
362            return (result, true);
363        }
364
365        if let Some((row, col)) = parse_cell_address(address) {
366            let (query_sheet, _) = split_sheet_prefix(address);
367            'outer: for entry in &self.range_dependents {
368                if range_contains_cell(&entry.reference, query_sheet, &self.sheet_name, row, col) {
369                    for addr in &entry.dependents {
370                        if !result.contains(addr) {
371                            result.push(addr.clone());
372                            if result.len() >= limit {
373                                break 'outer;
374                            }
375                        }
376                    }
377                }
378            }
379        }
380
381        let truncated = result.len() >= limit;
382        (result, truncated)
383    }
384}
385
386fn format_cell_address(sheet: Option<&str>, row: u32, col: u32) -> String {
387    let col_str = column_number_to_name(col);
388    match sheet {
389        Some(s) => format!("{}!{}{}", s, col_str, row),
390        None => format!("{}{}", col_str, row),
391    }
392}
393
394fn is_large_or_infinite_range(
395    start_row: Option<u32>,
396    start_col: Option<u32>,
397    end_row: Option<u32>,
398    end_col: Option<u32>,
399) -> bool {
400    match (start_row, start_col, end_row, end_col) {
401        (Some(sr), Some(sc), Some(er), Some(ec)) => {
402            let rows = er.saturating_sub(sr) + 1;
403            let cols = ec.saturating_sub(sc) + 1;
404            (rows as usize) * (cols as usize) > RANGE_EXPANSION_LIMIT
405        }
406        _ => true,
407    }
408}
409
410fn range_contains_cell(
411    range: &ReferenceType,
412    query_sheet: Option<&str>,
413    current_sheet: &str,
414    row: u32,
415    col: u32,
416) -> bool {
417    match range {
418        ReferenceType::Range {
419            sheet: range_sheet,
420            start_row,
421            start_col,
422            end_row,
423            end_col,
424            ..
425        } => {
426            let range_sheet_name = range_sheet.as_deref().unwrap_or(current_sheet);
427            let query_sheet_name = query_sheet.unwrap_or(current_sheet);
428            if !range_sheet_name.eq_ignore_ascii_case(query_sheet_name) {
429                return false;
430            }
431            let row_ok = match (start_row, end_row) {
432                (Some(sr), Some(er)) => row >= *sr && row <= *er,
433                (Some(sr), None) => row >= *sr,
434                (None, Some(er)) => row <= *er,
435                (None, None) => true,
436            };
437            let col_ok = match (start_col, end_col) {
438                (Some(sc), Some(ec)) => col >= *sc && col <= *ec,
439                (Some(sc), None) => col >= *sc,
440                (None, Some(ec)) => col <= *ec,
441                (None, None) => true,
442            };
443            row_ok && col_ok
444        }
445        _ => false,
446    }
447}
448
449fn parse_cell_address(address: &str) -> Option<(u32, u32)> {
450    let (_, cell_part) = split_sheet_prefix(address);
451    let cell_part = cell_part.trim_start_matches('$');
452
453    let mut col_str = String::new();
454    let mut row_str = String::new();
455
456    for ch in cell_part.chars() {
457        if ch == '$' {
458            continue;
459        }
460        if ch.is_ascii_alphabetic() && row_str.is_empty() {
461            col_str.push(ch.to_ascii_uppercase());
462        } else if ch.is_ascii_digit() {
463            row_str.push(ch);
464        }
465    }
466
467    if col_str.is_empty() || row_str.is_empty() {
468        return None;
469    }
470
471    let col = column_name_to_number(&col_str)?;
472    let row: u32 = row_str.parse().ok()?;
473    Some((row, col))
474}
475
476fn column_name_to_number(name: &str) -> Option<u32> {
477    let mut result: u32 = 0;
478    for ch in name.chars() {
479        if !ch.is_ascii_alphabetic() {
480            return None;
481        }
482        result = result * 26 + (ch.to_ascii_uppercase() as u32 - 'A' as u32 + 1);
483    }
484    Some(result)
485}
486
487fn split_sheet_prefix(address: &str) -> (Option<&str>, &str) {
488    if let Some(idx) = address.find('!') {
489        let sheet = &address[..idx];
490        let sheet = sheet.trim_start_matches('\'').trim_end_matches('\'');
491        let cell = &address[idx + 1..];
492        (Some(sheet), cell)
493    } else {
494        (None, address)
495    }
496}
497
498struct FormulaGroupAccumulator {
499    canonical: String,
500    addresses: Vec<String>,
501    is_volatile: bool,
502    is_array: bool,
503    is_shared: bool,
504}
505
506fn reference_to_string(reference: &ReferenceType) -> String {
507    reference.to_string()
508}
509
510pub fn normalize_cell_reference(sheet_name: &str, row: u32, col: u32) -> String {
511    format!("{}!{}{}", sheet_name, column_number_to_name(col), row)
512}
513
514fn default_volatility_functions() -> Vec<String> {
515    vec![
516        "NOW",
517        "TODAY",
518        "RAND",
519        "RANDBETWEEN",
520        "OFFSET",
521        "INDIRECT",
522        "INFO",
523        "CELL",
524        "AREAS",
525        "INDEX",
526        "MOD",
527        "ROW",
528        "COLUMN",
529        "ROWS",
530        "COLUMNS",
531        "HYPERLINK",
532    ]
533    .into_iter()
534    .map(|s| s.to_string())
535    .collect()
536}
spreadsheet_kit/analysis/formula.rs

spreadsheet_kit/analysis/
formula.rs
