use crate::error::GraphError;
use alloc::string::String;
use alloc::vec::Vec;
pub const RANGE_CELL_CAP: u64 = 65_536;
pub fn extract_refs(formula: &str) -> Result<Vec<(u32, u32)>, GraphError> {
let body = formula.trim();
let body = body.strip_prefix('=').unwrap_or(body).trim();
if body.is_empty() {
return Err(GraphError::EmptyFormula);
}
let bytes = body.as_bytes();
let mut refs = Vec::new();
let mut i = 0usize;
while let Some(&byte) = bytes.get(i) {
match byte {
b'"' => {
let open = i;
i += 1;
loop {
match bytes.get(i) {
None => return Err(GraphError::UnterminatedString { position: open }),
Some(b'"') => {
if bytes.get(i + 1) == Some(&b'"') {
i += 2; } else {
i += 1; break;
}
}
Some(_) => i += 1,
}
}
}
b'\'' => {
let open = i;
match skip_quoted_sheet(body, i) {
None => return Err(GraphError::UnterminatedQuote { position: open }),
Some(next) => {
if bytes.get(next) == Some(&b'!') {
i = parse_qualified_ref(body, next + 1, &mut refs)?;
} else {
i = next;
}
}
}
}
b'$' | b'A'..=b'Z' | b'a'..=b'z' => {
if i > 0 && bytes.get(i - 1).copied().is_some_and(is_identifier_byte) {
i += 1;
continue;
}
i = scan_identifier(body, i, &mut refs)?;
}
_ => i += 1,
}
}
refs.sort_unstable();
refs.dedup();
Ok(refs)
}
fn is_identifier_byte(b: u8) -> bool {
b.is_ascii_alphanumeric() || b == b'_' || b == b'.' || b == b'$'
}
fn skip_quoted_sheet(s: &str, start: usize) -> Option<usize> {
let bytes = s.as_bytes();
let mut i = start + 1;
loop {
match bytes.get(i) {
None => return None,
Some(b'\'') => {
if bytes.get(i + 1) == Some(&b'\'') {
i += 2; } else {
return Some(i + 1);
}
}
Some(_) => i += 1,
}
}
}
fn scan_identifier(s: &str, start: usize, refs: &mut Vec<(u32, u32)>) -> Result<usize, GraphError> {
let bytes = s.as_bytes();
let i = start;
let mut j = i;
while matches!(
bytes.get(j),
Some(&b) if b.is_ascii_alphanumeric() || b == b'_' || b == b'.'
) {
j += 1;
}
if j > i && bytes.get(j) == Some(&b'!') {
return parse_qualified_ref(s, j + 1, refs);
}
match parse_a1(s, i)? {
Some((coord, after)) => {
if is_function_call(s, after) || bytes.get(after) == Some(&b'!') {
return Ok(after);
}
refs.push(coord);
Ok(parse_range_tail(s, after, coord, refs)?)
}
None => Ok(i + 1), }
}
fn parse_qualified_ref(s: &str, i: usize, refs: &mut Vec<(u32, u32)>) -> Result<usize, GraphError> {
let bytes = s.as_bytes();
match bytes.get(i) {
Some(&b) if b == b'$' || b.is_ascii_alphabetic() => match parse_a1(s, i)? {
Some((coord, after)) => {
if is_function_call(s, after) {
return Err(GraphError::InvalidReference {
position: i,
text: snippet(s, i),
});
}
refs.push(coord);
Ok(parse_range_tail(s, after, coord, refs)?)
}
None => Err(GraphError::InvalidReference {
position: i,
text: snippet(s, i),
}),
},
_ => Err(GraphError::InvalidReference {
position: i,
text: snippet(s, i),
}),
}
}
fn is_function_call(s: &str, after: usize) -> bool {
s.as_bytes().get(after) == Some(&b'(')
}
fn parse_range_tail(
s: &str,
after: usize,
first: (u32, u32),
refs: &mut Vec<(u32, u32)>,
) -> Result<usize, GraphError> {
let bytes = s.as_bytes();
let mut i = after;
while matches!(bytes.get(i), Some(b' ' | b'\t')) {
i += 1;
}
if bytes.get(i) != Some(&b':') {
return Ok(after);
}
i += 1;
while matches!(bytes.get(i), Some(b' ' | b'\t')) {
i += 1;
}
match bytes.get(i) {
Some(&b) if b == b'$' || b.is_ascii_alphabetic() => match parse_a1(s, i)? {
Some((second, end)) => {
expand_range(first, second, refs)?;
Ok(end)
}
None => Ok(after), },
_ => Ok(after),
}
}
fn expand_range(
a: (u32, u32),
b: (u32, u32),
refs: &mut Vec<(u32, u32)>,
) -> Result<(), GraphError> {
let (r0, r1) = (a.0.min(b.0), a.0.max(b.0));
let (c0, c1) = (a.1.min(b.1), a.1.max(b.1));
let cells = u64::from(r1 - r0 + 1) * u64::from(c1 - c0 + 1);
if cells > RANGE_CELL_CAP {
return Err(GraphError::RangeTooLarge {
start: (r0, c0),
end: (r1, c1),
cells,
});
}
let mut r = r0;
while r <= r1 {
let mut c = c0;
while c <= c1 {
refs.push((r, c));
c += 1;
}
r += 1;
}
Ok(())
}
type A1Match = ((u32, u32), usize);
fn parse_a1(s: &str, start: usize) -> Result<Option<A1Match>, GraphError> {
let bytes = s.as_bytes();
let mut i = start;
if bytes.get(i) == Some(&b'$') {
i += 1;
}
let col_start = i;
while matches!(bytes.get(i), Some(&b) if b.is_ascii_alphabetic()) {
i += 1;
}
if i == col_start {
return Ok(None); }
let col_letters = s.get(col_start..i).unwrap_or_default();
if bytes.get(i) == Some(&b'$') {
i += 1;
}
let row_start = i;
while matches!(bytes.get(i), Some(&b) if b.is_ascii_digit()) {
i += 1;
}
if i == row_start {
return Ok(None); }
let row_digits = s.get(row_start..i).unwrap_or_default();
if matches!(bytes.get(i), Some(&b) if is_identifier_byte(b)) {
return Ok(None);
}
let col = parse_column(col_letters, col_start)?;
let row = parse_row(row_digits, row_start)?;
Ok(Some(((row, col), i)))
}
fn parse_column(letters: &str, position: usize) -> Result<u32, GraphError> {
if letters.is_empty() {
return Err(GraphError::InvalidReference {
position,
text: alloc::string::String::from(letters),
});
}
let mut col: u64 = 0;
for b in letters.bytes() {
col = col
.checked_mul(26)
.and_then(|c| c.checked_add(u64::from(b.to_ascii_uppercase() - b'A' + 1)))
.ok_or(GraphError::ColumnOverflow {
position,
text: alloc::string::String::from(letters),
})?;
}
let zero_based = col - 1; u32::try_from(zero_based).map_err(|_| GraphError::ColumnOverflow {
position,
text: alloc::string::String::from(letters),
})
}
fn parse_row(digits: &str, position: usize) -> Result<u32, GraphError> {
let mut row: u64 = 0;
for b in digits.bytes() {
row = row
.checked_mul(10)
.and_then(|r| r.checked_add(u64::from(b - b'0')))
.ok_or(GraphError::RowOverflow {
position,
text: alloc::string::String::from(digits),
})?;
}
if row == 0 {
return Ok(0); }
u32::try_from(row - 1).map_err(|_| GraphError::RowOverflow {
position,
text: alloc::string::String::from(digits),
})
}
fn snippet(s: &str, from: usize) -> String {
let end = s.len().min(from + 32);
match s.get(from..end) {
Some(text) => String::from(text),
None => String::from("…"),
}
}
#[must_use]
pub fn index_to_column(mut index: u32) -> String {
let mut digits: Vec<u8> = Vec::with_capacity(7);
loop {
digits.push(b'A' + (index % 26) as u8);
index /= 26;
if index == 0 {
break;
}
index -= 1;
}
digits.reverse();
digits.into_iter().map(|b| b as char).collect()
}
pub fn column_to_index(letters: &str) -> Result<u32, GraphError> {
if !letters.bytes().all(|b| b.is_ascii_alphabetic()) {
return Err(GraphError::InvalidReference {
position: 0,
text: alloc::string::String::from(letters),
});
}
parse_column(letters, 0)
}
#[must_use]
pub fn cell_name(coord: (u32, u32)) -> String {
let mut name = index_to_column(coord.1);
name.push_str(alloc::format!("{}", coord.0 + 1).as_str());
name
}
pub fn parse_cell_name(name: &str) -> Result<(u32, u32), GraphError> {
let trimmed = name.trim();
match parse_a1(trimmed, 0)? {
Some((coord, after)) if after == trimmed.len() => Ok(coord),
_ => Err(GraphError::InvalidReference {
position: 0,
text: alloc::string::String::from(name),
}),
}
}
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::expect_used,
clippy::panic,
clippy::indexing_slicing
)]
use super::{
cell_name, column_to_index, extract_refs, index_to_column, parse_cell_name, RANGE_CELL_CAP,
};
use crate::error::GraphError;
use alloc::{format, string::String, vec, vec::Vec};
fn refs(formula: &str) -> Vec<(u32, u32)> {
extract_refs(formula).unwrap_or_else(|e| panic!("test formula {formula:?} failed: {e}"))
}
#[test]
fn plain_relative_and_absolute_forms() {
assert_eq!(refs("=A1"), vec![(0, 0)]);
assert_eq!(refs("=$A$1"), vec![(0, 0)]);
assert_eq!(refs("=$A1"), vec![(0, 0)]);
assert_eq!(refs("=A$1"), vec![(0, 0)]);
assert_eq!(refs("B2"), vec![(1, 1)]);
assert_eq!(refs("=a1+b2"), vec![(0, 0), (1, 1)]);
assert_eq!(refs(" =C3 "), vec![(2, 2)]);
}
#[test]
fn functions_strings_and_numbers_are_not_references() {
assert_eq!(refs("=LOG10(A1)"), vec![(0, 0)]); assert_eq!(
refs("=SUM(A1:B2)+MAX(C1,C2)"),
vec![(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]
);
assert_eq!(refs("=\"A1 is quoted\"&A2"), vec![(1, 0)]);
assert_eq!(refs("=\"say \"\"A1\"\" ok\""), Vec::<(u32, u32)>::new());
assert_eq!(refs("=1.5E3+0.5"), Vec::<(u32, u32)>::new()); assert_eq!(refs("=IF(A1>3,TRUE,FALSE)"), vec![(0, 0)]); assert_eq!(refs("=1A+2B"), Vec::<(u32, u32)>::new()); }
#[test]
fn ranges_expand_per_cell_and_normalize() {
assert_eq!(refs("=A1:B2"), vec![(0, 0), (0, 1), (1, 0), (1, 1)]);
assert_eq!(refs("=B2:A1"), vec![(0, 0), (0, 1), (1, 0), (1, 1)]); assert_eq!(refs("=$B$2 : $C$3"), vec![(1, 1), (1, 2), (2, 1), (2, 2)]);
assert_eq!(
refs("=SUM($A$1:$B$2, C3)"),
vec![(0, 0), (0, 1), (1, 0), (1, 1), (2, 2)]
);
}
#[test]
fn sheet_qualifiers_parse_including_quoted_names() {
assert_eq!(refs("=Sheet2!B3"), vec![(2, 1)]);
assert_eq!(refs("='My Sheet'!$B$2"), vec![(1, 1)]);
assert_eq!(refs("='It''s'!A1:A2"), vec![(0, 0), (1, 0)]); assert_eq!(
refs("=SUM(Sheet2!A1:B2)"),
vec![(0, 0), (0, 1), (1, 0), (1, 1)]
);
assert_eq!(refs("=Sheet1!A1+1"), vec![(0, 0)]);
}
#[test]
fn error_cases() {
assert_eq!(extract_refs(""), Err(GraphError::EmptyFormula));
assert_eq!(extract_refs(" "), Err(GraphError::EmptyFormula));
assert_eq!(extract_refs("="), Err(GraphError::EmptyFormula));
assert_eq!(
extract_refs("=\"abc"),
Err(GraphError::UnterminatedString { position: 0 })
);
assert_eq!(
extract_refs("='Sheet!A1"),
Err(GraphError::UnterminatedQuote { position: 0 })
);
assert_eq!(
extract_refs("=Sheet1!"),
Err(GraphError::InvalidReference {
position: 7,
text: String::new()
})
);
assert_eq!(
extract_refs("=Sheet1!1A"),
Err(GraphError::InvalidReference {
position: 7,
text: String::from("1A")
})
);
assert_eq!(
extract_refs("=Sheet1!Q+1"),
Err(GraphError::InvalidReference {
position: 7,
text: String::from("Q+1")
})
);
}
#[test]
fn coordinate_overflow_is_typed() {
let wide = format!("={}1", "A".repeat(40));
assert!(matches!(
extract_refs(&wide),
Err(GraphError::ColumnOverflow { position: 0, .. })
));
let tall = format!("=A{}", u64::from(u32::MAX) + 2);
assert!(matches!(
extract_refs(&tall),
Err(GraphError::RowOverflow { position: 1, .. })
));
}
#[test]
fn ranges_above_the_cap_are_rejected() {
assert_eq!(
extract_refs("=A1:B1048576"),
Err(GraphError::RangeTooLarge {
start: (0, 0),
end: (1_048_575, 1),
cells: 2_097_152,
})
);
let under_cap =
extract_refs("=A1:B4096").unwrap_or_else(|e| panic!("sub-cap range failed: {e}"));
assert_eq!(under_cap.len(), 8192);
assert_eq!(
extract_refs("=A1:IV256").map(|r| r.len() as u64),
Ok(RANGE_CELL_CAP)
);
}
#[test]
fn a1_notation_conversion_round_trips() {
assert_eq!(index_to_column(0), "A");
assert_eq!(index_to_column(25), "Z");
assert_eq!(index_to_column(26), "AA");
assert_eq!(index_to_column(27), "AB");
assert_eq!(index_to_column(701), "ZZ");
assert_eq!(index_to_column(702), "AAA");
assert_eq!(column_to_index("A"), Ok(0));
assert_eq!(column_to_index("ZZ"), Ok(701));
assert_eq!(column_to_index("aaa"), Ok(702)); assert!(column_to_index("A1").is_err());
assert!(column_to_index("").is_err());
for col in [0u32, 1, 25, 26, 700, 16_383, 100_000] {
assert_eq!(column_to_index(&index_to_column(col)), Ok(col), "col {col}");
}
assert_eq!(cell_name((0, 0)), "A1");
assert_eq!(cell_name((1_048_575, 16_383)), "XFD1048576");
assert_eq!(parse_cell_name("XFD1048576"), Ok((1_048_575, 16_383)));
assert_eq!(parse_cell_name(" b3 "), Ok((2, 1)));
assert!(parse_cell_name("3B").is_err());
assert!(parse_cell_name("A1B2").is_err());
assert!(parse_cell_name("$A$1").is_ok()); }
#[test]
fn formula_text_needs_not_start_with_equals() {
assert_eq!(refs("A1+A2"), vec![(0, 0), (1, 0)]);
assert_eq!(extract_refs("="), Err(GraphError::EmptyFormula));
}
}