use formula_lang::ast::{col_name, col_number, CellRef, Expr, MAX_COL, MAX_ROW};
use std::string::{String, ToString};
use std::vec::Vec;
const GRID_W: u64 = MAX_COL as u64;
fn lin(col: u32, row: u32) -> u64 {
(u64::from(row) - 1) * GRID_W + u64::from(col) - 1
}
fn render_lin(l: u64) -> String {
let col = u32::try_from(l % GRID_W).unwrap_or(0) + 1;
let row = u32::try_from(l / GRID_W).unwrap_or(0) + 1;
let mut s = col_name(col);
s.push_str(&row.to_string());
s
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct CrossRef {
pub sheet: String,
pub rows: (u32, u32),
pub cols: (u32, u32),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum Piece {
Text(String),
Local(String, u64),
Qualified(CrossRef),
}
fn push_range(cs: &[char], i: usize, end: usize, buf: &mut String) {
buf.extend(cs.iter().skip(i).take(end.saturating_sub(i)));
}
fn string_end(cs: &[char], i: usize) -> usize {
let mut j = i + 1;
while let Some(&c) = cs.get(j) {
if c == '"' {
if matches!(cs.get(j + 1), Some('"')) {
j += 2;
} else {
return j + 1;
}
} else {
j += 1;
}
}
cs.len()
}
fn quoted_end(cs: &[char], i: usize) -> usize {
let mut j = i + 1;
while let Some(&c) = cs.get(j) {
if c == '\'' {
if matches!(cs.get(j + 1), Some('\'')) {
j += 2;
} else {
return j + 1;
}
} else {
j += 1;
}
}
cs.len()
}
fn quoted_name(cs: &[char], i: usize) -> Option<(String, usize)> {
let mut j = i + 1;
let mut name = String::new();
while let Some(&c) = cs.get(j) {
if c == '\'' {
if matches!(cs.get(j + 1), Some('\'')) {
name.push('\'');
j += 2;
} else {
return Some((name, j + 1));
}
} else {
name.push(c);
j += 1;
}
}
None
}
fn error_literal_len(cs: &[char], i: usize) -> usize {
const CANDIDATES: [&str; 7] = [
"#DIV/0!", "#VALUE!", "#NAME?", "#NULL!", "#NUM!", "#REF!", "#N/A",
];
let head: String = cs.iter().skip(i).take(CANDIDATES[0].len()).collect();
let head = head.to_ascii_uppercase();
CANDIDATES
.into_iter()
.find(|lit| head.starts_with(lit))
.map_or(1, str::len)
}
fn ident_end(cs: &[char], i: usize) -> usize {
let mut j = i;
while matches!(cs.get(j), Some(c) if c.is_ascii_alphanumeric() || *c == '_' || *c == '.') {
j += 1;
}
j
}
fn try_single_ref(cs: &[char], i: usize) -> Option<(usize, u32, u32)> {
let mut j = i;
if matches!(cs.get(j), Some('$')) {
j += 1;
}
let ls = j;
while matches!(cs.get(j), Some(c) if c.is_ascii_alphabetic()) {
j += 1;
}
if j == ls {
return None;
}
if j - ls > 3 {
return None;
}
let letters: String = cs.iter().skip(ls).take(j - ls).collect();
let col = col_number(&letters)?;
if col == 0 || col > MAX_COL {
return None;
}
if matches!(cs.get(j), Some('$')) {
j += 1;
}
let ds = j;
while matches!(cs.get(j), Some(c) if c.is_ascii_digit()) {
j += 1;
}
if j == ds {
return None;
}
let digits: String = cs.iter().skip(ds).take(j - ds).collect();
let row: u32 = digits.parse().ok()?;
if row == 0 || row > MAX_ROW {
return None;
}
if matches!(cs.get(j), Some(c) if c.is_ascii_alphanumeric() || *c == '_' || *c == '.') {
return None;
}
if matches!(cs.get(j), Some('(')) {
return None;
}
Some((j, col, row))
}
fn try_ref_range(cs: &[char], i: usize) -> Option<(usize, u64)> {
let (mut end, col1, row1) = try_single_ref(cs, i)?;
let mut far = lin(col1, row1);
if matches!(cs.get(end), Some(':')) {
if let Some((end2, col2, row2)) = try_single_ref(cs, end + 1) {
far = far.max(lin(col2, row2));
end = end2;
}
}
Some((end, far))
}
fn read_target(cs: &[char], i: usize) -> Option<(CrossRef, usize)> {
let (after_first, col_a, row_a) = try_single_ref(cs, i)?;
let (cols, rows, end) = if matches!(cs.get(after_first), Some(':')) {
match try_single_ref(cs, after_first + 1) {
Some((after_second, col_b, row_b)) => (
(col_a.min(col_b), col_a.max(col_b)),
(row_a.min(row_b), row_a.max(row_b)),
after_second,
),
None => ((col_a, col_a), (row_a, row_a), after_first),
}
} else {
((col_a, col_a), (row_a, row_a), after_first)
};
Some((
CrossRef {
sheet: String::new(),
rows,
cols,
},
end,
))
}
pub(crate) fn walk(src: &str) -> Vec<Piece> {
let cs: Vec<char> = src.chars().collect();
let mut pieces: Vec<Piece> = Vec::new();
let mut buf = String::new();
let mut i = 0;
while let Some(&c) = cs.get(i) {
match c {
'"' => {
let end = string_end(&cs, i);
push_range(&cs, i, end, &mut buf);
i = end;
}
'\'' => {
let mut handled = false;
if let Some((name, after)) = quoted_name(&cs, i) {
if matches!(cs.get(after), Some('!')) {
if let Some((mut target, end)) = read_target(&cs, after + 1) {
target.sheet = name;
pieces.push(Piece::Text(core::mem::take(&mut buf)));
pieces.push(Piece::Qualified(target));
i = end;
handled = true;
}
}
}
if !handled {
let end = quoted_end(&cs, i);
push_range(&cs, i, end, &mut buf);
i = end;
}
}
'#' => {
let len = error_literal_len(&cs, i);
push_range(&cs, i, i + len, &mut buf);
i += len;
}
_ if c == '$' || c.is_ascii_alphabetic() => {
if let Some((end, far)) = try_ref_range(&cs, i) {
if matches!(cs.get(end), Some('!')) {
if let Some((mut target, tend)) = read_target(&cs, end + 1) {
let mut name: String = cs.iter().skip(i).take(end - i).collect();
name.retain(|ch| ch != '$');
target.sheet = name;
pieces.push(Piece::Text(core::mem::take(&mut buf)));
pieces.push(Piece::Qualified(target));
i = tend;
continue;
}
}
let text: String = cs.iter().skip(i).take(end - i).collect();
pieces.push(Piece::Text(core::mem::take(&mut buf)));
pieces.push(Piece::Local(text, far));
i = end;
continue;
}
let end = ident_end(&cs, i);
if end == i {
buf.push(c);
i += 1;
continue;
}
let run: String = cs.iter().skip(i).take(end - i).collect();
if matches!(cs.get(end), Some('!')) {
if let Some((mut target, tend)) = read_target(&cs, end + 1) {
target.sheet = run;
pieces.push(Piece::Text(core::mem::take(&mut buf)));
pieces.push(Piece::Qualified(target));
i = tend;
continue;
}
}
buf.push_str(&run);
i = end;
}
_ => {
buf.push(c);
i += 1;
}
}
}
pieces.push(Piece::Text(buf));
pieces
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct StubRange {
pub start: u64,
pub rows: u32,
pub cols: u32,
pub target: (String, u32, u32),
}
#[derive(Debug, Clone)]
pub(crate) struct Prepared {
pub expr: Expr,
pub volatile: bool,
pub stub_base: u64,
pub stubs: Vec<StubRange>,
}
impl Prepared {
pub fn resolve_stub(&self, lin: u64) -> Option<(&StubRange, u64)> {
let idx = self.stubs.partition_point(|s| s.start <= lin);
let s = idx.checked_sub(1).and_then(|i| self.stubs.get(i))?;
let off = lin - s.start;
if off < (u64::from(s.rows) - 1) * GRID_W + u64::from(s.cols) {
Some((s, off))
} else {
None
}
}
#[must_use]
pub fn local_registration_text(&self) -> Option<String> {
let mut parts: Vec<String> = Vec::new();
collect_local(&self.expr, self.stub_base, &mut parts);
if parts.is_empty() {
None
} else {
Some(format!("={}", parts.join("+")))
}
}
}
fn collect_local(expr: &Expr, stub_base: u64, parts: &mut Vec<String>) {
match expr {
Expr::CellRef { col, row, .. } => {
if lin(*col, *row) < stub_base {
parts.push(format!("{}{}", col_name(*col), row));
}
}
Expr::Range { start, end } => {
let CellRef {
col: c0, row: r0, ..
} = *start;
let CellRef {
col: c1, row: r1, ..
} = *end;
if lin(c0, r0) < stub_base && lin(c1, r1) < stub_base {
parts.push(format!("{}{}:{}{}", col_name(c0), r0, col_name(c1), r1));
}
}
Expr::Unary { expr, .. } => collect_local(expr, stub_base, parts),
Expr::Binary { left, right, .. } => {
collect_local(left, stub_base, parts);
collect_local(right, stub_base, parts);
}
Expr::Function { args, .. } => {
for arg in args {
collect_local(arg, stub_base, parts);
}
}
_ => {}
}
}
pub(crate) fn prepare(text: &str) -> Result<Prepared, crate::EngineError> {
let pieces = walk(text);
let local_max = pieces.iter().fold(0u64, |m, p| match p {
Piece::Local(_, far) => m.max(*far),
_ => m,
});
let mut rewritten = String::new();
let mut next = local_max + 1;
let mut stubs: Vec<StubRange> = Vec::new();
for p in &pieces {
match p {
Piece::Text(t) | Piece::Local(t, _) => rewritten.push_str(t),
Piece::Qualified(t) => {
let rows = t.rows.1 - t.rows.0 + 1;
let cols = t.cols.1 - t.cols.0 + 1;
let start = next;
let span = (u64::from(rows) - 1) * GRID_W + u64::from(cols);
let end_lin = start + span - 1;
rewritten.push_str(&render_lin(start));
if rows > 1 || cols > 1 {
rewritten.push(':');
rewritten.push_str(&render_lin(end_lin));
}
stubs.push(StubRange {
start,
rows,
cols,
target: (t.sheet.clone(), t.rows.0 - 1, t.cols.0 - 1),
});
next += span;
}
}
}
if next > MAX_LIN + 1 {
return Err(crate::EngineError::StubSpaceExhausted);
}
let expr = formula_lang::parse(&rewritten).map_err(crate::EngineError::Formula)?;
let volatile = formula_lang::is_volatile(&expr);
Ok(Prepared {
expr,
volatile,
stub_base: local_max + 1,
stubs,
})
}
const MAX_LIN: u64 = GRID_W * (MAX_ROW as u64) - 1;
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::expect_used,
clippy::panic,
clippy::indexing_slicing
)]
use super::*;
use std::vec;
fn qualified_of(text: &str) -> Vec<CrossRef> {
walk(text)
.into_iter()
.filter_map(|p| match p {
Piece::Qualified(t) => Some(t),
_ => None,
})
.collect()
}
fn locals_of(text: &str) -> Vec<(String, u64)> {
walk(text)
.into_iter()
.filter_map(|p| match p {
Piece::Local(t, far) => Some((t, far)),
_ => None,
})
.collect()
}
fn plain(text: &str) -> String {
walk(text)
.into_iter()
.filter_map(|p| match p {
Piece::Text(t) | Piece::Local(t, _) => Some(t),
Piece::Qualified(_) => None,
})
.collect()
}
#[test]
fn plain_formulas_pass_through_unchanged() {
assert_eq!(plain("=A1+1"), "=A1+1");
assert_eq!(plain("= SUM( A1 : B2 ) + $C$3"), "= SUM( A1 : B2 ) + $C$3");
assert_eq!(
plain("=IF(A1>=2,\"yes\",\"no\")"),
"=IF(A1>=2,\"yes\",\"no\")"
);
assert_eq!(plain("=\"sum in A1?\"&A1"), "=\"sum in A1?\"&A1");
assert_eq!(plain("=\"say \"\"hi\"\"\""), "=\"say \"\"hi\"\"\"");
}
#[test]
fn error_literals_are_not_qualifiers() {
assert_eq!(plain("=IFERROR(A1,#REF!)"), "=IFERROR(A1,#REF!)");
assert_eq!(plain("=#DIV/0!+1"), "=#DIV/0!+1");
assert_eq!(plain("=ISERROR(#N/A)"), "=ISERROR(#N/A)");
}
#[test]
fn function_names_that_look_like_references_are_not_refs() {
assert_eq!(locals_of("=LOG10(A1)"), vec![("A1".to_string(), 0)]);
assert_eq!(plain("=LOG10(100)"), "=LOG10(100)");
assert_eq!(qualified_of("=LOG10(100)"), Vec::<CrossRef>::new());
}
#[test]
fn local_refs_record_their_far_corner() {
assert_eq!(locals_of("=A1"), vec![("A1".to_string(), 0)]);
assert_eq!(locals_of("=B2+1"), vec![("B2".to_string(), 16_385)]);
let far = lin(3, 3);
assert_eq!(locals_of("=SUM(A1:C3)"), vec![("A1:C3".to_string(), far)]);
assert_eq!(locals_of("=$A$1"), vec![("$A$1".to_string(), 0)]);
assert_eq!(locals_of("=A1B2"), Vec::new());
assert_eq!(locals_of("=ZZZ16385"), Vec::new());
}
#[test]
fn qualified_refs_are_found_in_all_spellings() {
assert_eq!(
qualified_of("=Sheet2!A1+1"),
vec![CrossRef {
sheet: "Sheet2".to_string(),
rows: (1, 1),
cols: (1, 1)
}]
);
assert_eq!(qualified_of("=sheet_two!B2:C3")[0].sheet, "sheet_two");
assert_eq!(qualified_of("=x.y_z9!A1")[0].sheet, "x.y_z9");
assert_eq!(
qualified_of("='My Sheet'!$B$2")[0].sheet,
"My Sheet".to_string()
);
assert_eq!(
qualified_of("='It''s here'!A1")[0].sheet,
"It's here".to_string()
);
assert_eq!(qualified_of("=A1!B2")[0].sheet, "A1".to_string());
let t = &qualified_of("='Q4 Data'!B2:F9")[0];
assert_eq!(t.rows, (2, 9));
assert_eq!(t.cols, (2, 6));
}
#[test]
fn malformed_qualifiers_copy_through_for_the_parser_to_reject() {
assert_eq!(plain("='Oops"), "='Oops");
assert_eq!(plain("=Sheet2!"), "=Sheet2!");
assert_eq!(plain("=Sheet2!1A"), "=Sheet2!1A");
}
#[test]
fn prepare_rewrites_qualified_refs_to_in_grid_stubs() {
let p = prepare("=Sheet2!A1+B2").expect("parses");
assert_eq!(p.stub_base, 16_386);
assert_eq!(p.stubs.len(), 1);
let s = &p.stubs[0];
assert_eq!(s.start, 16_386);
assert_eq!(s.target, ("Sheet2".to_string(), 0, 0));
assert!(p.local_registration_text().is_some_and(|t| t == "=B2"));
let q = prepare("='My Sheet'!B2:F9").expect("parses");
assert_eq!(q.stubs.len(), 1);
let s = &q.stubs[0];
assert_eq!(s.rows, 8);
assert_eq!(s.cols, 5);
assert_eq!(s.target, ("My Sheet".to_string(), 1, 1));
assert_eq!(q.local_registration_text(), None);
}
#[test]
fn stub_allocation_avoids_every_local_coordinate() {
let top = lin(16_384, 1_048_575);
let p = prepare("=XFD1048575+Sheet2!A1").expect("parses");
assert_eq!(p.stub_base, top + 1);
assert_eq!(p.stubs[0].start, top + 1);
let s = render_lin(p.stubs[0].start);
assert!(formula_lang::parse(&format!("={s}")).is_ok());
}
#[test]
fn the_last_grid_cell_leaves_no_stub_room() {
let err = prepare("=XFD1048576+Sheet2!A1").expect_err("no stub space");
assert!(matches!(err, crate::EngineError::StubSpaceExhausted));
assert!(prepare("=XFD1048576+A1").is_ok());
}
#[test]
fn resolve_stub_translates_cells_and_ranges() {
let p = prepare("=SUM('Data'!A1:B3)+C4").expect("parses");
assert_eq!(p.stubs.len(), 1);
let start = p.stubs[0].start;
let (s, off) = p.resolve_stub(start).expect("in range");
assert_eq!(s.target.0, "Data");
assert_eq!(off, 0);
let (_, off) = p.resolve_stub(start + 1).expect("in range");
assert_eq!(off, 1);
let (_, off) = p.resolve_stub(start + GRID_W).expect("in range");
assert_eq!(off, GRID_W);
assert!(p.resolve_stub(start - 1).is_none());
let span = (GRID_W) * 2 + 2; assert!(p.resolve_stub(start + span).is_none());
let (s, _) = p.resolve_stub(start + 6).expect("inside the stride");
assert_eq!(s.target.0, "Data");
assert!(p.resolve_stub(p.stub_base - 1).is_none());
assert!(p.resolve_stub(0).is_none());
}
#[test]
fn mixed_formulas_register_only_their_local_edges() {
let p = prepare("=Sheet2!A1+B2+SUM(C1:C9)").expect("parses");
let text = p.local_registration_text().expect("has locals");
assert!(text.contains("B2"));
assert!(text.contains("C1:C9"));
assert!(!text.contains('!'));
}
}