use std::collections::{BTreeMap, BTreeSet, VecDeque};
use crate::cell::cell::{CellValue, DataType};
use crate::cell::utils::{column_index_from_string, coordinate_from_string, get_column_letter};
use crate::exceptions::{Error, Result};
use crate::worksheet::Worksheet;
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct References {
pub cells: BTreeSet<String>,
pub cross_sheet: BTreeSet<(String, String)>,
pub named: BTreeSet<String>,
}
impl References {
pub fn is_empty(&self) -> bool {
self.cells.is_empty() && self.cross_sheet.is_empty() && self.named.is_empty()
}
pub fn absorb(&mut self, other: References) {
self.cells.extend(other.cells);
self.cross_sheet.extend(other.cross_sheet);
self.named.extend(other.named);
}
}
pub fn parse_references(expression: &str) -> References {
let mut found = References::default();
let text = expression.strip_prefix('=').unwrap_or(expression);
let bytes = text.as_bytes();
let mut i = 0usize;
while i < bytes.len() {
let ch = bytes[i] as char;
if ch == '"' {
i = skip_quoted(text, i, '"');
continue;
}
if ch == '\'' {
let end = skip_quoted(text, i, '\'');
if bytes.get(end) == Some(&b'!') {
if let Some((sheet, range)) = read_sheet_ref(text, i + 1, end) {
let consumed = range.len();
found.cross_sheet.insert((sheet, range));
i = end + 1 + consumed;
continue;
}
}
i = end;
continue;
}
if !(ch.is_ascii_alphabetic() || ch == '$') {
i += 1;
continue;
}
let (text_ref, len) = read_token(text, i);
let after = i + len;
if is_function_call(text, after) {
i = after;
continue;
}
if let Some(reference) = as_coordinate(text_ref) {
if let Some(range) = read_a1_range(text, i) {
if range.contains(':') {
expand_range(&reference, &range, &mut found.cells);
i += range.len();
continue;
}
}
found.cells.insert(reference);
i = after;
continue;
}
if is_keyword(text_ref) {
i = after;
continue;
}
if bytes.get(after) == Some(&b'!') {
if let Some(range) = read_a1_range(text, after + 1) {
let consumed = range.len();
found.cross_sheet.insert((text_ref.to_string(), range));
i = after + 1 + consumed;
continue;
}
}
found.named.insert(text_ref.to_string());
i = after;
}
found
}
fn read_token(text: &str, at: usize) -> (&str, usize) {
let bytes = text.as_bytes();
let mut end = at;
while end < bytes.len() {
let ch = bytes[end] as char;
if ch.is_ascii_alphanumeric() || ch == '$' {
end += 1;
continue;
}
break;
}
(&text[at..end], end - at)
}
fn as_coordinate(run: &str) -> Option<String> {
let letters: String = run
.chars()
.take_while(|c| c.is_ascii_alphabetic() || *c == '$')
.collect();
let digits: &str = &run[letters.len()..];
let letters = letters.trim_matches('$');
let digits = digits.trim_matches('$');
if letters.is_empty()
|| digits.is_empty()
|| !letters.chars().all(|c| c.is_ascii_alphabetic())
|| !digits.chars().all(|c| c.is_ascii_digit())
{
return None;
}
if digits.trim_start_matches('0').is_empty() {
return None;
}
Some(format!("{letters}{digits}"))
}
fn is_keyword(run: &str) -> bool {
matches!(run.to_ascii_uppercase().as_str(), "TRUE" | "FALSE")
}
fn is_function_call(text: &str, at: usize) -> bool {
text[at..].trim_start().starts_with('(')
}
fn strip_dollars(run: &str) -> String {
run.chars().filter(|c| *c != '$').collect()
}
fn skip_quoted(text: &str, start: usize, quote: char) -> usize {
let mut i = start + 1;
let bytes = text.as_bytes();
while i < bytes.len() {
if bytes[i] == b'\\' && quote == '"' {
i += 2;
continue;
}
if bytes[i] as char == quote {
if bytes.get(i + 1) == Some(&(quote as u8)) {
i += 2;
continue;
}
return i + 1;
}
i += 1;
}
bytes.len()
}
fn read_sheet_ref(text: &str, start: usize, end: usize) -> Option<(String, String)> {
let sheet = unescape_sheet(&text[start..end.saturating_sub(1)]);
let after = end + 1;
let range = read_a1_range(text, after)?;
Some((sheet, range))
}
fn unescape_sheet(sheet: &str) -> String {
sheet.replace("''", "'")
}
fn read_a1_range(text: &str, at: usize) -> Option<String> {
let bytes = text.as_bytes();
let first = read_cell_at(text, at)?;
let after = at + first.len();
if bytes.get(after) == Some(&b':') {
if let Some(second) = read_cell_at(text, after + 1) {
return Some(format!("{first}:{second}"));
}
}
Some(first)
}
fn read_cell_at(text: &str, at: usize) -> Option<String> {
let bytes = text.as_bytes();
let mut i = at;
if bytes.get(i) == Some(&b'$') {
i += 1;
}
let letters_start = i;
while i < bytes.len() && (bytes[i] as char).is_ascii_alphabetic() {
i += 1;
}
if i == letters_start {
return None;
}
if bytes.get(i) == Some(&b'$') {
i += 1;
}
let digits_start = i;
while i < bytes.len() && (bytes[i] as char).is_ascii_digit() {
i += 1;
}
if i == digits_start {
return None;
}
Some(text[at..i].to_string())
}
fn expand_range(start: &str, range: &str, out: &mut BTreeSet<String>) {
let Some((from, to)) = range.split_once(':') else {
out.insert(strip_dollars(start));
return;
};
let Ok((from_letters, from_row)) = coordinate_from_string(from) else {
return;
};
let Ok((to_letters, to_row)) = coordinate_from_string(to) else {
return;
};
let (Ok(from_col), Ok(to_col)) = (
column_index_from_string(&from_letters),
column_index_from_string(&to_letters),
) else {
return;
};
if from_row > to_row || from_col > to_col {
return;
}
if to_col - from_col > 4096 || to_row - from_row > 65_536 {
return;
}
for row in from_row..=to_row {
for column in from_col..=to_col {
if let Ok(letters) = get_column_letter(column) {
out.insert(format!("{letters}{row}"));
}
}
}
}
pub fn formula_at(worksheet: &Worksheet, coordinate: &str) -> Option<String> {
let cell = worksheet.get_cell(coordinate)?;
if cell.data_type != DataType::Formula {
return None;
}
match cell.internal_value() {
CellValue::Formula(expression) if !expression.is_empty() => Some(expression.clone()),
_ => None,
}
}
pub fn formula_cells(worksheet: &Worksheet) -> Vec<(String, String)> {
worksheet
.cells()
.filter(|cell| cell.data_type == DataType::Formula)
.filter_map(|cell| {
let coordinate = cell.coordinate();
match cell.internal_value() {
CellValue::Formula(expression) if !expression.is_empty() => {
Some((coordinate, expression.clone()))
}
_ => None,
}
})
.collect()
}
impl Worksheet {
pub fn trace_precedents(&self, coordinate: &str) -> Result<Vec<String>> {
let start = normalise(coordinate)?;
let mut order = Vec::new();
let mut seen = BTreeSet::new();
let mut on_stack = BTreeSet::new();
self.visit_precedents(&start, &start, &mut order, &mut seen, &mut on_stack)?;
Ok(order)
}
fn visit_precedents(
&self,
start: &str,
key: &str,
order: &mut Vec<String>,
seen: &mut BTreeSet<String>,
on_stack: &mut BTreeSet<String>,
) -> Result<()> {
if !on_stack.insert(key.to_string()) {
return Ok(());
}
if !seen.insert(key.to_string()) {
on_stack.remove(key);
return Ok(());
}
if let Some(expression) = formula_at(self, key) {
let references = parse_references(&expression);
for cell in references.cells {
self.visit_precedents(start, &cell, order, seen, on_stack)?;
}
}
if key != start {
order.push(key.to_string());
}
on_stack.remove(key);
Ok(())
}
pub fn trace_dependents(&self, coordinate: &str) -> Result<Vec<String>> {
let key = normalise(coordinate)?;
let graph = self.dependency_graph()?;
Ok(order_from(&key, &graph))
}
pub fn dependency_graph(&self) -> Result<BTreeMap<String, BTreeSet<String>>> {
let mut graph: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();
for (coordinate, expression) in formula_cells(self) {
let mut references = parse_references(&expression);
references.cells.remove(&coordinate); graph.insert(coordinate, references.cells);
}
Ok(graph)
}
pub fn circular_references(&self) -> Result<Vec<Vec<String>>> {
let graph = self.dependency_graph()?;
Ok(find_cycles(&graph))
}
}
fn order_from(start: &str, graph: &BTreeMap<String, BTreeSet<String>>) -> Vec<String> {
let mut readers: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
for (cell, reads) in graph {
for read in reads {
readers
.entry(read.as_str())
.or_default()
.push(cell.as_str());
}
}
let mut order = Vec::new();
let mut seen = BTreeSet::new();
let mut queue = VecDeque::from([start]);
while let Some(current) = queue.pop_front() {
if !seen.insert(current.to_string()) {
continue;
}
for reader in readers.get(current).into_iter().flatten() {
if !order.contains(&(*reader).to_string()) {
order.push((*reader).to_string());
}
queue.push_back(reader);
}
}
order
}
fn find_cycles(graph: &BTreeMap<String, BTreeSet<String>>) -> Vec<Vec<String>> {
#[derive(Clone, Copy, PartialEq)]
enum Mark {
Open,
Done,
}
fn walk(
node: &str,
graph: &BTreeMap<String, BTreeSet<String>>,
marks: &mut BTreeMap<String, Mark>,
path: &mut Vec<String>,
found: &mut Vec<Vec<String>>,
) {
match marks.get(node) {
Some(Mark::Done) => return,
Some(Mark::Open) => {
if let Some(start) = path.iter().position(|cell| cell == node) {
let mut cycle = path[start..].to_vec();
cycle.push(node.to_string());
if !found.contains(&cycle) {
found.push(cycle);
}
}
return;
}
None => {}
}
marks.insert(node.to_string(), Mark::Open);
path.push(node.to_string());
if let Some(reads) = graph.get(node) {
for read in reads {
if graph.contains_key(read) {
walk(read, graph, marks, path, found);
}
}
}
path.pop();
marks.insert(node.to_string(), Mark::Done);
}
let mut marks = BTreeMap::new();
let mut path = Vec::new();
let mut found = Vec::new();
for node in graph.keys() {
walk(node, graph, &mut marks, &mut path, &mut found);
}
let mut seen: BTreeSet<Vec<String>> = BTreeSet::new();
let mut unique = Vec::new();
for cycle in found {
let mut key = cycle.clone();
key.sort();
key.dedup();
if seen.insert(key) {
unique.push(cycle);
}
}
unique
}
fn normalise(coordinate: &str) -> Result<String> {
let cleaned = strip_dollars(coordinate.trim().trim_start_matches('='));
let (letters, row) = coordinate_from_string(&cleaned)?;
column_index_from_string(&letters)?;
if row == 0 {
return Err(Error::CellCoordinates(format!("{coordinate} has no row")));
}
Ok(format!("{letters}{row}"))
}
pub fn is_unknown_cell(coordinate: &str) -> Result<()> {
normalise(coordinate).map(|_| ())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::cell::cell::CellValue;
fn sheet() -> Worksheet {
let mut ws = Worksheet::new("S").expect("title");
for (coordinate, value) in [
("A1", "1"),
("A2", "2"),
("A3", "3"),
("A4", "=SUM(A1:A3)"),
("A5", "=A4*2"),
("B1", "0.5"),
] {
let value = match value.strip_prefix('=') {
Some(expression) => CellValue::formula(expression),
None => CellValue::number(value.parse().expect("number")),
};
ws.set(coordinate, value).expect("set");
}
ws
}
#[test]
fn a_single_reference_is_parsed() {
let found = parse_references("=A1+1");
assert_eq!(found.cells.iter().cloned().collect::<Vec<_>>(), ["A1"]);
}
#[test]
fn dollars_are_anchoring_not_identity() {
let found = parse_references("=$B$2+$C3");
let mut cells: Vec<&String> = found.cells.iter().collect();
cells.sort();
assert_eq!(cells, ["B2", "C3"]);
}
#[test]
fn a_range_is_expanded_to_its_cells() {
let found = parse_references("=SUM(A1:A3)");
assert_eq!(found.cells.len(), 3);
assert!(found.cells.contains("A2"));
}
#[test]
fn a_function_name_is_not_a_reference() {
let found = parse_references("=LOG10(A1)");
assert_eq!(found.cells.iter().cloned().collect::<Vec<_>>(), ["A1"]);
}
#[test]
fn a_quoted_literal_is_not_a_reference() {
let found = parse_references("=IF(A1>0,\"A1\",\"B2\")");
let mut cells: Vec<&String> = found.cells.iter().collect();
cells.sort();
assert_eq!(cells, ["A1"]);
}
#[test]
fn booleans_are_not_defined_names() {
let found = parse_references("=IF(A1=TRUE,1,0)");
assert!(found.named.is_empty(), "{:?}", found.named);
assert!(found.cells.contains("A1"));
}
#[test]
fn a_defined_name_is_reported_rather_than_guessed_at() {
let found = parse_references("=SUM(Totals)+A1");
assert!(found.named.contains("Totals"));
assert!(found.cells.contains("A1"));
}
#[test]
fn a_cross_sheet_reference_keeps_its_sheet() {
let found = parse_references("=Data!B2+C3");
assert!(found
.cross_sheet
.contains(&("Data".to_string(), "B2".to_string())));
assert!(found.cells.contains("C3"));
}
#[test]
fn a_quoted_sheet_name_keeps_its_spaces() {
let found = parse_references("='Q1 Sales'!B2");
assert!(found
.cross_sheet
.contains(&("Q1 Sales".to_string(), "B2".to_string())));
}
#[test]
fn precedents_come_back_in_dependency_order() {
let ws = sheet();
let order = ws.trace_precedents("A5").expect("precedents");
assert!(!order.contains(&"A5".to_string()), "{order:?}");
assert_eq!(order.last().map(String::as_str), Some("A4"));
let position = |cell: &str| order.iter().position(|c| c == cell).expect("in order");
assert!(position("A1") < position("A4"));
assert_eq!(order, ["A1", "A2", "A3", "A4"]);
}
#[test]
fn dependents_are_the_formulas_that_read_the_cell() {
let ws = sheet();
let dependents = ws.trace_dependents("A1").expect("dependents");
assert!(dependents.contains(&"A4".to_string()), "{dependents:?}");
assert!(dependents.contains(&"A5".to_string()), "{dependents:?}");
let through = ws.trace_dependents("A4").expect("dependents");
assert!(through.contains(&"A5".to_string()), "{through:?}");
}
#[test]
fn a_cell_is_not_its_own_precedent() {
let mut ws = sheet();
ws.set("C1", CellValue::formula("C1*2"))
.expect("self reference");
let order = ws.trace_precedents("C1").expect("precedents");
assert!(!order.contains(&"C1".to_string()), "{order:?}");
}
#[test]
fn a_cycle_is_found_and_reported_once() {
let mut ws = sheet();
ws.set("D1", CellValue::formula("E1")).expect("D1");
ws.set("E1", CellValue::formula("F1")).expect("E1");
ws.set("F1", CellValue::formula("D1")).expect("F1");
let cycles = ws.circular_references().expect("cycles");
assert_eq!(cycles.len(), 1, "{cycles:?}");
let cells: BTreeSet<&String> = cycles[0].iter().collect();
assert_eq!(cells.len(), 3, "three cells on the cycle: {cycles:?}");
assert_eq!(cycles[0].first(), cycles[0].last());
}
#[test]
fn a_clean_sheet_reports_no_cycles() {
assert!(sheet().circular_references().expect("cycles").is_empty());
}
#[test]
fn a_bad_coordinate_is_refused() {
assert!(is_unknown_cell("not a cell").is_err());
assert!(is_unknown_cell("A1").is_ok());
}
}