1use formula_lang::ast::{col_name, col_number, CellRef, Expr, MAX_COL, MAX_ROW};
32use std::string::{String, ToString};
33use std::vec::Vec;
34
35const GRID_W: u64 = MAX_COL as u64;
37
38fn lin(col: u32, row: u32) -> u64 {
42 (u64::from(row) - 1) * GRID_W + u64::from(col) - 1
43}
44
45fn render_lin(l: u64) -> String {
47 let col = u32::try_from(l % GRID_W).unwrap_or(0) + 1;
48 let row = u32::try_from(l / GRID_W).unwrap_or(0) + 1;
49 let mut s = col_name(col);
50 s.push_str(&row.to_string());
51 s
52}
53
54#[derive(Debug, Clone, PartialEq, Eq)]
57pub(crate) struct CrossRef {
58 pub sheet: String,
60 pub rows: (u32, u32),
62 pub cols: (u32, u32),
64}
65
66#[derive(Debug, Clone, PartialEq, Eq)]
68pub(crate) enum Piece {
69 Text(String),
72 Local(String, u64),
75 Qualified(CrossRef),
77}
78
79fn push_range(cs: &[char], i: usize, end: usize, buf: &mut String) {
81 buf.extend(cs.iter().skip(i).take(end.saturating_sub(i)));
82}
83
84fn string_end(cs: &[char], i: usize) -> usize {
88 let mut j = i + 1;
89 while let Some(&c) = cs.get(j) {
90 if c == '"' {
91 if matches!(cs.get(j + 1), Some('"')) {
92 j += 2;
93 } else {
94 return j + 1;
95 }
96 } else {
97 j += 1;
98 }
99 }
100 cs.len()
101}
102
103fn quoted_end(cs: &[char], i: usize) -> usize {
106 let mut j = i + 1;
107 while let Some(&c) = cs.get(j) {
108 if c == '\'' {
109 if matches!(cs.get(j + 1), Some('\'')) {
110 j += 2;
111 } else {
112 return j + 1;
113 }
114 } else {
115 j += 1;
116 }
117 }
118 cs.len()
119}
120
121fn quoted_name(cs: &[char], i: usize) -> Option<(String, usize)> {
124 let mut j = i + 1;
125 let mut name = String::new();
126 while let Some(&c) = cs.get(j) {
127 if c == '\'' {
128 if matches!(cs.get(j + 1), Some('\'')) {
129 name.push('\'');
130 j += 2;
131 } else {
132 return Some((name, j + 1));
133 }
134 } else {
135 name.push(c);
136 j += 1;
137 }
138 }
139 None
140}
141
142fn error_literal_len(cs: &[char], i: usize) -> usize {
145 const CANDIDATES: [&str; 7] = [
146 "#DIV/0!", "#VALUE!", "#NAME?", "#NULL!", "#NUM!", "#REF!", "#N/A",
147 ];
148 let head: String = cs.iter().skip(i).take(CANDIDATES[0].len()).collect();
149 let head = head.to_ascii_uppercase();
150 CANDIDATES
151 .into_iter()
152 .find(|lit| head.starts_with(lit))
153 .map_or(1, str::len)
154}
155
156fn ident_end(cs: &[char], i: usize) -> usize {
159 let mut j = i;
160 while matches!(cs.get(j), Some(c) if c.is_ascii_alphanumeric() || *c == '_' || *c == '.') {
161 j += 1;
162 }
163 j
164}
165
166fn try_single_ref(cs: &[char], i: usize) -> Option<(usize, u32, u32)> {
170 let mut j = i;
171 if matches!(cs.get(j), Some('$')) {
172 j += 1;
173 }
174 let ls = j;
175 while matches!(cs.get(j), Some(c) if c.is_ascii_alphabetic()) {
176 j += 1;
177 }
178 if j == ls {
179 return None;
180 }
181 if j - ls > 3 {
185 return None;
186 }
187 let letters: String = cs.iter().skip(ls).take(j - ls).collect();
188 let col = col_number(&letters)?;
189 if col == 0 || col > MAX_COL {
190 return None;
191 }
192 if matches!(cs.get(j), Some('$')) {
193 j += 1;
194 }
195 let ds = j;
196 while matches!(cs.get(j), Some(c) if c.is_ascii_digit()) {
197 j += 1;
198 }
199 if j == ds {
200 return None;
201 }
202 let digits: String = cs.iter().skip(ds).take(j - ds).collect();
203 let row: u32 = digits.parse().ok()?;
204 if row == 0 || row > MAX_ROW {
205 return None;
206 }
207 if matches!(cs.get(j), Some(c) if c.is_ascii_alphanumeric() || *c == '_' || *c == '.') {
209 return None;
210 }
211 if matches!(cs.get(j), Some('(')) {
213 return None;
214 }
215 Some((j, col, row))
216}
217
218fn try_ref_range(cs: &[char], i: usize) -> Option<(usize, u64)> {
221 let (mut end, col1, row1) = try_single_ref(cs, i)?;
222 let mut far = lin(col1, row1);
223 if matches!(cs.get(end), Some(':')) {
224 if let Some((end2, col2, row2)) = try_single_ref(cs, end + 1) {
225 far = far.max(lin(col2, row2));
226 end = end2;
227 }
228 }
229 Some((end, far))
230}
231
232fn read_target(cs: &[char], i: usize) -> Option<(CrossRef, usize)> {
235 let (after_first, col_a, row_a) = try_single_ref(cs, i)?;
236 let (cols, rows, end) = if matches!(cs.get(after_first), Some(':')) {
237 match try_single_ref(cs, after_first + 1) {
238 Some((after_second, col_b, row_b)) => (
239 (col_a.min(col_b), col_a.max(col_b)),
240 (row_a.min(row_b), row_a.max(row_b)),
241 after_second,
242 ),
243 None => ((col_a, col_a), (row_a, row_a), after_first),
244 }
245 } else {
246 ((col_a, col_a), (row_a, row_a), after_first)
247 };
248 Some((
249 CrossRef {
250 sheet: String::new(),
251 rows,
252 cols,
253 },
254 end,
255 ))
256}
257
258pub(crate) fn walk(src: &str) -> Vec<Piece> {
262 let cs: Vec<char> = src.chars().collect();
263 let mut pieces: Vec<Piece> = Vec::new();
264 let mut buf = String::new();
265 let mut i = 0;
266
267 while let Some(&c) = cs.get(i) {
268 match c {
269 '"' => {
270 let end = string_end(&cs, i);
271 push_range(&cs, i, end, &mut buf);
272 i = end;
273 }
274 '\'' => {
275 let mut handled = false;
276 if let Some((name, after)) = quoted_name(&cs, i) {
277 if matches!(cs.get(after), Some('!')) {
278 if let Some((mut target, end)) = read_target(&cs, after + 1) {
279 target.sheet = name;
280 pieces.push(Piece::Text(core::mem::take(&mut buf)));
281 pieces.push(Piece::Qualified(target));
282 i = end;
283 handled = true;
284 }
285 }
286 }
287 if !handled {
288 let end = quoted_end(&cs, i);
289 push_range(&cs, i, end, &mut buf);
290 i = end;
291 }
292 }
293 '#' => {
294 let len = error_literal_len(&cs, i);
295 push_range(&cs, i, i + len, &mut buf);
296 i += len;
297 }
298 _ if c == '$' || c.is_ascii_alphabetic() => {
299 if let Some((end, far)) = try_ref_range(&cs, i) {
300 if matches!(cs.get(end), Some('!')) {
305 if let Some((mut target, tend)) = read_target(&cs, end + 1) {
306 let mut name: String = cs.iter().skip(i).take(end - i).collect();
307 name.retain(|ch| ch != '$');
308 target.sheet = name;
309 pieces.push(Piece::Text(core::mem::take(&mut buf)));
310 pieces.push(Piece::Qualified(target));
311 i = tend;
312 continue;
313 }
314 }
315 let text: String = cs.iter().skip(i).take(end - i).collect();
316 pieces.push(Piece::Text(core::mem::take(&mut buf)));
317 pieces.push(Piece::Local(text, far));
318 i = end;
319 continue;
320 }
321 let end = ident_end(&cs, i);
322 if end == i {
323 buf.push(c);
324 i += 1;
325 continue;
326 }
327 let run: String = cs.iter().skip(i).take(end - i).collect();
328 if matches!(cs.get(end), Some('!')) {
329 if let Some((mut target, tend)) = read_target(&cs, end + 1) {
330 target.sheet = run;
331 pieces.push(Piece::Text(core::mem::take(&mut buf)));
332 pieces.push(Piece::Qualified(target));
333 i = tend;
334 continue;
335 }
336 }
337 buf.push_str(&run);
338 i = end;
339 }
340 _ => {
341 buf.push(c);
342 i += 1;
343 }
344 }
345 }
346 pieces.push(Piece::Text(buf));
347 pieces
348}
349
350#[derive(Debug, Clone, PartialEq, Eq)]
354pub(crate) struct StubRange {
355 pub start: u64,
357 pub rows: u32,
359 pub cols: u32,
361 pub target: (String, u32, u32),
363}
364
365#[derive(Debug, Clone)]
368pub(crate) struct Prepared {
369 pub expr: Expr,
371 pub volatile: bool,
373 pub stub_base: u64,
376 pub stubs: Vec<StubRange>,
378}
379
380impl Prepared {
381 pub fn resolve_stub(&self, lin: u64) -> Option<(&StubRange, u64)> {
385 let idx = self.stubs.partition_point(|s| s.start <= lin);
386 let s = idx.checked_sub(1).and_then(|i| self.stubs.get(i))?;
387 let off = lin - s.start;
388 if off < (u64::from(s.rows) - 1) * GRID_W + u64::from(s.cols) {
390 Some((s, off))
391 } else {
392 None
393 }
394 }
395
396 #[must_use]
404 pub fn local_registration_text(&self) -> Option<String> {
405 let mut parts: Vec<String> = Vec::new();
406 collect_local(&self.expr, self.stub_base, &mut parts);
407 if parts.is_empty() {
408 None
409 } else {
410 Some(format!("={}", parts.join("+")))
411 }
412 }
413}
414
415fn collect_local(expr: &Expr, stub_base: u64, parts: &mut Vec<String>) {
419 match expr {
420 Expr::CellRef { col, row, .. } => {
421 if lin(*col, *row) < stub_base {
422 parts.push(format!("{}{}", col_name(*col), row));
423 }
424 }
425 Expr::Range { start, end } => {
426 let CellRef {
427 col: c0, row: r0, ..
428 } = *start;
429 let CellRef {
430 col: c1, row: r1, ..
431 } = *end;
432 if lin(c0, r0) < stub_base && lin(c1, r1) < stub_base {
433 parts.push(format!("{}{}:{}{}", col_name(c0), r0, col_name(c1), r1));
434 }
435 }
436 Expr::Unary { expr, .. } => collect_local(expr, stub_base, parts),
437 Expr::Binary { left, right, .. } => {
438 collect_local(left, stub_base, parts);
439 collect_local(right, stub_base, parts);
440 }
441 Expr::Function { args, .. } => {
442 for arg in args {
443 collect_local(arg, stub_base, parts);
444 }
445 }
446 _ => {}
447 }
448}
449
450pub(crate) fn prepare(text: &str) -> Result<Prepared, crate::EngineError> {
461 let pieces = walk(text);
462 let local_max = pieces.iter().fold(0u64, |m, p| match p {
463 Piece::Local(_, far) => m.max(*far),
464 _ => m,
465 });
466
467 let mut rewritten = String::new();
468 let mut next = local_max + 1;
469 let mut stubs: Vec<StubRange> = Vec::new();
470 for p in &pieces {
471 match p {
472 Piece::Text(t) | Piece::Local(t, _) => rewritten.push_str(t),
473 Piece::Qualified(t) => {
474 let rows = t.rows.1 - t.rows.0 + 1;
475 let cols = t.cols.1 - t.cols.0 + 1;
476 let start = next;
477 let span = (u64::from(rows) - 1) * GRID_W + u64::from(cols);
481 let end_lin = start + span - 1;
482 rewritten.push_str(&render_lin(start));
483 if rows > 1 || cols > 1 {
484 rewritten.push(':');
485 rewritten.push_str(&render_lin(end_lin));
486 }
487 stubs.push(StubRange {
488 start,
489 rows,
490 cols,
491 target: (t.sheet.clone(), t.rows.0 - 1, t.cols.0 - 1),
492 });
493 next += span;
494 }
495 }
496 }
497
498 if next > MAX_LIN + 1 {
499 return Err(crate::EngineError::StubSpaceExhausted);
500 }
501 let expr = formula_lang::parse(&rewritten).map_err(crate::EngineError::Formula)?;
502 let volatile = formula_lang::is_volatile(&expr);
503 Ok(Prepared {
504 expr,
505 volatile,
506 stub_base: local_max + 1,
507 stubs,
508 })
509}
510
511const MAX_LIN: u64 = GRID_W * (MAX_ROW as u64) - 1;
513
514#[cfg(test)]
515mod tests {
516 #![allow(
517 clippy::unwrap_used,
518 clippy::expect_used,
519 clippy::panic,
520 clippy::indexing_slicing
521 )]
522
523 use super::*;
524 use std::vec;
525
526 fn qualified_of(text: &str) -> Vec<CrossRef> {
527 walk(text)
528 .into_iter()
529 .filter_map(|p| match p {
530 Piece::Qualified(t) => Some(t),
531 _ => None,
532 })
533 .collect()
534 }
535
536 fn locals_of(text: &str) -> Vec<(String, u64)> {
537 walk(text)
538 .into_iter()
539 .filter_map(|p| match p {
540 Piece::Local(t, far) => Some((t, far)),
541 _ => None,
542 })
543 .collect()
544 }
545
546 fn plain(text: &str) -> String {
547 walk(text)
548 .into_iter()
549 .filter_map(|p| match p {
550 Piece::Text(t) | Piece::Local(t, _) => Some(t),
551 Piece::Qualified(_) => None,
552 })
553 .collect()
554 }
555
556 #[test]
557 fn plain_formulas_pass_through_unchanged() {
558 assert_eq!(plain("=A1+1"), "=A1+1");
559 assert_eq!(plain("= SUM( A1 : B2 ) + $C$3"), "= SUM( A1 : B2 ) + $C$3");
560 assert_eq!(
561 plain("=IF(A1>=2,\"yes\",\"no\")"),
562 "=IF(A1>=2,\"yes\",\"no\")"
563 );
564 assert_eq!(plain("=\"sum in A1?\"&A1"), "=\"sum in A1?\"&A1");
566 assert_eq!(plain("=\"say \"\"hi\"\"\""), "=\"say \"\"hi\"\"\"");
567 }
568
569 #[test]
570 fn error_literals_are_not_qualifiers() {
571 assert_eq!(plain("=IFERROR(A1,#REF!)"), "=IFERROR(A1,#REF!)");
573 assert_eq!(plain("=#DIV/0!+1"), "=#DIV/0!+1");
574 assert_eq!(plain("=ISERROR(#N/A)"), "=ISERROR(#N/A)");
575 }
576
577 #[test]
578 fn function_names_that_look_like_references_are_not_refs() {
579 assert_eq!(locals_of("=LOG10(A1)"), vec![("A1".to_string(), 0)]);
582 assert_eq!(plain("=LOG10(100)"), "=LOG10(100)");
583 assert_eq!(qualified_of("=LOG10(100)"), Vec::<CrossRef>::new());
584 }
585
586 #[test]
587 fn local_refs_record_their_far_corner() {
588 assert_eq!(locals_of("=A1"), vec![("A1".to_string(), 0)]);
589 assert_eq!(locals_of("=B2+1"), vec![("B2".to_string(), 16_385)]);
591 let far = lin(3, 3);
593 assert_eq!(locals_of("=SUM(A1:C3)"), vec![("A1:C3".to_string(), far)]);
594 assert_eq!(locals_of("=$A$1"), vec![("$A$1".to_string(), 0)]);
595 assert_eq!(locals_of("=A1B2"), Vec::new());
597 assert_eq!(locals_of("=ZZZ16385"), Vec::new());
600 }
601
602 #[test]
603 fn qualified_refs_are_found_in_all_spellings() {
604 assert_eq!(
605 qualified_of("=Sheet2!A1+1"),
606 vec![CrossRef {
607 sheet: "Sheet2".to_string(),
608 rows: (1, 1),
609 cols: (1, 1)
610 }]
611 );
612 assert_eq!(qualified_of("=sheet_two!B2:C3")[0].sheet, "sheet_two");
613 assert_eq!(qualified_of("=x.y_z9!A1")[0].sheet, "x.y_z9");
614 assert_eq!(
616 qualified_of("='My Sheet'!$B$2")[0].sheet,
617 "My Sheet".to_string()
618 );
619 assert_eq!(
620 qualified_of("='It''s here'!A1")[0].sheet,
621 "It's here".to_string()
622 );
623 assert_eq!(qualified_of("=A1!B2")[0].sheet, "A1".to_string());
625 let t = &qualified_of("='Q4 Data'!B2:F9")[0];
627 assert_eq!(t.rows, (2, 9));
628 assert_eq!(t.cols, (2, 6));
629 }
630
631 #[test]
632 fn malformed_qualifiers_copy_through_for_the_parser_to_reject() {
633 assert_eq!(plain("='Oops"), "='Oops");
635 assert_eq!(plain("=Sheet2!"), "=Sheet2!");
636 assert_eq!(plain("=Sheet2!1A"), "=Sheet2!1A");
637 }
638
639 #[test]
640 fn prepare_rewrites_qualified_refs_to_in_grid_stubs() {
641 let p = prepare("=Sheet2!A1+B2").expect("parses");
642 assert_eq!(p.stub_base, 16_386);
644 assert_eq!(p.stubs.len(), 1);
645 let s = &p.stubs[0];
646 assert_eq!(s.start, 16_386);
647 assert_eq!(s.target, ("Sheet2".to_string(), 0, 0));
648 assert!(p.local_registration_text().is_some_and(|t| t == "=B2"));
650
651 let q = prepare("='My Sheet'!B2:F9").expect("parses");
652 assert_eq!(q.stubs.len(), 1);
653 let s = &q.stubs[0];
654 assert_eq!(s.rows, 8);
655 assert_eq!(s.cols, 5);
656 assert_eq!(s.target, ("My Sheet".to_string(), 1, 1));
657 assert_eq!(q.local_registration_text(), None);
659 }
660
661 #[test]
662 fn stub_allocation_avoids_every_local_coordinate() {
663 let top = lin(16_384, 1_048_575);
666 let p = prepare("=XFD1048575+Sheet2!A1").expect("parses");
667 assert_eq!(p.stub_base, top + 1);
668 assert_eq!(p.stubs[0].start, top + 1);
669 let s = render_lin(p.stubs[0].start);
670 assert!(formula_lang::parse(&format!("={s}")).is_ok());
671 }
672
673 #[test]
674 fn the_last_grid_cell_leaves_no_stub_room() {
675 let err = prepare("=XFD1048576+Sheet2!A1").expect_err("no stub space");
676 assert!(matches!(err, crate::EngineError::StubSpaceExhausted));
677 assert!(prepare("=XFD1048576+A1").is_ok());
679 }
680
681 #[test]
682 fn resolve_stub_translates_cells_and_ranges() {
683 let p = prepare("=SUM('Data'!A1:B3)+C4").expect("parses");
684 assert_eq!(p.stubs.len(), 1);
685 let start = p.stubs[0].start;
686 let (s, off) = p.resolve_stub(start).expect("in range");
688 assert_eq!(s.target.0, "Data");
689 assert_eq!(off, 0);
690 let (_, off) = p.resolve_stub(start + 1).expect("in range");
692 assert_eq!(off, 1);
693 let (_, off) = p.resolve_stub(start + GRID_W).expect("in range");
695 assert_eq!(off, GRID_W);
696 assert!(p.resolve_stub(start - 1).is_none());
699 let span = (GRID_W) * 2 + 2; assert!(p.resolve_stub(start + span).is_none());
701 let (s, _) = p.resolve_stub(start + 6).expect("inside the stride");
705 assert_eq!(s.target.0, "Data");
706 assert!(p.resolve_stub(p.stub_base - 1).is_none());
707 assert!(p.resolve_stub(0).is_none());
709 }
710
711 #[test]
712 fn mixed_formulas_register_only_their_local_edges() {
713 let p = prepare("=Sheet2!A1+B2+SUM(C1:C9)").expect("parses");
714 let text = p.local_registration_text().expect("has locals");
715 assert!(text.contains("B2"));
717 assert!(text.contains("C1:C9"));
718 assert!(!text.contains('!'));
719 }
720}